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

Арсак Жак

Возвращаясь отсюда к предыдущему соотношению, получаем

p'² + q'² = sq² + 4sp² + р² = s(4р² + q²) + p² = p² + q².

Таким

образом, все кончено… Это соотношение гарантирует, что p² + q² является инвариантом цикла. При каждом входе в цикл выполняется соотношение

p² + q^{2 =} a² + b².

При выходе из цикла

p² + q^{2 =} a² + b², причем q < ерs.

Отсюда следует, что

p² = (a² + b²) * (1 - q²/(a² + b²)).

Cpaey получаем, что

p = a² + b²

с относительной ошибкой eps²/(2 * (a² + b²)).

Чтобы получить точность до 10^{– 5}, совершенно ненужно брать eps = 10^{– 5}; более чем достаточно eps = 0.004. Эта программа сходится очень быстро.

3. Игры без стратегии

Игра 13.

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

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

Я не храню положений лис с помощью двух переменных. Я отыскиваю их положение в цепочке, представляющей игру, с помощью функции «положение» языка LSE. Это — существенная деталь. Поиск наиболее длинного взятия я осуществляю итеративно. Я образую две цепочки:

— одна из них содержит список кур, уже взятых при исследовании данного пути (это — последовательность букв взятых кур),

— вторая цепочка содержит дуплеты: положение в игре и рассматриваемое направление (мы осуществляем взятие, исходя из положения x и двигаясь в направлении, обозначенном через i).

Находясь в положении x

и в направлении i я смотрю, есть ли кура на поле x + d[i]. Если ее нет, то в этом направлении никакое взятие невозможно. Если же такая кура есть, то я смотрю, не содержится ли буква этой куры в цепочке уже взятых кур. Если содержится, то в этом направлении ничего не сделаешь. Если же эта кура еще не взята, то я проверяю, действительно ли поле x + 2 * d[i] содержит именно точку — в противном случае никакого взятия нет. Действуя таким образом, я не сталкиваюсь ни с какими трудностями на краях (там есть предохранительная строка, и она не содержит ни одной куры).

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

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

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

Игра 19.

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

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

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