Сумма игр и теорема Шпрага — Гранди

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

Это не редкость, а типичная ситуация: несколько куч камней, несколько фишек на графе, пирог с тремя измерениями, набор отдельных компонент — всё это суммы.

Теорема

$$G(\text{сумма}) = G_1 \oplus G_2 \oplus \ldots \oplus G_k.$$

Отсюда сразу: сумма проигрышна ровно тогда, когда XOR значений равен нулю.

Почему именно XOR, видно из двух свойств, которые нужны от суммы:

• из позиции со значением $S \ne 0$ должен существовать ход в позицию со значением $0$;
• из позиции со значением $0$ такого хода быть не должно.

Первое: возьмём старший единичный бит $S$. Найдётся слагаемое $G_i$, у которого этот бит тоже единица (иначе он не появился бы в XOR). Тогда $G_i \oplus S < G_i$, и по определению $\mathrm{mex}$ в $i$-й игре есть ход в позицию со значением ровно $G_i \oplus S$. После него XOR станет $S \oplus G_i \oplus (G_i \oplus S) = 0$.

Второе: любой ход меняет ровно одно слагаемое и меняет его значение (на равное перейти нельзя — иначе $\mathrm{mex}$ включал бы само себя). Значит XOR изменится и нулём не останется.

Как этим пользоваться

long long total = 0;
for (auto &part : parts) total ^= grundy(part);
if (total == 0) { /* проигрыш */ }

А чтобы назвать сам ход, ищут слагаемое, где старший бит total установлен, и переводят его в состояние со значением g ^ total:

for (auto &part : parts) {
    long long g = grundy(part), need = g ^ total;
    if (need < g) { /* ход в этой части в состояние со значением need */ }
}

Условие need < g — тот же самый критерий «старший бит total стоит в g», записанный короче.

Осторожно: это условие годится, только чтобы найти какой-нибудь выигрышный ход. Оно не перечисляет все ходы: $\mathrm{mex}$ запрещает у соседей лишь само значение $G_i$, а значения больше $G_i$ у них бывают. Поэтому ход в состояние со значением $need > G_i$ вполне может существовать — просто он не гарантирован.

Если задача просит конкретный ход (первый по номеру, наименьший из всех), отбрасывать слагаемые по условию need < g нельзя — надо честно проверять каждое.

Где теорема не работает

нарушено	пример
ходы игроков различаются	шахматы, любые «свои и чужие» фигуры
проигрывает сделавший последний ход	мизерные игры
ход меняет сразу несколько слагаемых	ним Мура, разрезание сразу по двум осям
игра бесконечна	графы с циклами — там ретроанализ

Первая и последняя строки — жёсткие: теория Гранди про них ничего не говорит. Мизерный случай для нима разобран отдельно и оказывается почти таким же; см. «Ним».

Смежное

• Функция Гранди;
• Исключающее «или».