Задание 19-21 ЕГЭ (теория игр): как найти выигрышную стратегию через перебор?
Камни/спички, два игрока, можно прибавить столько-то или умножить на столько-то, выигрывает тот, кто наберёт >= N. Надо найти, при каком начальном S выигрывает второй игрок и т.д. Через таблицу рисовать долго и страшно. Можно это закодить?
3 ответа
Да, теория игр в ЕГЭ отлично решается рекурсией с мемоизацией — пишешь функцию «выигрывает ли тот, чей ход». Позиция проигрышная для ходящего, если ВСЕ ходы ведут в выигрышную позицию соперника; выигрышная — если есть хотя бы один ход в проигрышную для соперника.
from functools import lru_cache
def moves(s):
return [s + 1, s * 2] # ходы из условия
@lru_cache(None)
def win(s): # выигрывает ли тот, чей сейчас ход
if s >= 29: # условие конца игры
return False # тот, кто ДОЛЖЕН ходить из >=29, уже проиграл (зависит от формулировки!)
return any(not win(ns) for ns in moves(s))
for s in range(1, 29):
if not win(s):
print('у второго есть стратегия при S =', s)
Аккуратно с тем, кто считается проигравшим при достижении N — это половина успеха. Дальше для заданий 19/20/21 просто меняешь, на каком ходу анализируешь (1-2 хода до победы и т.д.).
Рекурсия «выигрышная/проигрышная позиция» + lru_cache. Кто ходит — выигрывает, если есть ход в проигрышную для соперника.
Через перебор позиций.
