Введение: Абсолютная предопределенность за простыми правилами — Беспристрастные комбинаторные игры

На столе лежат три кучки камней: в первой — $3$ камня, во второй — $4$, в третьей — $5$. Два игрока ходят по очереди; за один ход разрешается выбрать любую одну кучку и взять из неё хотя бы один камень (можно забрать и всю кучку целиком). Побеждает тот, кто заберёт последний камень. Это знаменитая игра Ним (Nim), прославленная в кинематографе фильмом Алена Рене «В прошлом году в Мариенбаде». На первый взгляд кажется, что это психологическая дуэль и состязание в расчёте вариантов, но с точки зрения математики исход партии предрешён на $100\,\%$ ещё до первого хода: если первый игрок знает алгебраический инвариант, скрытый в двоичной записи чисел, он гарантированно выиграет при любых ответных действиях соперника.

В современной математике такой класс игр называется беспристрастными комбинаторными играми (Impartial Combinatorial Games) и удовлетворяет пяти аксиомам: (1) два игрока делают ходы поочерёдно; (2) полная информация (Perfect Information) без скрытых карт; (3) детерминированность без кубиков и случайности; (4) беспристрастность (Impartiality), означающая, что в любой позиции множество допустимых ходов абсолютно одинаково для обоих игроков (в отличие от пристрастных игр вроде шахмат или го, где каждый двигает только фигуры своего цвета); и (5) конечность партии, гарантирующая завершение за конечное число шагов на направленном ациклическом графе (DAG). При стандартном правиле — нормальном соглашении об игре (Normal Play Convention) — проигрывает тот, кто не может сделать очередной ход (то есть выигрывает игрок, сделавший последний ход).

По обратной индукции (теорема Цермело) все позиции беспристрастной игры единственным образом разбиваются на два непересекающихся класса: $\mathcal{P}$-позиции (Previous-player winning — выигрышные для только что сходившего игрока, то есть проигрышные для того, чья очередь ходить) и $\mathcal{N}$-позиции (Next-player winning — выигрышные для игрока, чья очередь ходить). Их рекурсивное определение безупречно: все терминальные позиции без ходов являются $\mathcal{P}$-позициями; позиция является $\mathcal{N}$-позицией, если из неё существует хотя бы один допустимый ход в некоторую $\mathcal{P}$-позицию; и позиция является $\mathcal{P}$-позицией, если все допустимые ходы из неё ведут исключительно в $\mathcal{N}$-позиции.

  flowchart TD
    A["Impartial Game Position G"] --> B{"Compute Grundy Value g(G)"}
    B -->|"g(G) > 0"| C["N-Position: Next Player Wins"]
    B -->|"g(G) = 0"| D["P-Position: Previous Player Wins"]
    C -->|"Optimal Move: Choose option G' with g(G') = 0"| D
    D -->|"Every Legal Move: Flips at least one bit"| C

1. Открытие Чарльза Бутона (1901): Побитовый XOR (Ним-сумма) и две леммы об инварианте

Когда кучек много, а камней в них миллионы, прямой обход графа состояний с обратной индукцией приводит к экспоненциальному взрыву. В 1901 году математик Гарвардского университета Чарльз Леонард Бутон (Charles Leonard Bouton) опубликовал фундаментальную статью, полностью решившую игру Ним для любого числа кучек. Он обнаружил, что ключ к победе — записать размеры всех кучек в двоичной системе счисления и вычислить их побитовое исключающее ИЛИ (XOR, называемое ним-суммой или Nim-sum).

Для позиции $(n_1, n_2, \dots, n_k)$ ним-сумма определяется как $S = n_1 \oplus n_2 \oplus \dots \oplus n_k$. Операция $\oplus$ представляет собой поразрядное двоичное сложение без переноса над конечным полем $\mathbb{F}_2 = ext{GF}(2)$ (коммутативное, ассоциативное и удовлетворяющее тождеству $x \oplus x = 0$). Теорема Бутона гласит: Позиция Ним $(n_1, \dots, n_k)$ является проигрышной ($\mathcal{P}$-позицией) тогда и только тогда, когда её ним-сумма равна $S = 0$, и выигрышной ($\mathcal{N}$-позицией) тогда и только тогда, когда $S eq 0$.

Доказательство опирается на две изящные алгебраические леммы: Во-первых, из позиции с $S = 0$ любой допустимый ход неизбежно ведёт к $S' eq 0$. Если игрок уменьшает $i$-ю кучку с $n_i$ до $n_i' < n_i$, двоичные записи $n_i$ и $n_i'$ различаются хотя бы в одном разряде, поэтому $n_i \oplus n_i' eq 0$. Новая ним-сумма равна $S' = S \oplus n_i \oplus n_i' = 0 \oplus (n_i \oplus n_i') eq 0$. Следовательно, игрок в состоянии $S=0$ при любом ходе вынужден передать сопернику выигрышную позицию $S' eq 0$. Во-вторых, из любой позиции с $S eq 0$ всегда существует хотя бы один допустимый ход, дающий $S' = 0$. Рассмотрим старший единичный бит (Most Significant Bit, MSB) числа $S eq 0$, находящийся в разряде $d$. Поскольку $d$-й бит числа $S$ равен $1$, среди чисел $n_1, \dots, n_k$ обязательно найдётся нечётное количество (а значит, хотя бы одна) кучек $n_i$, у которых в разряде $d$ также стоит $1$. Выберем такую кучку $n_i$ и положим новое число камней в ней равным $n_i' = n_i \oplus S$. Так как и у $n_i$, и у $S$ в разряде $d$ стоит $1$, после операции XOR этот бит в $n_i'$ превратится в $0$, а все более старшие биты останутся неизменными. Значит, строго выполняется неравенство $n_i' < n_i$! Взятие $n_i - (n_i \oplus S)$ камней является полностью корректным ходом, а новая ним-сумма становится равной $S' = S \oplus n_i \oplus n_i' = S \oplus n_i \oplus (n_i \oplus S) = 0$. В начальном примере $(3, 4, 5)$ имеем $S = 3 \oplus 4 \oplus 5 = 2 = (010)_2 eq 0$. Старший единичный бит имеет вес $2$ и присутствует в $n_1 = 3 = (011)_2$. Первый игрок уменьшает первую кучку до $n_1' = 3 \oplus 2 = 1$, оставляя позицию $(1, 4, 5)$ с ним-суммой $1 \oplus 4 \oplus 5 = 0$ и обеспечивая себе победу!

2. Теорема Шпрага — Гранди (1935/1939): Любая беспристрастная игра изоморфна Ниму

Спустя три с лишним десятилетия после работы Бутона Роланд Шпраг (Roland Sprague, 1935) и Патрик Майкл Гранди (Patrick Michael Grundy, 1939) независимо друг от друга открыли поразительную универсальную теорему: не только сам Ним, но и абсолютно любая конечная беспристрастная комбинаторная игра при нормальном соглашении математически изоморфна одной-единственной кучке Ним некоторого размера!

Для построения этого изоморфизма вводятся минимальное исключённое значение (Minimum Excluded Value, $ ext{mex}$) и число Гранди (Grundy Value, или нимбер Nimber). Для любого конечного подмножества неотрицательных целых чисел $A \subset \mathbb{N}_0$ величина $ ext{mex}(A)$ определяется как наименьшее неотрицательное целое число, не принадлежащее $A$ (например, $ ext{mex}(\emptyset) = 0$, $ ext{mex}(\{0, 1, 3\}) = 2$). Для произвольной вершины $u$ игрового графа её число Гранди $\mathcal{G}(u)$ рекурсивно определяется как $ ext{mex}$ от множества чисел Гранди всех позиций $v$, достижимых из $u$ за один ход. Отсюда мгновенно следуют два ключевых свойства: (1) $\mathcal{G}(u) = 0$ тогда и только тогда, когда ни один из последователей не имеет значения $0$, то есть $u$ — проигрышная $\mathcal{P}$-позиция; (2) если $\mathcal{G}(u) = g > 0$, то для любого целого $m$ из диапазона $0 \le m < g$ существует хотя бы один ход в позицию $v$ с $\mathcal{G}(v) = m$. Это в точности повторяет поведение одной кучки Ним из $g$ камней!

Более того, когда мы объединяем несколько независимых беспристрастных игр $G_1, G_2, \dots, G_k$ в дизъюнктивную сумму $G = G_1 + G_2 + \dots + G_k$ (на каждом ходу игрок выбирает ровно одну из под-игр и делает в ней ход, пока все под-игры не завершатся), теорема Шпрага — Гранди доказывает, что число Гранди составной игры в точности равно побитовой XOR-сумме чисел Гранди отдельных компонент: $\mathcal{G}(G_1 + \dots + G_k) = \mathcal{G}(G_1) \oplus \dots \oplus \mathcal{G}(G_k)$. Даже если в какой-то под-игре возможен ход, увеличивающий число Гранди (аналог добавления камней в кучку), соперник всегда может нейтрализовать это добавление ответным ходом, вернув прежнее значение. Таким образом, любая сложнейшая игра на графах сводится к вычислению функции $ ext{mex}$ и операции XOR!

  flowchart TD
    G1["Subgame G1: Grundy Value g(G1)"] --> XOR["Bitwise XOR Sum: S = g(G1) XOR g(G2) XOR g(G3)"]
    G2["Subgame G2: Grundy Value g(G2)"] --> XOR
    G3["Subgame G3: Grundy Value g(G3)"] --> XOR
    XOR -->|"Sprague-Grundy Isomorphism"| NIM["Equivalent to 3-Heap Nim (g(G1), g(G2), g(G3))"]

3. Классические приложения и ловушка игры в поддавки (Misère Play)

Теорема Шпрага — Гранди даёт мощный инструмент для анализа множества игр:

• Вычитательные игры (Subtraction Games, игра Баше): за один ход можно брать от $1$ до $m$ камней. Здесь периодически выполняется $\mathcal{G}(n) = n mod (m+1)$, и позиция проигрышна тогда и только тогда, когда $n$ делится на $m+1$.
• Игры с разделением: Кейлс (Kayles) и шахматы Доусона: в игре в кегли Kayles в ряд стоят $n$ кеглей, и за один бросок можно сбить либо $1$ кеглю, либо $2$ стоящие вплотную кегли. Самое интересное происходит, когда кегли выбивают из середины ряда: исходный ряд распадается на два независимых под-ряда длины $a$ и $b$! По теореме Шпрага — Гранди получившаяся позиция эквивалентна дизъюнктивной сумме двух под-рядов, и её функция Гранди равна $\mathcal{G}(a) \oplus \mathcal{G}(b)$. С помощью динамического программирования за время $O(n^2)$ вычисляется вся последовательность (которая начиная с $n \ge 72$ становится строго периодической с периодом $12$).
• Поддавки / Миere-игры (Misère Play — взявший последний камень проигрывает): что изменится, если последний ход приносит поражение? Многие новички ошибочно полагают, что достаточно просто поменять местами $\mathcal{P}$ и $\mathcal{N}$. Бутон доказал точное правило для Ним в поддавки (Misère Nim): пока на столе остаётся хотя бы две кучки размера больше $1$, нужно играть точно так же, как в обычный Ним (поддерживая $S = 0$). И только в тот единственный момент, когда ваш ход впервые оставит на столе исключительно кучки размера $1$, следует изменить ход так, чтобы оставить нечётное число единичных кучек (то есть $S = 1$)! Однако для общих беспристрастных игр в поддавки теорема Шпрага — Гранди полностью рушится; лишь в начале XXI века Тейн Пламбек и Аарон Сигел создали теорию мизерных факторов (Misère Quotients) на базе коммутативных моноидов для алгебраической классификации таких игр.