Теория игр: что где применять

Разбор задачи про игру почти всегда начинается с трёх вопросов: ходы у игроков одинаковые? партия конечна? позиция распадается на независимые части?

в условии	что брать
одна позиция, граф ходов без циклов	выигрышные и проигрышные позиции
граф ходов с циклами, возможна бесконечная партия	ретроанализ, три исхода
несколько независимых частей	функция Гранди и XOR
кучи камней, берут из одной	ним
берут не больше $k$	ним с Гранди $x \bmod (k+1)$
проигрывает взявший последний	мизерный ним
двигают к краю, у края объекты исчезают	лестничный ним
две кучи, можно брать поровну из обеих	игра Уайтхоффа
большие ограничения, игра простая	искать закономерность
ход зависит от предыдущего хода соперника	позиция — пара (что осталось, что разрешено)

Что проверить до того, как писать

• Кто проигрывает. «Не может сходить» и «взял последний» — разные игры.
• Одинаковы ли ходы. Если у игроков разные наборы ходов, вся теория Гранди неприменима.
• Конечна ли партия. Появился цикл — нужен ретроанализ и третий исход.
• Независимы ли части. Ход, задевающий сразу две части, ломает XOR.

Оценка бюджета

подход	стоимость
перебор с запоминанием на графе позиций	$O(V + E)$
ретроанализ	$O(V + E)$
Гранди для игры вычитания до $n$	$O(n \cdot |S|)$
поиск периода	$O(n \cdot \text{период})$ в худшем случае
ответ по формуле	$O(1)$ на запрос

Практический вывод: если $n \le 10^6$, считайте перебором и не ищите формулу. Если $n$ до $10^{18}$ — формула нужна обязательно, и её всё равно сначала угадывают по таблице, посчитанной перебором.