Игра «Ним»

Рассмотрим следующую игру. Даны $n$ кучек, в каждой из них какое-то количество камней. За один ход игрок может выбрать кучку и выбросить оттуда любое ненулевое число камней. Выигрывает тот игрок, который забрал последний камень.

Немного переформулируем условие. Состояние игры однозначно описывается неупорядоченным набором неотрицательных чисел — пронумеруем их и обозначим количество камней в $i$-й кучке как $a_i$. Теперь, за один ход разрешается строго уменьшить любое из чисел. Терминальное состояние — когда все числа стали нулями.

Теорема. Состояние игры выигрышное тогда и только тогда, когда xor-сумма размеров кучек отлична от нуля:

Доказательство проведём по индукции.

Для терминального состояния кучек уже нет, и xor-сумма равна нулю, и оно действительно проигрышное. База доказана — теперь докажем переходы.

Из состояния с нулевой xor-суммой все переходы ведут в выигрышные состояния, то есть в состояния с ненулевой суммой. В самом деле, достаточно убрать сколько угодно спичек из любой кучки — xor-сумма изменится с нуля на $a_i \oplus b_i$, где $b_i < a_i$ равно числу камней в $i$-й кучке после нашего действия.

Противоположный случай сложнее. Нужно показать, что если xor-сумма ненулевая, то всегда существует такой $b_i < a_i$, что xor-сумма станет нулевой, то есть

Для этого посмотрим на старший единичный бит $S$ и возьмём любой $a_i$, у которого этот бит тоже единичный. Такой $a_i$ найдётся хотя бы один — по свойствам xor, их должно быть нечетное число. Из условия выше следует, что искомый $b_i$ должен быть равен $S \oplus a_i$.

Выясняется, что это корректный новый размер кучки, то есть $b_i < a_i$. Почему так? Потому что все старшие биты в выражении остались нетронутыми, $k$-й бит изменился на единицу, а что происходило с дальнейшими битами нам не важно, потому что эти изменения точно не больше, чем $2^k$.

Получается, что оптимальная стратегия такая: посчитать xor-сумму всех $a_i$, найти такой $a_i$, у которого старший бит взведен, и заменить его на $S \oplus a_i$. (А если xor-сумма $S$ оказалась нулевая, то сдаться.)

#Модификации

#Ним в поддавки (misère nim)

В противоположность обычному ниму, существует также «ним в поддавки»: когда игрок, совершивший последний ход, не выигрывает, а проигрывает.

Решение такого нима удивительно просто. Выигрышность позиции определяется так же, как и в обычном ниме — xor-суммой размеров кучек — но с одним исключением: если размеры всех кучек равны единице, то выигрышность и проигрышность меняются местами.

С учетом этого исключения, будем делать ходы как в обычном ниме, переходя в позицию с нулевой xor-суммой, но если такой ход ведёт в позицию, в которой размеры всех кучек равны единице, то этот ход надо изменить так, чтобы количество остающихся непустых кучек изменило свою чётность.

Доказательство. Рассмотрим некоторое течение игры: выберем произвольную стартовую позицию и выпишем ходы игроков вплоть до завершения игры. В любой игре двух оптимальных игроков рано или поздно наступает момент, когда размеры всех непустых кучек равны единице. Обозначим через $k$ число непустых кучек в этот момент — тогда для текущего игрока эта позиция выигрышна тогда и только тогда, когда $k$ чётно.

Откатимся теперь на один ход назад. Мы оказались в позиции, где ровно одна кучка имеет размер $a_i > 1$, а все остальные кучки (возможно, их было ноль) имеют размер $1$. Эта позиция выигрышна, так как мы всегда можем сделать такой ход, после которого останется нечетное число кучек размера $1$:

• Если всего непустых кучек нечетное количество, то заменяем $a_i$ на $1$.
• В противном случае, заменяем $a_i$ на $0$.

Далее, если продолжим откатываться по игре назад, то для всех состояний выигрышность также будет совпадать с «нормальным» нимом — просто потому, что когда у нас есть более одной кучки размера $>1$, то все переходы ведут в состояния с одной и более кучкой размера $>1$, а для всех них, как мы уже показали, ничего по сравнению с «нормальным» нимом не изменилось.

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

#Ним Мура (k-ним)

Условие. Есть $n$ кучек камней размера $a_i$. Также задано натуральное число $k$. За один ход игрок может уменьшить размеры от одной до $k$ кучек (то есть теперь разрешаются одновременные ходы в нескольких кучках сразу). Проигрывает тот, кто не может сделать хода.

Очевидно, при $k=1$ ним Мура превращается в обычный ним.

Решение. Запишем размер каждой кучки в двоичной системе счисления. Затем просуммируем эти нули и единицы вдоль каждого разряда и возьмём эту сумму по модулю $(k+1)$. Если во всех разрядах получился ноль, то текущая позиция проигрышная, иначе — выигрышная.

Доказательство, как и для обычного нима, заключается в описании стратегии игроков — нужно показать, что

1. из игры с нулевым значением мы можем перейти только в игры с ненулевыми значениями, и
2. из любой игры с ненулевым значением найдется ход в игру с нулевым значением.

Первый пункт доказывается следующим рассуждением. Если для всех разрядов сумма бит по модулю $(k+1)$ была равна нулю, то после изменения от одного до $k$ элементов снова получить нулевую сумму можно только «уравновешиванием» всех изменений: для всех элементов, где определенный бит удаляется, должен быть другой элемент, где этот бит добавляется. В частности, это должно выполняться и для самого старшего разряда, для которого хотя бы один бит у любого числа меняется. Но тогда это будет означать, что существует какой-то элемент, для которого добавилась единица в этом разряде, а все более старших разрядах ничего не менялось — значит, этот элемент будет больше исходного, что нарушает правила.

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

Обозначим за $u$ количество кучек, которые мы уже начали изменять; изначально, $u = 0$. Обратим внимание, что так в этих $u$ кучках мы уменьшали какой-то из предыдущих, более старших, битов, то все более младшие биты мы можем ставить как угодно.

Пусть мы рассматриваем текущий бит, в котором сумма по модулю $(k+1)$ получилась ненулевой. В идеале, мы хотим сделать её нулевой, изменяя в этом разряде только те $u$ элементов, которые мы и так уже собрались изменять. Мысленно поставим во всех из этих $u$ элементов единицы в соответствующем разряде и пересчитаем сумму, обозначив её за $s$. Теперь рассмотрим два случая:

• Если $s \le u$, то мы можем обойтись уже выбранными элементами, убрав в $s$ из них единичный бит.
• В противном случае, если $s > u$ найдем $(s - u)$ дополнительных кучек, у которых рассматриваемый бит единичный, и будем уменьшать их вместе с $u$ уже имеющимися.

После каждой итерации число $u$ изменяемых кучек станет равным $u’ = \max(s, u) \le k$.

Таким образом, мы показали способ выбирать множество изменяемых кучек и какие биты следует в них изменять, чтобы общее их количество $u$ никогда не превысило $k$. Следовательно, мы доказали, что искомый переход из состояния с ненулевой суммой в состояние с нулевой суммой всегда существует, что и требовалось доказать.

#Зачем это вообще надо?

Цугцвангом (от немецкого zug — ход, и zwang — принуждение) в шахматах и многих других стратегических играх называют ситуацию, когда у игрока закончились хорошие ходы, и если бы правила позволяли, он бы просто стоял на месте и передал ход оппоненту.

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

В дальнейших статьях мы разберемся, как сводить подобные игры к ниму.