Программирование игр и головоломок

Из 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, или можно взять две и закончить игру:

SG(2, q) = 2.

Начиная с трех, выбор меняется.

Для 3, 1 ваш противник может взять 1 и оставить пару 2, 1, следовательно, SG(3, 1) ? 2, либо взять 2 и оставить пару 1, 2, так что SG(3, 1) ? 1. Но большее количество изымать нельзя. Наименьшее неотрицательное целое, отличное от 1 и 2, есть 0:

SG(3, 1) = 0.

Если вы оставляете 3, взяв больше, чем одну спичку, то противник может взять и 3, достигая 0 с SG (0, 3) = 0, и, следовательно,

SG(3, q > 1) = 3.

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

Игра 24.

Я много раз излагал нижеследующее различным программистам и каждый раз оставался в недоумении, видя, что они не считают это «очевидным».

Вы играете в «Гениального отгадчика», вы ищете неизвестную комбинацию; чтобы сделать это, вы предлагаете комбинации c₁, c₂, …, c_k. Для каждой из них вы получаете ответ о числе белых и черных шашек:

б₁, ч₁; б₂, ч₂; …; 6_k, ч_k.

Следующая предлагаемая комбинация должна быть такой, которая при сравнении с c₁ дает ч₁ черных и б₁ белых шашек; …; при сравнении с c_k она должна давать ч_k черных и б_k белых шашек. Почему? Вы ищете неизвестную комбинацию. Но эта комбинация дает при сравнении с комбинацией c_i именно ч_i черных и б_i белых шашек. Бесполезно искать решение вне множества комбинаций, обладающих этим свойством: там его не может быть[23] .

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

Так как возможных комбинаций много, то нужно попытаться не перебирать их все заново при каждой следующей попытке. Вы можете, например, начать с первой позиции новой комбинации. Вы присваиваете ей первый цвет, а затем смотрите, сколько черных шашек он образует с уже испытанными комбинациями. Если он дает черную шашку с комбинацией, с которой ее не следует давать, то этот цвет нужно отбросить. Когда вы уже нашли подходящий цвет для этой позиции, переходите к следующей. Она может дать вам слишком много черных шашек, и это событие очень даже вероятно. Мало таких комбинаций, которые черных шашек не дают совсем, и больше таких, которые дают не более одной. То, что было зафиксировано для первого цвета, не может быть использовано для второго, Но заметьте, что у вас есть и другой случай для отбрасывания: если нужно получить три черных шашки при сравнении с некоторой комбинацией и если первая позиция никакого вклада не вносит, то необходимо, чтобы вторая позиция вносила свой вклад (предполагая, что есть 4 позиции). Действуя таким образом, вы достигаете в конце концов комбинации с правильным числом черных шашек. Тогда нужно проверить белые. Если они принимают нужные значения для всех предложенных комбинаций, то у вас готово новое предложение, и вы получите либо успех, либо новые элементы для сравнения.

Если испытание комбинации потерпело неудачу, то вы переходите к следующей, начиная, если это