Жак Арсак - Программирование игр и головоломок
Игра 11.
Никаких особенных трудностей, если не считать тех, которые связаны с рисунком дороги и положением препятствий. У вас много способов представить игру. Если вы используете таблицу, то факт перемещения фигуры очевидно обязывает вас производить сдвиги. Если вы используете цепочки символов, то дело упрощается. Вы можете, например, состыковывать (конкатенировать) различные строчки (вначале — пробелы, 4 знака (точка, звездочка, 0), код окончания строки) в единую строку, которую вы выводите на экран кусок за куском. Чтобы сдвинуть фигуру, вы убираете некоторое количество кусков в начале (определяемое скоростью) и добавляете столько же в конце. Но это неприемлемо, если ваш компьютер не допускает длинных цепочек (счастливы обладатели LSE1).
Чтобы заставить дорогу повернуть, вы изменяете на i число пробелов в начале. Но не выбирайте случайным образом одно из трех чисел: −1, 0, 1. (Технически это легко. Вы выбираете случайным образом число в интервале (0, 1), скажем x, а затем берете целую часть от (3 * x), уменьшенную на 1.) Если вы сделаете так, то дорога останется приблизительно прямой с маленькими колебаниями влево или вправо. Задайте фактор поворота принимающий значения −1, 0 или 1. На каждой новой строке вы увеличиваете на t число пробелов в начале. Чтобы изменить t, вы выбираете случайное число. Вы надаете постоянную величину a. Если случайное число меньше a, то вы уменьшаете t на 1, и если это действие дает вам −2, то вы полагаете t равным 1. Если, напротив, случайное число больше, чем 1 − a, то вы увеличиваете t нa 1 и если получаете 2, то заменяете его на −1. Параметр a вы подберете экспериментально.
Для размещения тяжелых грузовиков вы можете случайным образом выбирать целое число в интервале длины, большей 4. Если оно примет значения 1, 2, 3 или 4, то вы помещаете грузовик в соответствующий ряд, а если оно примет большее значение, то препятствия нет. Чем больше выбранный исходный интервал, тем меньше шансов для появления грузовика. Подберите этот параметр экспериментально.
Игра 12.
Итак, мы покончили с «маленькими играми». Все предыдущие требовали лишь немного умения программировать и немного ловкости. С другой стороны, они требовали большой тщательности, и только хорошие программисты могли сделать из них что-нибудь красивое и приятное. Ну, а в этой игре, по моему мнению, нужно действовать более мощными методами.
Тщательно проанализируйте способ создания комбинации, исходя из 6 шашек. Начало всегда одно и то же.
Вы выбираете две шашки, скажем a и b, и соединяете их одной из операций:
a + b, a − b, a * b, a : b.
Сложение возможно всегда. Что касается вычитания, то с ним дела обстоят так же, если договориться, что мы всегда вычитаем меньшее из большего (это относится к правильному наименованию чисел, или — что то же — к взятию той из двух операций a − b или b — a, которая дает положительный результат). Заметим, однако, что если a = b, то знак «−» выбирать нельзя.
a * b можно вычислять только тогда, когда ни один из двух сомножителей не равен 1.
a : b ориентировано (как и вычитание). Число b не должно быть равно 1. Остаток при делении должен быть нулевым.
Все это не очень трудно запрограммировать. Вы случайным образом выбираете две шашки. Затем вы случайным образом выбираете знак операции, а если его нельзя использовать — вы повторяете розыгрыш знака. В конце концов вы всегда получите хороший знак…
Теперь вы получили промежуточный результат. Вы можете решить остановиться, а затем выбрать случайным образом недостающие шашки, которые не участвовали в счете:
7 * 75 = 525 8 3 1 10;
вы выводите на экран
1 3 7 8 10 75 найдено: 525.
Вы можете выбрать новую шашку и скомбинировать ее с предыдущим результатом
525 − 8 = 517,
Вы снова получите промежуточный результат.
Вы можете выбрать две шашки и скомбинировать их:
3 * 7 = 21.
Тогда вы получите два промежуточных результата:
7 * 75 = 525; 3 * 7 = 21
Если у вас два промежуточных результата, то появляется много возможностей:
— все 6 шашек уже выбраны. Вы комбинируете между собой два промежуточных результата и получаете вашу окончательную комбинацию;
— даже если не все 6 шашек использованы, вы можете скомбинировать между собой два промежуточных результата и снова получить один-единственный результат.
Но вы можете также выбрать новую шашку и скомбинировать ее с одним из двух промежуточных результатов. Вы снова получите два промежуточных результата.
Таким образом, вы получаете то, что называется конечным автоматом. Есть четыре возможных состояния:
начальное состояние, состояние ОДИН, в котором у вас есть один (и притом единственный) промежуточный результат.
состояние ДВА, в котором у вас есть два промежуточных результата,
конечное состояние, в котором у вас есть результат, который вы рассматриваете как достигнутую цель. В вычислениях участвуют три операции.
Т2: выбрать случайным образом две шашки и соединить их случайным образом выбранным знаком, чтобы получить промежуточный результат;
Т1: случайным образом выбрать шашку и соединить ее случайным знаком с промежуточным результатом;
Т0: соединить два промежуточных результата между собой случайным образом выбранным знаком.
Рисунок 35 дает граф этого автомата, где стрелки показывают операции, которые нужно выполнить, чтобы перейти от одного состояния к другому. Ваша программа должна реализовать этот автомат, причем переходы должны выбираться случайным образом, если это возможно.
Вы теперь знаете все. Конечные автоматы часто встречаются в программировании. Запомните этот пример, он имеет очень широкую область применения…
Игра 13.
Проблема наиболее длинного пути взятия является типичной возвратной задачей. Когда лиса находится в некотором положении, нужно испытать 4 возможных направления и для каждого из них увидеть, есть ли курица и свободно ли следующее за ней поле. Это легко!
Если вы не обнаружили никакого возможного взятия, то все закончено.
Если вы обнаружили возможное взятие, то результат есть наиболее длинное взятие, возможное при этом новом исходном положении, увеличенное на 1.
Но вы можете также действовать итеративным способом. Вы делаете первое взятие и продолжаете дальнейшие исследования, исходя из этого поля прибытия. Нужно испытать все возможности. Вы снова получаете, таким образом, тип задач, известный по головоломке 8. Упорядочьте четыре направления перемещения. Вы исходите из некоторого положения с направлением перемещения i = 1.
Если все четыре направления испытаны, то все закончено.
В противном случае вы смотрите, возможно ли взятие в направлении i:
— если невозможно, то вы увеличиваете i на 1 и возвращаетесь для нового цикла;
— если возможно, то вы выполняете это взятие, оказываетесь в новом положении и начинаете заново, исходя из него.
Внимание: нужно иметь возможность отменять сделанные вами взятия, потому что они происходят в рамках исследования… Это требует некоторой ловкости. По этой причине рассматриваемая игра — не из самых легких.
Остальное вы исследуете совершенно самостоятельно.
Игра 14.
Ничего нового с точки зрения программирования, за исключением того, что нужно исследовать восемь направлений перемещения вместо четырех.
4. Игры со стратегией
Игра 16. Числа Спрага-Грюнди
В большинстве нижеследующих игр два игрока делают ходы по очереди, и выигрывает тот, кто достигает некоторой намеченной в начале игры позиции. В той игре, которую мы обсуждаем сейчас, позиция может быть полностью охарактеризована числом оставшихся спичек, и выигрывающая позиция соответствует числу спичек, равному нулю. Спраг и Грюнди предложили (соответственно в 1936 и 1939 годах) связывать с каждой игровой позицией неотрицательное целое число следующим образом:
— выигрывающей позиции вы сопоставляете 0;
— данной игровой позиции вы сопоставляете наименьшее неотрицательное целое, отличающееся от чисел, связанных с позициями, которые могут быть достигнуты, исходя из данной.
Образуем числа Спрага-Грюнди для этой игры.
Позиции 0 сопоставляется число 0, SG (0) = 0.
Исходя из 1, можно получить 0 (поскольку мы имеем право удалить одну спичку[19]. Следовательно, SG(1) — наименьшее неотрицательное целое, отличное от 0, или SG(1) = 1. Исходя из 2, можно получить 1 и 0. Следовательно, SG(2) — наименьшее неотрицательное целое, отличное от 0 и 1, поэтому SG(2) = 2.
Так как можно удалять спички вплоть до 6, то точно так же имеем
