Ним-сумма позиции игры: как XOR решает кто выиграет

Ним-сумма позиции игры - это побитовое исключающее ИЛИ (XOR) размеров всех куч. Одно это число отвечает на главный вопрос комбинаторной игры: кто выиграет при идеальной игре обеих сторон. Если ним-сумма равна нулю, ходящий проигрывает; если отлична от нуля - у него есть выигрышная стратегия. Ниже разберём, почему так работает, как найти спасительный ход и где появляется теорема Спрэга-Гранди. Калькулятор ниже соберёт условие вашей задачи и покажет полный разбор позиции.

Что такое ним и его позиция

Ним - классическая игра с полной информацией: на столе несколько куч камней, два игрока ходят по очереди, за ход берут любое положительное число камней из одной кучи. Проигрывает тот, кто не может сделать ход - то есть забравший последний камень выигрывает (нормальная конвенция). Позиция игры полностью описывается набором размеров куч, например $(3, 4, 5)$.

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

Рассчитать для своей задачи

Ним-сумма: побитовое XOR размеров куч

Ним-сумма позиции $(a_1, a_2, \dots, a_n)$ - это

$$S = a_1 \oplus a_2 \oplus \dots \oplus a_n,$$

где $\oplus$ - побитовое исключающее ИЛИ. Чтобы посчитать её вручную, запишите каждый размер в двоичной системе и сложите столбцы по модулю 2: в каждом разряде единица, если число единиц в этом столбце нечётно, и ноль, если чётно.

Для позиции $(3, 4, 5)$:

$$\begin{aligned} 3 &= 011_2 \\ 4 &= 100_2 \\ 5 &= 101_2 \\ \hline S &= 010_2 = 2. \end{aligned}$$

Ним-сумма равна $2 \neq 0$, значит позиция выигрышная для того, чей ход. XOR коммутативен и ассоциативен, поэтому порядок куч и порядок свёртки не важны - это и делает ним-сумму удобной характеристикой позиции.

Выигрышная и проигрышная позиции

Здесь работает простая дихотомия, доказанная Чарльзом Бутоном ещё в 1901 году:

• P-позиция (Previous player wins, проигрышная для ходящего): ним-сумма $S = 0$. Любой ход уводит из неё.
• N-позиция (Next player wins, выигрышная для ходящего): ним-сумма $S \neq 0$. Найдётся ход в P-позицию.

Логика опирается на два факта. Во-первых, из позиции с $S = 0$ любой ход даёт $S \neq 0$: меняя одну кучу, вы меняете её вклад в XOR, а значит и общую сумму. Во-вторых, из позиции с $S \neq 0$ всегда есть ход в $S = 0$ - его и нужно уметь находить.

Рассчитать для своей задачи

Как найти выигрышный ход

Алгоритм поиска спасительного хода прямой:

1. Посчитайте ним-сумму $S = a_1 \oplus \dots \oplus a_n$. Если $S = 0$, выигрышного хода нет - вы в проигрышной позиции.
2. Найдите старший установленный бит числа $S$. Возьмите любую кучу $a_k$, у которой в этом разряде стоит единица. Такая куча обязательно есть.
3. Новый размер этой кучи равен $a_k \oplus S$. Это число строго меньше $a_k$ (старший бит гасится), значит ход допустим - вы убираете $a_k - (a_k \oplus S)$ камней.

После такого хода ним-сумма станет нулём: вы заменили вклад $a_k$ на $a_k \oplus S$, и общий XOR превратился в $S \oplus a_k \oplus (a_k \oplus S) = 0$. Соперник снова окажется в P-позиции, и так до конца партии.

Для $(3, 4, 5)$ с $S = 2 = 010_2$ старший установленный бит это второй разряд. Единица в нём стоит у кучи 3 ($011_2$). Новый размер: $3 \oplus 2 = 1$. То есть из кучи 3 надо взять 2 камня, получив позицию $(1, 4, 5)$ с ним-суммой $1 \oplus 4 \oplus 5 = 0$.

