Глава 14. Ним и так-тикс

Ним - одна из самых старых и занимательных математических игр. Играют в нее вдвоем. Дети используют для игры камешки или клочки бумаги, взрослые предпочитают раскладывать монетки на стойке бара, В наиболее известном варианте нима 12 монет раскладывают в три ряда так, как показано на рис. 84.

Рис. 84. Монеты, разложенные для игры в ним по схеме '3, 4, 5'

Правила нима просты. Игроки по очереди забирают по одной или несколько монет из любого ряда. Выигрывает тот, кто возьмет последнюю монету. Можно играть и наоборот: считать того, кто возьмет последнюю монету, проигравшим. Хороший игрок вскоре обнаружит, что и в том и в другом варианте можно добиться победы, если после его хода останется два одинаковых ряда монеток (то есть с одним и тем же числом монет в каждом ряду), причем в каждом ряду будет находиться более одной монетки. Выиграть можно и в том случае, если в первом ряду останется одна, во втором - две и в третьем - три монетки. Тот, кто открывает игру, наверняка побеждает, если первым ходом он забирает две монетки из верхнего ряда, а затем рационально продолжает игру.

Казалось, что анализ столь простой игры не может привести к каким-либо неожиданностям, однако в начале века было сделало удивительное открытие. Обнаружилось, что ним допускает обобщение на любое число рядов с любым числом фишек в каждом ряду и что с помощью до смешного простой стратегии, используя двоичную систему счисления, любой желающий может стать непобедимым игроком. Полный анализ и доказательство существования оптимальной стратегии впервые опубликовал в 1901 году Чарлз Л. Бутон, профессор математики Гарвардского университета. Бутон и назвал игру "ним" от устаревшей формы английских глаголов "стянуть", "украсть".

Каждую комбинацию фишек в обобщенной игре Бутон назвал либо "опасной", либо "безопасной". Если позиция, создавшаяся после очередного хода игрока, гарантирует ему выигрыш, она называется безопасной; в противном случае позиция называется опасной. Так, при игре в ним по описанной выше схеме "3, 4, 5" (рис. 84) первый игрок окажется в безопасной позиции, взяв две монетки из верхнего ряда. Любую опасную позицию, сделав соответствующий ход, всегда можно превратить в безопасную. Каждая безопасная позиция становится опасной после любого хода. Следовательно, рациональная игра заключается в том, чтобы каждый раз превращать опасную позицию в безопасную.

Чтобы определить, опасна или безопасна данная позиция, число фишек в каждом ряду нужно записать в двоичной системе. Если сумма чисел в каждом столбце (разряде) равна нулю или четна, то позиция безопасна. Если же сумма нечетна хотя бы в одном разряде, то позиция опасна.

В двоичной системе нет ничего сверхъестественного. Это всего лишь способ записи чисел в виде суммы степеней двойки. В помещенной здесь таблице приведена

Двоичные числа для игры в ним

двоичная запись чисел от 1 до 20. Обратите внимание на то, что, двигаясь справа налево, вы каждый раз попадаете в столбец, отвечающий большей степени двойки, чем предыдущий (то есть переходите ко все более старшим двоичным разрядам). Так, двоичная запись 10 101 говорит нам, что к 16 нужно прибавить 4 и 1, а это дает десятичное число 21. Записывая в двоичной системе число фишек в каждом ряду, расставленных по схеме "3, 4, 5", мы получим

Сумма цифр в среднем столбце равна 1 - нечетному числу, что свидетельствует об опасности данной позиции. Поэтому первый игрок может сделать ее безопасной. Как уже объяснялось, именно это он и делает, когда забирает из верхнего ряда две монетки. В результате в верхнем ряду остается лишь 1 монетка (двоичное число также 1) и нечетное число в последовательности сумм чисел по столбцам пропадает. Перепробовав остальные ходы, читатель убедится в том, что только указанный ход может сделать исходную позицию безопасной.

