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

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

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: отрезок соединяет две чистые вершины.

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

Игра 23.

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

3,1 5,2 8,3 11,1 13,6 16,1 18,2

21,10 24,1 26,2 29,3 32,1

34,16 37,1 39,2 42,3 44,1 47,6 50,1

Игра 24.

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

Для каждой новой комбинации предложение некоторого цвета в некоторой позиции ведет к следующему:

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

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

Поэтому вы можете немедленно остановить испытание с цветом x в положении i, если:

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

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

либо она дает слишком много белых шашек,

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

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

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

Оглавление книги