Теория игр: выигрышные и проигрышные позиции (задания 19–21)

Разбираемся в фундаменте заданий 19–21: что такое позиция игры, чем выигрышная отличается от проигрышной и как это перебрать кодом.

Выигрышная стратегия — правило выбора ходов, при котором игрок побеждает при ЛЮБЫХ ответах соперника.

Что проверяют задания 19–21

Это блок из трёх связанных заданий (19 — базовый, 20 — повышенный, 21 — высокий уровень), все про одну и ту же игру двух игроков. Обычно есть куча (или две кучи) камней, два игрока ходят по очереди, ходы заданы (например, «добавить один камень» или «увеличить кучу вдвое»), игра заканчивается при достижении порога. Нужно анализировать, у кого есть выигрышная стратегия.

На КЕГЭ эти задания решают перебором дерева игры: вместо ручного анализа пишут рекурсию, которая для каждой позиции говорит, выигрышная она или проигрышная. Один аккуратный код закрывает все три задания варианта.

Ключевые определения

Рассматриваем игру с точки зрения игрока, который должен ходить сейчас (позиция «чей ход»).

Выигрышная позиция (W) — существует ход, после которого соперник попадает в проигрышную позицию. Достаточно одного хорошего хода.
Проигрышная позиция (P) — любой ход ведёт соперника в выигрышную позицию. Что ни сделай — соперник побеждает.
Терминальная позиция — игра закончена; тот, кто сделал последний ход, выиграл.

Эти определения рекурсивны: чтобы классифицировать позицию, надо знать классы позиций, в которые из неё можно перейти. Поэтому удобнее всего рекурсия с мемоизацией (lru_cache).

Дерево игры

Дерево игры — это все возможные партии: корень — стартовая позиция, рёбра — ходы, узлы — позиции. На чётных уровнях ходит первый игрок, на нечётных — второй. Лист — конец партии. Задание 21 часто прямо просит нарисовать дерево всех партий при выигрышной стратегии — кодом мы сначала находим, кто выигрывает, а потом руками рисуем нужную ветку.

Старт S=22 (ходит Петя)
├── +1 → 23 (ходит Ваня) ──► Ваня может ...
└── ×2 → 44 (ходит Ваня) ──► Ваня выигрывает (44+1=45 < 49, ...)
... и так далее, пока кто-то не достигнет порога

Универсальный код-классификатор

Сформулируем типовую игру: одна куча, ходы — «+1 камень» и «×2 камня», игра кончается при достижении 49 камней, выигрывает сделавший последний ход. Функция is_win(s) возвращает True, если игрок, которому ходить из позиции s, выигрывает при оптимальной игре.

from functools import lru_cache

LIMIT = 49

def moves(s):
    return [s + 1, s * 2]      # допустимые ходы из позиции s

@lru_cache(maxsize=None)
def is_win(s):
    if s >= LIMIT:
        return False           # игра кончилась, ходить нельзя — текущий уже проиграл
    for m in moves(s):
        if m >= LIMIT:
            return True        # этим ходом достигли порога — победа
        if not is_win(m):
            return True        # соперник попадает в проигрышную позицию — победа
    return False               # все ходы ведут соперника к победе — проигрыш

# Проигрышные позиции (для того, кто ходит): это и есть «опорные» точки игры
losing = [s for s in range(1, LIMIT) if not is_win(s)]
print("Проигрышные позиции для игрока, который ходит:", losing)

Вывод:

Проигрышные позиции для игрока, который ходит: [1, 4, 6, 14, 16, 18, 20, 22, 24]

Эта таблица — каркас для всех трёх заданий. Если S — проигрышная позиция для того, кто ходит, значит первый игрок (Петя) проигрывает, а второй (Ваня) выигрывает. Если выигрышная — наоборот.

Как читать формулировки

Формулировка	Что искать
«у Пети есть выигрышная стратегия»	S — выигрышная позиция (is_win(S) = True)
«у Вани есть выигрышная стратегия»	S — проигрышная позиция для ходящего (is_win(S) = False)
«выигрывает первым ходом»	есть ход сразу в терминал (m ≥ LIMIT)
«выигрывает не позднее второго хода»	победа за ≤ 2 своих хода с учётом защиты

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

Путают, чья позиция. Классификатор отвечает про игрока, который ХОДИТ сейчас. Для второго игрока ответ инвертируется.
Неверный порог. «Не менее 49» — это >= 49; «более 48» — то же; внимательно к границе.
Неверные ходы. «Увеличить вдвое» — это s*2, а не s+s+1; читайте правила буквально.
Забывают мемоизацию. Без lru_cache рекурсия для двух куч может быть очень медленной.

Итог

Позиция выигрышна, если ЕСТЬ ход в проигрышную позицию соперника; проигрышна, если ВСЕ ходы ведут в выигрышные.
Рекурсия с lru_cache классифицирует все позиции; таблица проигрышных позиций — каркас для заданий 19–21.
Ответ функции — про игрока, который ходит сейчас; для второго игрока инвертируйте.