Если в каждом ряду стоит не более 31 фишки, то любую позицию легко проанализировать, использовав в качестве вычислительной машины (работающей в двоичной системе!) пальцы левой руки. Предположим, что в начальной позиции в первом ряду стоит 7, во втором - 13, в третьем - 24 и в четвертом - 30 фишек. Вы должны сделать первый ход. Опасна или безопасна исходная позиция? Поверните левую руку с растопыренными пальцами ладонью к себе. Большой палец будет означать коэффициент при 16, указательный - коэффициент при 8, средний - при 4, безымянный - при 2 и мизинец - коэффициент при 1. Для того чтобы ввести в вашу вычислительную машину число 7, прежде всего нужно загнуть палец, соответствующий наибольшей степени двойки, входящей в 7. Такой степенью является 4, поэтому вы загибаете средний палец. Продолжая двигаться направо, добавляйте степени двойки до тех пор, пока вы в сумме не получите 7. Для этого вам придется загнуть средний, безымянный пальцы и мизинец. Три остальных числа - 13, 24 и 30 - вводятся в вашу вычислительную машину точно так же, но, поскольку вам требуется вычислить сумму чисел, стоящих в столбцах при одной и той же степени двойки, вы, дойдя до согнутого пальца, который вам нужно согнуть еще раз, просто разгибаете его.

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

Итак, вы знаете, что позиция 7, 13, 20, 30 опасна. Как найти ход, превращающий ее в безопасную позицию? На пальцах найти нужный ход довольно трудно, поэтому лучше всего записать четыре двоичных числа в последовательности

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

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

Поскольку в вычислительных машинах используется двоичная система, их нетрудно научить беспрерывной игре в ним. Для этого можно построить и специальную машину. Одним из создателей первой машины такого рода был Эдвард У. Кондон. Машина была запатентована в 1940 году под названием "Ниматрон". Ее построила фирма "Вестингауз". "Ниматрон" экспонировался на Всемирной выставке в Нью-Йорке. Он сыграл 100 000 партий, 90 000 из них выиграл. Большая часть проигрышей была намеренно подстроена экскурсоводом, чтобы доказать скептикам, что и машину можно победить.

В 1941 году существенно усовершенствованную машину для игры в ним спроектировал Рэймонд М. Редхеффер. Емкость памяти у машины Редхеффера была такой же, как и у машины Кондона (четыре ряда с семью фишками в каждом), но "Ниматрон" весил целую тонну и для его. изготовления требовались дорогостоящие реле. Машина же Редхеффера весила всего пять фунтов, для ее изготовления достаточно было четырех вращающихся переключателей. В 1951 году на выставке в Англии и позднее на Торговой ярмарке в Берлине демонстрировался играющий в ним робот "Нимрод". А. М. Тьюринг вспоминал позже, что "Нимрод" приобрел у берлинцев необыкновенную популярность. Посетители выставки совершенно игнорировали даже находившийся в конце помещения бар с бесплатной выпивкой; чтобы утихомиривать и сдерживать толпу, приходилось вызывать полицию. Машина стала особенно популярной после того, как выиграла три партии у тогдашнего министра экономики Эрхарда.

Среди многочисленных полностью изученных вариантов игры в ним особый интерес представляет вариант, предложенный в 1910 году американским математиком Элиакимом X. Муром. Правила этой игры во всем совпадают с правилами обычного нима, с той лишь разницей, что в варианте Мура игроки могут брать из любого ряда не более чем k фишек, где k - некоторое заранее заданное число. Любопытно заметить, что анализ безопасности позиции с помощью двоичных чисел оказывается применимым и в этом случае, если безопасной позицией называть такую, в которой сумма двоичных цифр в каждом столбце делится без остатка на (k + 1).

Другие разновидности игры в ним, по-видимому, не имеют достаточно простой оптимальной стратегии. Наиболее интересным из еще не проанализированных вариантов нима я считаю игру, придуманную около 10 лет назад Питом Хейном (тем самым Питом Хейном, который изобрел гекс).