Обратите внимание: выигрышный ход не обязан быть единственным. Если единица старшего бита ним-суммы стоит сразу в нескольких кучах, любую из них можно привести к нулевой ним-сумме, и все эти ходы одинаково корректны. Важно лишь не ошибиться разрядом: гасить нужно именно старший бит $S$, иначе новый размер кучи может оказаться больше исходного, и ход станет недопустимым (камни в ниме только убирают, добавлять нельзя). Поэтому проверка $a_k \oplus S < a_k$ это не формальность, а гарантия легальности хода.

Теорема Спрэга-Гранди: за пределами нима

Сила ним-суммы не ограничивается самим нимом. Теорема Спрэга-Гранди утверждает: любая беспристрастная игра (impartial game) в позиции эквивалентна одной куче нима некоторого размера. Этот размер называют значением Гранди (или ним-значением) позиции.

Значение Гранди считается через функцию $\operatorname{mex}$ (minimal excludant) - наименьшее неотрицательное целое, которого нет среди значений Гранди позиций-преемников:

$$G(\text{позиция}) = \operatorname{mex}\{\, G(p) : p \text{ - преемник} \,\}.$$

Если игра распадается на независимые компоненты (несколько досок, несколько куч), значение Гранди всей игры - это XOR значений Гранди компонент. То есть та же ним-сумма, только теперь складываются не размеры куч, а их ним-значения. Так анализ сводится к ниму даже там, где правил «бери камни» нет - например в играх на графах или с разбиением куч. Близкий приём свёртки сложного объекта в одно число встречается и при подсчёте через метод минимального элемента в транспортной задаче, где одна характеристика тоже задаёт следующий шаг.

Рассчитать для своей задачи

Misère-ним: когда правило переворачивается

Если конвенция обратная (misère): забравший последний камень проигрывает - стратегия почти та же, но с поправкой. Пока хотя бы в одной куче больше одного камня, играют как в обычном ниме (стремятся к нулевой ним-сумме). Как только остаются только кучи по одному камню, переключаются: оставляют нечётное число единичных куч сопернику, а не чётное. Эта тонкость часто и валит на экзамене - основная теория ним-суммы при этом не меняется, меняется лишь концовка.

Частые ошибки

• Складывают размеры куч арифметически, а не через XOR. Ним-сумма $(3, 4, 5)$ - это $2$, а не $12$. Обычное сложение к теории игр отношения не имеет.
• Путают P- и N-позиции. Нулевая ним-сумма - проигрыш для того, кто ходит сейчас, а не выигрыш. Это контринтуитивно: «у меня ноль» звучит нейтрально, но означает поражение.
• Ищут ход не в той куче. Менять нужно кучу с единицей в старшем бите ним-суммы; в произвольной куче нужного хода может не быть.
• Применяют обычную стратегию в misère-ниме до конца партии. Переключаться на счёт единичных куч надо только в эндшпиле, не раньше.
• Забывают, что Спрэг-Гранди работает лишь для беспристрастных игр. В шахматах или шашках (partizan-игры) ним-сумма напрямую не применима.

FAQ

Чему равна ним-сумма проигрышной позиции? Нулю. Проигрышная (P-позиция) - это ровно та, где XOR размеров всех куч равен нулю. Из неё любой ход ведёт в позицию с ненулевой ним-суммой, то есть отдаёт сопернику выигрышную позицию.

Как ним-сумма связана с двоичной системой? XOR работает поразрядно в двоичной записи: в каждом бите результат равен единице, если число единиц в этом разряде среди всех куч нечётно. Поэтому ним-сумму удобно считать столбиком в двоичном виде, складывая разряды по модулю 2.

Можно ли применять ним-сумму к любой игре? Только к беспристрастным играм с нормальной конвенцией, где оба игрока имеют одинаковый набор ходов из каждой позиции. По теореме Спрэга-Гранди такая игра сводится к ниму через значения Гранди. Для partizan-игр (шахматы, го) нужна более общая теория Конвея.

Коротко

Ним-сумма позиции игры - это XOR размеров куч, и одно это число решает исход: ноль означает проигрыш ходящего (P-позиция), ненуль - выигрыш (N-позиция). Выигрышный ход находят, гася старший бит ним-суммы в подходящей куче. Через значения Гранди и теорему Спрэга-Гранди тот же приём распространяется на любую беспристрастную игру, а misère-вариант требует лишь поправки в эндшпиле.