Статья Автор: Лебедев Дмитрий

NEW_Игровая стратегия. Обобщенная постановка и решение (для математиков и не только)

Сформулируем игру следующим образом:

Есть три непересекающихся множества: G, L, W (L или W могут быть пустыми) и процедура pi,
которая для любого элемента из G возвращает непустое подмножество множества G U L U W
Два игрока, Петя и Ваня, поочередно делают ходы. Первый ход всегда делает Петя.
Ход состоит в том, что для текущей позиции pos определяется результат:
- если pos есть элемент из W, то игра завершается и игрок, который должен сделать ход, объявляется победителем
- если pos есть элемент из L, то игра завершается и игрок, который должен сделать ход, считается проигравшим, а победителем объявляется его соперник
- если pos есть элемент из G, то строится/получается множество Y = pi(pos) и игрок, в качестве хода, выбирает один из элементов Y
Считается, что игроки знают результаты pi(pos) для всех pos из G.
Гарантируется завершение игры за конечное число ходов при любых действиях игроков

Ваша задача

Провести кластеризацию множества G, разбив его на два подмножества P и V

P - множество элементов, для который выигрышная стратегия есть у Пети
V - множество элементов, для которых выигрышная стратегия есть у Вани

Для каждого из элементов G определить глубину выигрышной стратегии

Считается, что у игрока есть выигрышная стратегия (ВС), если он может выиграть при любых ходах соперника

Глубиной ВС назовем минимальное число ходов, необходимых игроку для победы при любых ходах соперника

Рассмотрим стандартную задачу ЕГЭ, немного усложним и сформулируем в рамках введенных определений

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя.
За один ход игрок может: убрать из кучи два камня или убрать из кучи пять камней или уменьшить количество камней в куче в три раза (целочисленное деление на 3).
Игра завершается, когда количество камней в куче становится не более 19.
Если при этом количество камней будет нечётным, то Победителем считается игрок, сделавший последний ход,
а если чётным, то Победителем объявляется его соперник

Определим множества G, L, W и функцию pi

G = {20, 21, ... , 2000} (2000 взято для того, чтобы рассмотреть всех ходы с глубиной ВС < 3)
L = {1, 3, 5, 7, 9, 11, 13, 15,17, 19} - переход в L равнозначен/гарантирует Победу, поскольку Противник будет объявлен проигравшим. Для Победы игрок ДОЛЖЕН стремиться попасть в L
W = {0, 2, 4, 6, 8, 10, 12, 14, 16, 18} - переход в W - равнозначен поражению (соперник Побеждает), значит надо избегать хода в W
pi (pos) - возвращает множество значений pos - 2, pos - 5, pos // 3

Составим алгоримт решения задачи. Будем использовать принцип динамического программирования.
1. Инициализируем счетчик тактов работы нулем. (Такт работы это ход одного из игроков. Петя ходит в нечётные такты, а Ваня в чётные)
2. Организуем цикл while пока G не станет пустым (или на определенное число тактов - глубину просмотра). После каждого такта будем удалять из G некоторые элементы, перенося их в L или W
Для программы нам подтребуются две подпрограмм pi и step - подпрограмма, определяющая какие элементы необходимо переместить из G
3. Результат работы каждого такта будем записывать в словарь (ключ - номер такта)

Решение приведем для указанного примера, пункт 3 пока не будем выполнять (для ЕГЭ этого не надо)
При решении объединим множества L, W в словарь