Рис. 85. Игра так-тикс, придуманная Питом Хейном

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

Обычная ("прямая") игра тривиальна из-за слишком простой стратегии, поэтому в так-тикс следует играть "наоборот" и считать проигравшим того, кто возьмет последнюю фишку. Если игра ведется на квадратной доске с нечетным числом клеток, то первый игрок может одержать победу, взяв фишку, стоящую на центральной клетке, и делая затем ходы, симметричные ходам противника. На доске с четным числом клеток второй игрок выигрывает, делая ходы, симметричные ходам своего противника. Для "обращенной" игры ничего похожего не известно, хотя, как нетрудно показать, на доске размером 3×3 первый игрок выигрывает, взяв либо центральную, либо угловую фишку, либо весь центральный ряд или столбец.

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

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

На первый взгляд кажется, что на поле 4×4 второй игрок обязательно выигрывает, если он все время играет симметрично и меняет эту стратегию только при последнем ходе. Увы, во многих ситуациях симметричная игра не годится. Рассмотрим, например, следующую типичную партию, когда второй игрок избирает симметричную стратегию.

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

Игра так-тикс значительно сложнее, чем это кажется на первый взгляд. До сих пор не известно, кто выигрывает даже на доске 4×4, с которой сняты угловые фишки. В качестве упражнения попробуйте решить две задачи (предложенные Хейном), которые изображены на рис. 86. На каждой доске нужно найти ход, обеспечивающий победу. Может быть, найдется прилежный читатель, который сможет ответить и на более сложный вопрос: кто из игроков всегда может выиграть на доске 4×4 - первый или второй?

Рис. 86. Две задачи из игры в так-тикс

С. Чепмен прислал мне остроумную схему портативной машины для игры в ним, которую он собрал в 1957 году. Она весит 35 унций, ее главный узел состоит из трех многослойных вращающихся переключателей, с помощью которых можно одновременно включать три ряда из четырех возможных. В каждом ряду располагается до десяти фишек. Начиная игру, машина всегда ? одерживает победу. Доказать это можно очень изящно. Запишем число фишек в каждом ряду в двоичной системе так, как делали это в начале главы. Ясно, что в каждом ряду 1 должна стоять либо в столбце с 8, либо в столбце с 4, но не в том и другом столбце одновременно. (Нули не могут стоять в обоих столбцах, ибо тогда число фишек в ряду было бы меньше четырех; единицы также не могут стоять в том и другом столбце одновременно, ибо тогда число фишек было бы больше десяти.) Три единицы (по одной в каждом ряду) можно разместить лишь двумя способами: 1) все три единицы в одном столбце; 2) две единицы в одном столбце и одна в другом. И в первом, и во втором случае сумма цифр в каждом столбце нечетна, поэтому начальная позиция опасна, и машина, открывая игру, заведомо выигрывает.

Многие читатели прислали подробный анализ игры на доске 4×4. Простой стратегии найти не удалось никому, но теперь уже нет никаких сомнений в том, что второй игрок всегда может выиграть как на этой доске, так и на доске 4×4 с заранее снятыми угловыми фишками. Было высказано предположение, что на любой квадратной или прямоугольной доске, имеющей хотя бы одну нечетную сторону, начинающий игру одерживает " победу, если он снимает первым ходом весь средний ряд, а на досках с четными сторонами всегда выигрывает второй игрок. Однако эти предположения до сих пор не доказаны.

Сейчас положение вещей таково: для "так-тикстов", овладевших игрой 4×4, лучше всего начать играть на доске 6×6. Она достаточно мала для того, чтобы игра не слишком затягивалась, и все-таки достаточно велика, чтобы игра была захватывающей и результат ее нельзя было предсказать.

В первой задаче можно было выиграть несколькими разными способами: например, взяв фишки с полей 9-10-11-12 или 4-8-12-16. Для второй задачи выигрыш приносит взятие фишек, стоящих на клетках 9 или 10.