Игры с выигрышными и проигрышными позициями

В задачах № 19–21 двое игроков по очереди меняют позицию (например, число камней в куче) по заданным правилам. Выигрывает тот, кто первым достиг заданного условия. Обычно игроков зовут Петя и Ваня, Петя ходит первым.

Основная идея

Позиции делятся на две группы для того, кто сейчас ходит:

• проигрышная позиция: любой ход ведёт в позицию, из которой следующий игрок выигрывает; или игра уже закончилась победой предыдущего игрока;
• выигрышная позиция: существует хотя бы один ход в проигрышную для соперника позицию (или сразу выигрышный ход).

Это определение рекурсивное, поэтому его удобно писать программой.

Перебор позиций программой

Пример игры. Есть куча из S камней. За ход можно добавить 1 камень, добавить 3 камня или увеличить количество камней вдвое. Выигрывает тот, после чьего хода в куче станет не менее 21 камня.

from functools import lru_cache

LIMIT = 21

def moves(s):
    return (s + 1, s + 3, s * 2)

@lru_cache(None)
def mover_wins(s):
    if s >= LIMIT:
        return False              # игра окончена: предыдущий игрок уже победил
    return any(not mover_wins(m) for m in moves(s))

for s in range(1, 21):
    print(s, mover_wins(s))

Результат: ходящий проигрывает при S = 2, 6, 8, 10, во всех остальных случаях от 1 до 20 выигрывает. Эти числа можно проверить руками: при S = 10 любой ход (11, 13 или 20) даёт сопернику позицию, из которой он удваивает или добавляет единицу и сразу получает 21 и больше.

Типовые вопросы

Формулировки в вариантах отличаются, но обычно спрашивают следующее:

1. Выигрыш за один ход. Позиции, из которых ходящий выигрывает немедленно: хотя бы один ход ведёт к ≥ LIMIT.
2. Задача № 19. Петя не может выиграть первым ходом, но Ваня выигрывает своим первым ходом при любом ходе Пети. Ищут такое значение S (чаще наибольшее или наименьшее из подходящих).
3. Задача № 20. Петя не может выиграть первым ходом, но может выиграть вторым ходом при любой игре Вани. Обычно просят указать два наименьших подходящих значения S.
4. Задача № 21. Ваня выигрывает первым или вторым своим ходом при любой игре Пети, но не может гарантированно выиграть первым. Обычно просят наименьшее такое S.

Условие из пункта 2 (Ваня выигрывает первым ходом) записывается так:

def wins_now(s):
    return any(m >= LIMIT for m in moves(s))

def vanya_first(s):
    return (not wins_now(s)) and all(m < LIMIT and wins_now(m) for m in moves(s))

print([s for s in range(1, 21) if vanya_first(s)])   # [10]

В нашей игре единственное такое значение — S = 10: Петя не выигрывает сразу, а после любого его хода (11, 13 или 20) Ваня выигрывает одним ходом.

Условие из пункта 3 (Петя выигрывает вторым ходом) требует вложенных проверок: есть такой ход Пети, после которого при любом ответе Вани у Пети выигрыш одним ходом.

def petya_second(s):
    return (not wins_now(s)) and any(
        m < LIMIT and all(k < LIMIT and wins_now(k) for k in moves(m))
        for m in moves(s)
    )

print([s for s in range(1, 21) if petya_second(s)])   # [5, 7, 9]

Для S = 5 Петя играет 5 → 10: из 10 любой ход Вани (11, 13, 20) оставляет Пете выигрыш одним ходом. Два наименьших подходящих значения в нашей игре — 5 и 7.

Условие пункта 4 строится так же, но с общим видом «любой ход Пети → у Вани выигрыш сразу или своим вторым ходом», и затем из найденных значений исключают те, где Ваня выигрывает уже первым ходом (в нашей игре подходят 6 и 8, наименьшее — 6).

Как читать условие

• Внимательно выясните, кто выигрывает при достижении условия: тот, кто сделал ход, или тот, кто должен ходить дальше.
• Условие окончания часто сформулировано как «не менее N» — в коде это >= LIMIT.
• Если ходов несколько, они перечисляются во всех функциях одинаково: пользуйтесь единой функцией moves(s).
• Для игр с двумя кучами позицией служит пара чисел (a, b); запоминание (lru_cache) работает так же.

Типичные ошибки

• Путают, чьи ходы считаются: функция mover_wins всегда говорит о том, кто ходит сейчас.
• Забывают, что при s >= LIMIT ходящий проигрывает: игру уже выиграл предыдущий.
• Используют all вместо any (и наоборот): для ходящего нужен один хороший ход, для соперника — все ходы должны проигрывать.
• Проверяют только позицию S, но не позиции после хода Пети, когда нужен ответ Вани.