Как находить выигрышные позиции в дискретной игре двух игроков?

В игре с полной информацией оба участника знают текущее состояние и доступные ходы. Чтобы доказать выигрышную стратегию, недостаточно показать одну удачную партию: нужно выбрать…

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

Терминальные состояния

Сначала формально определяют, когда игра заканчивается и кто считается победителем. Терминальная позиция может быть выигрышной или проигрышной для игрока, которому предстоит ход, в зависимости от правила. Неверно заданная база меняет классификацию всего дерева состояний.

Обратная разметка

Позиция выигрышна, если существует хотя бы один ход в проигрышное состояние для соперника. Она проигрышна, если каждый допустимый ход ведёт сопернику в выигрышную позицию. Эти два квантора — «существует» и «для всех» — являются ядром доказательства стратегии.

Число ходов до результата

Задачи могут спрашивать победу ровно за два хода или не позднее определённого момента. Тогда одной метки W/L мало: сохраняют уровень, на котором состояние получает статус. Игрок, стремящийся выиграть, выбирает кратчайший путь к победе, а сопротивляющийся соперник — продолжение, которое её максимально откладывает.

Дерево и динамика

Полное дерево быстро растёт, но одинаковое состояние может возникнуть разными путями. Мемоизация вычисляет его статус один раз и превращает повторяющиеся ветви в ориентированный граф состояний. Если ходы монотонно уменьшают или увеличивают параметр до границы, позиции удобно размечать таблицей.

Формулировка стратегии

В ответе назовите первый ход и опишите реакцию на каждую категорию ответа соперника. Для проверки постройте небольшую таблицу достижимых состояний и убедитесь, что ни один разрешённый ответ не выпал. Конкретная стратегия и индуктивная разметка вместе дают полноценное обоснование, а не прогноз партии.

Рекурсивное определение позиции

В конечной игре позиция выигрышная, если существует ход в проигрышную позицию соперника. Она проигрышная, если ходов нет либо каждый допустимый ход ведёт в выигрышную. Вычисление начинают от терминалов и движутся против направления ходов. В ациклической игре мемоизация не даёт одной позиции вычисляться много раз.

from functools import cache

@cache
def winning(stones: int) -> bool:
    if stones == 0:
        return False
    moves = (stones - step for step in (1, 3, 4) if stones >= step)
    return any(not winning(next_state) for next_state in moves)

for stones in range(13):
    print(stones, "W" if winning(stones) else "L")

Чтобы предъявить стратегию, недостаточно написать «позиция выигрышная». Нужно назвать конкретный первый ход и правило ответа на каждый возможный ход соперника. Если требуется победа ровно за определённое число ходов, к состоянию добавляют глубину и аккуратно различают «не позднее» и «ровно».

Практика: стратегия для игры с камнями

Для ходов −1, −3 и −4 найдите проигрышные позиции до 30 вручную и программой. Для трёх выигрышных стартов укажите ход в проигрышное состояние. Затем измените цель: выигрывает тот, кто забрал последний камень, но ход, оставивший отрицательное число, запрещён. Объясните, почему база остаётся важнее рекурсивной формулы. В дополнительном варианте разрешите удвоение числа и задайте верхнюю границу, чтобы граф состояний оставался конечным.