Программирование игр и головоломок - [47]
В игре Нима вам нужно для каждого хода, делаемого компьютером, получить двоичное представление числа спичек в каждой кучке. Вам следует решить, будете ли вы пересчитывать его при каждом ходе или вы будете сохранять различные представления, так как имея единственное представление, вы после каждого хода должны изменять его…
Я полагаю, что вы знаете, как получать двоичное представление числа, Пусть
n = a>p2>p + a>p−12>p−1 + . .. + a>22>2 + a>12 + а>0.
Если разделить n на 2, вы получаете в остатке а>0, крайнюю справа цифру двоичного представления, а частное
a>p2>p−1 + a>p−12>p-2 + . .. + a>22 + a>1,
которое также является двоичной записью целого числа, получаемой из предыдущей записи вычеркиванием ее крайней правой цифры. По индукции (или, что то же самое, рекурсивно или итеративно) вы получите все двоичные цифры числа n справа налево.
Восстановление значения числа, исходя из двоичных цифр, производится в обратном порядке, слева направо, Сначала вы вычисляете
x>0 = a>p,
x>1 = 2x>0 + a>p−1 = 2a>p + a>p−1,
x>2 = 2x>1 + a>p-2 = a>p2>2 + a>p−12 + a>p>-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, мы всегда проигрываем, поскольку обязаны взять единственную оставшуюся спичку:
