Ним-игры

Игра "Ним" известна, наверное, всякому, кто читал книги Мартина Гарднера. Но я уверен, что смысл "магического ним-правила" понимают далеко не все. А впрочем, многие ведь и Гарднера не читали или успели крепко подзабыть, так что я начну с самого начала.

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

Для нима существует стратегия, которая сводится к применению уже упомянутого выше "магического правила". Давайте разберем это правило и всю стратегию на примере.

Пусть изначально есть три кучки (A, B и C) в которых находится соответственно 5, 9 и 11 камешков. "Правило" предписывает сделать следующее:

1. Представить каждое из чисел в двоичной системе: 5=4+1, 9=8+1, 11=8+2+1.
2. Вычеркнуть все встретившиеся пары равных слагаемых, в данном случае - пару восьмерок и пару единиц.
3. Сложить оставшиеся степени двойки (4+2+1=7). В результате получается так называемая ним-сумма для данной позиции. Если ним-сумма равна нулю, то такая позиция называется "безопасной", а если отлична от нуля - то "опасной".
4. Если позиция опасна, то нужно сделать ход, переводящий ее в безопасную позицию. Если исходная позиция безопасна - то право первого хода надо уступить сопернику.

Ход игры, когда один из партнеров применяет это правило, сводится к тому, что игроки по очереди получают опасные и безопасные позиции. Так как конечная позиция (0 камешков во всех кучках) имеет нулевую ним-сумму, то она безопасна, а значит, в нее сделаете ход именно вы, а не ваш партнер.

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

Сначала разберемся с ходом. Как следует из правила, ход должен быть сделан так, чтобы в результате каждая степень двойки входила в оставшиеся кучки четное число раз (в данном случае - либо дважды, либо вообще ни разу). В приведенном выше примере в ним-сумму не входила восьмерка, поэтому после хода в кучках B и C должно остаться не менее 8 камешков. Это означает, что если забирать камешки из этих кучек, то возможны всего четыре хода:

• оставить в кучке B 8 камешков (взять 1)
• оставить в кучке C 8 камешков (взять 3)
• оставить в кучке C 9 камешков (взять 2)
• оставить в кучке C 10 камешков (взять 1)

Но все такие ходы оставляют в ним-сумме четверку, а поэтому получающиеся позиции не будут безопасными. Следовательно, надо делать ход, забирая какие-то камешки из кучки A. Легко заметить, что, оставив в ней 2 камешка (то есть забрав три), мы получим безопасную позицию: A=2, B=8+1, C=8+2+1.

Совершенно аналогичным образом нужный ход можно найти и в общем случае. Для этого нужно вычислить двоичные дополнения каждого количества камешков до их ним-суммы (для знатоков программирования это - то же самое, что результат побитовой логической операции XOR: для каждого двоичного разряда 0 XOR 0 и 1 XOR 1 равны 0, а 0 XOR 1 равен 1. Хотя бы для одной кучки такое дополнение будет меньше, чем исходное число камешков в этой кучке. Ход делается именно в этой кучке. Для нашего примера 11 XOR 7 = 12, 9 XOR 7 = 14 и 5 XOR 7 = 2. Так как 12>11 и 14>11, то единственный возможный ход - это оставить два камешка в кучке A, что мы и сделали. Заметим, что и сама ним-сумма - это результат той же операции XOR: 7 = 5 XOR 9 XOR 11.

Пришло самое время дать некоторую пищу для мозгов.

Задача 1

Почему результат операции XOR с несколькими числами не зависит от порядка, в котором выполняются операции?

Задача 2

Почему хотя бы для одного из количеств камешков в кучках двоичное дополнение до ним-суммы будет меньше, чем само это количество? Выполняется ли то же свойство для четырех (или другого четного числа) кучек?

А теперь попробуем посмотреть на другую игру.

В игре "удаление цифр" (о которой я писал год назад в статье "Пять игр Джона Конуэя", "Компьютерра" #198) вначале выписывается какое-нибудь большое число, например 314159. Каждым ходом игрок может либо уменьшить какую-либо цифру (не равную нулю), либо стереть любой нуль и вместе с ним все цифры, стоящие правее его. Например, первый игрок мог уменьшить своим ходом четверку до нуля, а второй - стереть этот нуль и вместе с ним весь кусок 0159, то есть оставить только 31. Игра продолжается до тех пор, пока с доски не стерты все цифры, а игрок, вынужденный стереть последнюю цифру, проигрывает.

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

Для начала назначим числу 0 ним-сумму, равную нулю, числу 1 - сумму 1 и так далее до девятки. Первый нетривиальный случай - число 10. Из него можно получить либо 1 (стерев 0), либо 0 (уменьшив 1 до нуля). Но это значит, что 10 ничем не отличается от числа 2! Поэтому я сопоставлю десятке ним-сумму, равную 2, и двинемся дальше.

До сих пор все числа были "опасными" - из них можно было получить 0 первым же ходом. Число 11 - первое безопасное число: из него можно получить либо 1, либо 10, но 0 получить уже нельзя. Следовательно, его ним-суммой будет 0. Из 12 можно получить либо 02, либо 10, либо 11. Так как ним-суммы этих чисел равны 2 и 0, а единица среди них не встречается, то ним-сумму для числа 12 положим равной 1. И точно так же будем идти дальше, пользуясь еще одним "магическим правилом": значением ним-суммы для числа N делаем наименьшее из чисел, не встречающихся среди тех ним-сумм, которые можно получить из числа N по правилам игры "удаление цифр".

Задача 3

Как вы думаете, почему для этой хитроумной операции я использую термин "ним-сумма", который в обыкновенном ниме определялся совершенно иначе?

Не отвлекаясь на решение этой задачи, посмотрим на результат применения описанного правила к двузначным числам:

вдоль диагонали таблички аккуратно выстроились нолики. Это значит, что все двузначные числа с равными цифрами являются безопасными.

Задача 4

Исследуйте трехзначные числа в этой игре. Попробуйте сформулировать выигрышную стратегию в общем случае (для многозначных чисел) или хотя бы написать программу, которая бы умела играть в "удаление чисел" и выигрывала при этом у противника-человека.

Пишите письма, заходите на WWW-страничку.