def pi(pos) : # pi от слова периферия - окружение
  return { pos - 2, pos - 5, pos // 3} 
def step (S, X, t): # поиск результата такта t
  Y = set() # результат работы
  for pos in S : # перебор игровых точек и поиск результата в зависимости от такта работы
    if (t % 2 == 1) and (pi(pos) & X)  or  (t % 2 == 0) and (pi(pos) <= X): Y.add(pos) 
  return Y 
swin = int(input()) # параметры игры
G = set([i for i in range(swin, swin * 3 ** 4)]) # Множство стартовых точек
LW = {0 : set([i for i in range (0, swin, 2)]), 1 : set([i for i in range (1, swin, 2)])} # словарь исходов L = LW[0], W = LW[1]
t = 0 # инициализация такта
while t < 6: # просмотр 6 тактов работы
  t +=1 # переход к новому такту
  R = step(G, LW[t % 2], t) # получение результата работы
  G = G - R #  уменьшение множества G
  LW[(t + 1) % 2] = LW[(t + 1) % 2].union(R) # перенос результатов в финальные множества 
  print('R{} = '.format(t),sorted(R),) # вывод результатов

Решение не является оптимальным, написано наиболее сжатым способом (для любителей) и возможно не очень легко читается. Это сделано сознательно

В ответе выводятся результаты только шести тактов работы (это более чем достаточно для ответов на вопросы ЕГЭ).
Сформулируем вопросы возможные вопросы ЕГЭ и определим ответы на них по выводу программы

Задание 19:
- Ваня выиграл после неудачного хода Пети. При каком наибольшем значении s (камней в куче) это могло произойти
  смотрим строчку R1 находим максимум x : x // 3 = max(К1) - легко понять, что x = max(R1)*3 +2 = 179
- Найдите максимальное/минимальное значение s, при котором Ваня имеет выигрышную стратегию глубины 1 (или Петя не может выиграть, а Ваня выигрывает после 1 хода при любом ходе Пети) - ответ в R2 (первый ход Вани - это второй такт) равный 26/25
Задание 20
- Петя не может выиграть первым ходом, но имеет выигрышную стратегия для победы вторым ходом. Найдите максимальное и минимальное/два средних значения s когда это возможно - ответы находим в строке R3 (3 такт, второй ход Пети)
Задание 21
- Ваня имеет выигрышную стратегию глубиной два хода (то есть, может выиграть первым или вторым ходом, но не может гарантированно выиграть в один ход). При каких s это возможно. Укажите минимальное/максимальное/среднее и т.п. значение - ответы находим в R4 (4 такт, второй ход Вани

Рассмотрим задание на две кучи. Для этого возьмем задачу с kompege.ru
Условие

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) 10 камней или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 5 камней, такую позицию в игре будем обозначать (10, 5). Тогда за один ход можно получить любую из четырёх позиций: (20, 5), (10, 15), (10, 10). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 107. Если при этом суммарное количество камней в двух кучах не превышает 170, победителем считается игрок, совершивший последний ход, иначе его противник. В начальный момент в первой куче было 5 камней, во второй куче – S камней, 1 ≤ S ≤ 100.

Определим, G, L, W

G = set([ (i, j) for i in range (1,107) for j in range (1, 107 - i)]) - все точки с суммой координат не превосходящей 106
L = set([ (i,j) for i in range (1,171) for j in range(1, 171 - i)]} - G : все точки с суммой координат не превосходящей 170 и не принадлежащих G
W = set([ (i,j) for i in range (1,213) for j in range(1, 213 - i)]} - L - G :- все точки с суммой координат не превосходящей 213 и не принадлежащих G или L
(точки в имеют сумму не более 106, "максимальная операция" - умножение одной кучи на два, значит новая сумма увеличится не более чем в два раза)

Добавим еще множество Start = set ([ (5, i) for i in range (101)])

def pi(pos) : # pi от слова периферия - окружение
  x, y = pos 
  return {(x + 10, y), (x , y + 10), (x *  2, y), (x, y * 2)} 
def step (S, X, t): # поиск результата такта t
  Y = set() # результат работы
  for pos in S : # перебор игровых точек и поиск результата в зависимости от такта работы
    if (t % 2 == 1) and (pi(pos) & X)  or  (t % 2 == 0) and (pi(pos) <= X): Y.add(pos) 
  return Y 
swin, sper = map(int,input().split()) # параметры игры swin = 107, sper = 171
aa = 5 # определение стартовой строки 
St = set([(aa,i) for i in range(1, swin -aa -1)]) 
G = set([(i,j) for i in range(1, swin) for j in range(1, swin - i)]) # Множство стартовых точек
L = set([(i,j) for i in range(1, sper) for j in range(1, sper - i)]) # Множство точек для L
W = set([(i,j) for i in range(1, 2 * sper +1) for j in range(1, 2 * sper +1 - i)]) # Множство точек W
LW = {0 : W - L - G, 1 : L - G} # словарь исходов L = LW[0], W = LW[1]
t = 0 # инициализация такта
while t < 6: # просмотр 6 тактов работы
  t +=1 # переход к новому такту
  R = step(G, LW[t % 2], t) # получение результата работы
  G = G - R #  уменьшение множества G
  LW[(t + 1) % 2] = LW[(t + 1) % 2].union(R) # перенос результатов в финальные множества 
  print('R{} = '.format(t),sorted(R & St),) # вывод результатов

Вопросы и поиск ответов:

Задание 19.
Известно, что Ваня выиграл своим первым ходом после неудачного хода Пети. При каком минимальном значении S такое возможно?
Ответ найдем с строке R1. Минимальные значения (5, 51), (5, 52), и в позицию (5,52) можно попасть из (5, 26). Ответ 26

Задание 20.
Для игры, описанной в задании 19, известно, что Петя имеет выигрышную стратегию.
Укажите два минимальных значения:
1.      при котором Петя имеет выигрышную стратегию своим первым или вторым ходом, при этом Ваня должен совершить свой первый ход.
2.      при котором Петя имеет выигрышную стратегию своим вторым ходом при любой игре Вани.
В качестве ответа укажите сначала значение для п.1, затем для п.2.
Ответ найдем с строке R3 и R2.
Ответ на пункт 2 - это минимальные значения в R3 (5, 25)
Для ответа на п1. надо уяснить, что у Пети должна быть возможность выиграть первым ходом, то есть Петя должен дать Ване проиграть по правилу 171.
Получаеся, что Петя из (5,s) пойдет в (5,2s) и попадет в R2 (ходить в (15,s) можно, но s ,будет больше). Причем 5 + 4s >= 171, значит s >= 42 и (5,2s) есть в R2.
Минимальным таким s будет s = 44  Ответ 44 25

Задание 21.
Для игры, описанной в задании 19, известно, что Ваня имеет выигрышную стратегию за один или два хода, при этом не имеет выигрышной стратегии в один ход. Найдите минимальное значение S, при котором это возможно.
Ответ найдем с строке R4. Минимальные значения (5, 34) Ответ 34

Предлагаемый подход возник в ходе обсуждений с учениками и является "компромисом" между длиной кода, простотой понимания, эффективностью работы.
Вы можете попробовать написать свой вариант решения и проверить его правильность

Чтобы оставить комментарий нужна авторизация

Печать