Жак Арсак - Программирование игр и головоломок
1, 4, 5, или в двоичной записи 001 100 101
Опять в каждом разряде наши три числа имеют либо 0, либо две цифры 1. Я разобрал достаточно случаев, чтобы подвести вас к результату К. Бутона (1902): положение является выигрывающим, если в каждом двоичном разряде суммарное число 1 двоичных представлений числа спичек в каждой кучке четно.
Совершенно очевидно, что нужно совершить прыжок для перехода от случая двух куч или первых примеров в случае трех куч к Наиболее общему случаю. Тут требуется выдумка или изобретение. Следует, иметь мужество признать, что некоторые люди имеют настоящий талант изобретать или открывать то, что совершенно не очевидно, и не всегда можно потом сказать: да никакой заслуги в этом нет, это было очевидно. Нет, это остается тайной, и преподавателя раздражает, если он оказывается вынужден давать результат, который нельзя легко «переоткрыть».
Назовем Ним-суммой двух целых чисел p и q число, которое вычисляется следующим образом:
p и q записываются в двоичной системе;
сложение выполняется поразрядно, по следующему правилу:
0 + 0 = 0, 0 + 1 = 1 + 0 = 1, 1 + 1 = 0
(сложение без переноса в следующий разряд).
Рассмотрим игру, образованную объединением n независимых игр, каждая со своими собственными правилами. Игра проходит в кучке 1 но правилам R1, в кучке 2 — по правилам R2, … в кучке n — по правилам Rn. В каждой кучке мы располагаем числом Спрага-Грюнди, зависящим от числа спичек в этой кучке. Число Спрага-Грюнди есть Ним-сумма чисел Спрага-Грюнди в каждой кучке…[22] Красиво, не правда ли?
Обратимся к программированию обычной игры города Нима (одно и то же правило для всех кучек: можно брать столько спичек, сколько пожелаешь, но не меньше одной). Вам нужно вычислить Ним-сумму данной ситуации. Если она равна нулю, то у вас нет шансов: ситуацию придется изменить и она перестанет быть выигрывающей. Вы можете, например, взять одну спичку из самой большой кучи: это — способ замедлить конец, и вы всегда можете ожидать, что ваш противник допустит ошибку…
Если же эта сумма не равна нулю, то это в точности означает, что есть разряды, в которых при двоичном представлении единицы встречаются нечетное число раз. Рассмотрим крайний левый из таких разрядов. Нужно уменьшить число единиц в этом разряде. Выберите кучку, содержащую единицу в этом разряде (все равно какую: взять ли самую большую, первую или последнюю…). Нужно уменьшить эту кучку на «эту» единицу. Кроме того, в любом другом (расположенном правее) разряде, где стоит нечетное число единиц, нужно
если в данной кучке в этом разряде стоит 1, удалить ее;
если в данной кучке в этом разряде стоит 0, заменить его на 1.
Это дает вам новое число спичек в этой кучке.
Я видел в некоторых книгах программы для игры Нима, в которых после обнаружения ситуации с ненулевой Ним- суммой испытывались все возможные конфигурации, чтобы найти конфигурацию с нулевой Ним-суммой. Над кем они смеются?
В игре Нима вам нужно для каждого хода, делаемого компьютером, получить двоичное представление числа спичек в каждой кучке. Вам следует решить, будете ли вы пересчитывать его при каждом ходе или вы будете сохранять различные представления, так как имея единственное представление, вы после каждого хода должны изменять его…
Я полагаю, что вы знаете, как получать двоичное представление числа, Пусть
n = ap2p + ap−12p−1 + . .. + a222 + a12 + а0.
Если разделить n на 2, вы получаете в остатке а0, крайнюю справа цифру двоичного представления, а частное
ap2p−1 + ap−12p-2 + . .. + a22 + a1,
которое также является двоичной записью целого числа, получаемой из предыдущей записи вычеркиванием ее крайней правой цифры. По индукции (или, что то же самое, рекурсивно или итеративно) вы получите все двоичные цифры числа n справа налево.
Восстановление значения числа, исходя из двоичных цифр, производится в обратном порядке, слева направо, Сначала вы вычисляете
x0 = ap,
x1 = 2x0 + ap−1 = 2ap + ap−1,
x2 = 2x1 + ap-2 = ap22 + ap−12 + ap-2,
и т. д. Последнее x есть искомое значение,
Игра 20.
Об этой игре я вам больше ничего не скажу. Совершенно необходимо, чтобы вы хотя бы время от времени работали, Впрочем, если я вам ничего не говорю, то дело, вероятно, в том, что я вам уже достаточно рассказал. Это — новая головоломка: выясните, почему у меня нет нужды что- либо вам еще говорить…
Игра 21.
Не протестуйте, я вам помогу… Что бы вы без меня делали? Но кстати, нужно быть честным — я был вдохновлен книгой Роуза Болла [BAL].
В начале игры у вас одна-единственная строка: Спраг-Грюнди… По прошествии некоторого времени она разбивается на много строк, и связанное с ними число Спрага-Грюнди есть Ним-сумма чисел Спрага-Грюнди для каждой строки. Следовательно, нужно вычислить числа Спрага-Грюнди для одной строки, и этого будет достаточно, Вот начало:
0 SG(0) = 0
Из 1 вы достигаете 0: SG(1) = 1.
Из 2 вы достигаете либо 1, либо 0. Поэтому SG(2) — наименьшее целое неотрицательное, отличное от 0 и 1; следовательно, SG(2) = 2.
Исходя из 3, вы можете получить либо одну строку с 2 спичками (SG = 2), либо одну строку с одной спичкой (SG = 1), либо две строки по одной спичке в каждой (удалив среднюю спичку). Но число SG(1, 1) есть Ним-сумма 1 в 1 и потому равно нулю. Следовательно, SG(3) равно трем. Таким же образом вы находите
0 1 2 3 1 4 3 2 1 4 2 6 4 1
Р К. Ги доказал, что начиная с 71, эта последовательность становится периодической с периодом 12. Я не представляю себе, для чего это может быть вам нужно — разве что, если это доставит вам удовольствие, чтобы передоказать его.
Задайте компьютеру таблицу первых чисел Спрага-Грюнди, снабдите его Ним-суммой. Остальное просто.
Игра 22.
Каждая вершина может быть связана с 5 другими, что создает 6 × 5 = 30 связей. Но каждая из них считается дважды (связь между A и B и между B и A). Поэтому есть 15 отрезков, которые нужно провести. Если игра полностью сыграна и все пути пройдены, то у одного из игроков на чертеже должно быть 8 отрезков (у того, который начинает). Они связывают 16 вершин, и поскольку в игре участвует только 6 вершин, то имеется хотя бы одна вершина, из которой выходят три отрезка. Пусть B, C и D — достигаемые этими отрезками вершины (см. рис. 36). Либо этот игрок прошел один из путей связывающих эти вершины, и тогда он проиграл. Либо он ни одного из них не провел, и тогда их провел его противник и противник проиграл…
Может оказаться, что проведено 14 отрезков, не образующих треугольников (как показано на рис. 37).
В этой позиции можно быть уверенным, что кто начинал, тот и проиграет, поскольку нет возможности свести партию вничью. Число возможных комбинаций очень велико, и вы не можете ожидать, что компьютер перепробует все возможные комбинации, прежде чем принять решение. Нужно отказаться от комбинаторных соображений и играть эвристически. Первый ход, если его делает компьютер, не важен: все прямые равноценны. После этого у компьютера остается не более 14 возможных линий, и он их все исследует. Каждой из них он сопоставляет вес: О, если эта линия завершает треугольник из его линия, и он тем самым проигрывает; 1, если эта линия завершает треугольник для его противника, так как она оставляет противнику шанс проиграть; максимальный вес, если эта линия связывает еще не использованные вершины. Когда все линии испытаны таким образом, компьютер делает ход с наибольшим весом. Его стратегия оценит шкалу весов, которые вы будете выбирать.
Игра 23.
В этой игре вы не можете охарактеризовать ситуации числом спичек, оставшихся в кучке, потому что этого недостаточно; нужно еще знать, сколько спичек только что было взято, так как именно это определяет максимальное число спичек, которые вы можете взять. Поэтому нужно определить ситуацию парой
p: число спичек, оставшихся в кучке,
q: число спичек, которое только что было взято.
Положение 0 является выигрывающим, каково бы ни было число спичек, только что взятых, чтобы достичь этого состояния:
SG(0, q) = 0.
Исходя из 1, мы всегда проигрываем, поскольку обязаны взять единственную оставшуюся спичку:
SG(1, q) = 1.
Если у вас осталось две спички, то всегда можно одну взять и одну оставить, следовательно, SG(2, q) ≠ 1, или можно взять две и закончить игру:
