Программирование игр и головоломок - [68]

Если взятие оказывается возможным, я присоединяю его характеристики к обеим цепочкам, продвигаюсь на новую позицию и возобновляю изучение взятий, исходя из этого нового положения. Я не изменяю состояния игры, за исключением того, которое относится к начальному полю отправления лиса (на этом поле лис может оказаться снова. Напротив, из соображений четности мы не можем прийти на поле, занимаемое какой-либо из взятых кур).

Когда оказывается, что мы достигли поля, исходя из которого уже никакое дальнейшее взятие невозможно, я сравниваю длину цепочки взятых кур с наиболее длинной уже сохраняемой цепочкой и выбираю лучшую из них (нужно смотреть и на цепочку дублетов, чтобы осуществить взятие, обновляя состояние игры, как только наиболее длинное взятие будет определено). Затем я отменяю последнее взятие (совершенное в этих двух цепочках) и перехожу к следующему направлению, исходя из последнего положения. Никакой проблемы с временем вычислений на моем микрокомпьютере не возникает, даже наоборот. Часто нужно добавлять замедляющий цикл, чтобы предоставить игроку время увидеть, что происходит…

4. Игры со стратегией

Игра 19.

И здесь тоже решение неединственно. Вот одно из них, хорошо приспособленное к используемой мною машине, на которой деления на 2 не бесплатны (на мой взгляд, выполняются слишком долго). Нам известна верхняя граница числа спичек в каждой кучке, определяемая принятым вами правилом (я взял 4 кучки с по крайней мере 16 спичками). Я рассматриваю двоичные записи числа спичек в кучке, начиная слева. Я задаюсь числом p = 8. Если число больше или равно 8, то оно содержит 1 в крайнем левом из возможных положений. Тогда я вычитаю 8 из этого числа и перехожу к p = 4.

Сначала я определяю крайнюю левую цифру для числа спичек во всех четырех кучках. Из них я удерживаю только две вещи: четность этого числа (переменная q, вначале равная 0, изменяется на 1 — q при каждой встрече с единицей; результат нечетен, если в конце получается q = 1); номер последней встреченной кучки, у которой в данном положении встретилась единица. Я исследую таким образом все положения слева направо, пока не встречаю положение, для которого сумма единиц, стоящих в этом положении, нечетна. Тогда я знаю кучку (ту, номер которой был удержан в памяти), у которой в этом положении стоит именно единица. Я убираю из этой кучки желаемое число спичек, чтобы эта единица исчезла (8, если сейчас изучается крайнее левое положение).

Тогда я аналогичным образом исследую оставшиеся положения, за исключением того, что я больше не трогаю номера кучек, из которых я уже брал спички. Для каждой оставшейся позиции, вплоть до крайней правой, я отыскиваю единицы и, если число единиц нечетно, то я изменяю число спичек в выбранной кучке. Чтобы узнать, нужно ли добавить или уменьшить, я сохраняю их число перед изменением в цикле. Если оно больше р, я вычитаю из него р, а если меньше, то я р добавляю (я ставлю 0 вместо 1 и 1 вместо 0). Все это — очень быстрое вычисление, но оно требует немного больше строк в программе. Так вы легко достигнете цели.

Игра 20.

Я ничего не добавляю, потому что эта игра является вариантом нимской игры. На каждой строке есть пустые поля, играющие ту же роль, что и спички в кучках нимской игры. Единственная разница состоит в том, что игрок может отступать. Если вы можете достичь выигрывающей позиции (такой, что НИМ-сумма пустых полей между игроками на каждой строчке оказывается равной нулю) и если противник отступает одной из своих шашек, увеличивая число пустот на этой строке, то вы на столько же полей продвигаетесь вперед, восстанавливая таким образом предшествующую — и потому выигрывающую — ситуацию. Противник оказывается немного глубже вбитым в свой угол и приблизившимся к своей гибели. Если в какой-то момент все промежуточные пустые поля пропадут, то шашки оказываются рядом друг с другом, и ваш противник может только отступать. А вы за ним следуете…

Игра 22.

Вот шкала весов, предложенная А.-П. де Лоашем в книге Шварца [SCHJ:

0: отрезок замыкает проигрывающий треугольник,

1: отрезок замыкает треугольник, две стороны которого принадлежат моему противнику,

2: отрезок замыкает смешанный треугольник (одна из сторон которого — моя, а другая — моего противника),

3: отрезок соединяет две смешанных вершины (из каждой из них выходит и моя сторона, и сторона моего противника),

4: отрезок соединяет смешанную вершину и вершину, из которой выходит только одна сторона,

5: отрезок соединяет две вершины, каждая из которых принадлежит только одному отрезку, который провел именно я,

6: отрезок соединяет две вершины, каждая из которых принадлежит только одному отрезку, один из которых провел я, а другой — мой противник,

7: отрезок соединяет две вершины, которые не принадлежат проведенным мною отрезкам,

8: отрезок проходит через «чистую» (еще не использованную) вершину,

9: отрезок соединяет чистую вершину с вершиной, не принадлежащей моим отрезкам,

10: отрезок соединяет две чистые вершины.

Можно немного упростить этот список, не увеличивая сколько-нибудь серьезно опасность проиграть.