Жак Арсак - Программирование игр и головоломок

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

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

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

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

Игра 25.

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

Я предоставляю вам выбор весов…

Игра 26.

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

Чтобы определить веса игрового положения, нужно видеть, принадлежит ли оно отрезку из четырех игровых положений, уже содержащему 3 ваших шашки (тогда именно так и нужно играть: максимальный вес) или 3 шашки противника (максимальный вес минус 1). Если игровое положение находится на пересечении двух отрезков, содержащих по две шашки противника и ничего больше, то оно представляет очень большой интерес для хода. Продолжите этот анализ, и ваша программа будет носить ваш отличительный знак.

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

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

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

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

— либо вы определяете его с помощью программы,

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

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

Остается способ вычисления состояния отрезка. Я принял следующее соглашение:

— поле, ход на которое невозможен, обозначается 0 (нулем);

— поле, ход на которое возможен, обозначается 1.

Так как нужно изучить отрезки, проходящие через игровое поле, то их наименьшее число 1, но может доходить и до 4. Поэтому нужно быть в состоянии выделять среди них сегмент, содержащий игровое поле и шашку +. Следовательно, придадим такой шашке значение 4. Может появиться отрезок, содержащий ·+++ со значением 13, отличающийся от сегмента с игровым полем и шашкой 0.

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

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

Игра 27.

Чтобы найти рекурсивное решение в игре НАДЕВАТЬ, нужно действовать по индукции. Назовем НАДЕВАТЬ( n ) решение, которое помещает n шашек на первоначально пустое игровое поле. Предположим, что мы умеем выполнять задание игры НАДЕВАТЬ для p , меньших n .

Как поставить на место последнюю шашку? Мы не можем ее поставить, если это поле не является следующим за первым полем, занятым шашкой. Следовательно, для ее помещения на место нужно, чтобы в игре участвовала одна-единственная шашка шашка с номером n − 1. С помощью НАДЕВАТЬ( n − 1) можно поставить на место все шашки от 1 до n − 1. Если мы удалим все шашки от 1 до n − 2, то останется только шашка n − 1, можно будет поставить шашку n , а затем снова надеть шашки от 1 до n − 2:

НАДЕВАТЬ( n ) = НАДЕВАТЬ( n − 1);

СНИМАТЬ( n − 2); поместить( n ); НАДЕВАТЬ( n − 2)