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

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

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

Игра 25.

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

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

Игра 26.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5. Стратегия без игры (выигрывающие стратегии)

Игра 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)

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

Но еще более удивительно изучение «итеративной» стратегии для этой игры, т, е. последовательности ходов, приводящих к выигрышу. Рассмотрим игру НАДЕВАТЬ. Вы увидите, что первый ход предопределен. Используйте тот факт, что ход не должен разрушать то, что было сделано на предыдущем ходе. Вы установите, что

— вы делаете первой шашкой один ход из двух,

— остальные ходы полностью определены,

так что в игре НАДЕВАТЬ нет никакого выбора. Она полностью определена на каждом ходе: делайте единственно возможный не глупый ход…

Для игры СНИМАТЬ есть два способа начать игру:

— удалить сначала шашку 1 (это возможно всегда),

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

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

Игра 28.

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

Игра 29.

Используйте индукцию или ее двоюродную сестру рекурсию. Если у вас на вашем компьютере