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

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

Можете ли вы вычислить число f ( n ) ходов, необходимое для проведения партии в игре с n дисками? Сколько веков потребуется для проведения игры в 50 дисков, если каждый ход делается за секунду?

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

* Игра 32.Рисунок игры.

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

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

Более хитрый способ представляет стержни вертикально либо как последовательность номеров, либо — что еще лучше — если у вас есть графическая система, стилизованным образом, как на рис. 26. Это труднее…

? Игра 33.Итеративная стратегия.

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

??? Игра 34.Игра с 4 стержнями.

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

Найдите способ действовать, минимизируя число ходов, и найдите их необходимое число для малых значений n . Из письма Паскаля Младшего неясно, сколько времени нужно — если каждый ход совершается за секунду — для завершения игры с 4 стержнями и 50 дисками. Вычислите его.

??** Игра 35.Составьте итеративную программу для игры с 4 стержнями.

Если теперь добавить пятый стержень, то нужно все начинать сначала, или результаты, полученные для 4 стержней, допускают немедленную экстраполяцию на случай 5 стержней?

??? Игра 36.Спички Бергсона.

Эта игра была предложена выше (игра 23). Тогда требовалось только дать компьютеру указание, что он должен будет сделать, чтобы выиграть наверняка, если исходить из 50 спичек. Теперь нужно заглянуть глубже и изучить выигрывающую стратегию в полной общности.

Как и во многих играх, есть ситуации, которые позволяют игроку выиграть наверняка (если он их знает), и другие ситуации, исходя из которых выиграть невозможно. Пусть П обозначает ситуацию, благоприятную первому игроку (или предыдущему. П — это первая буква слова «позитивный», как это заметил Роуэ Болл [BAL]). Эта ситуация хороша для меня, если это такая ситуация, которой я достигаю после своего хода. Ситуация Н благоприятна второму, «новому», игроку (неблагоприятна первому, негативна). Она хороша для меня, если это — та ситуация, которую я застаю в момент своей игры. Вся моя стратегия есть переход от ситуации Н в ситуацию П.

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

— из ситуации Н всегда можно достичь ситуации П,

— из ситуации П можно достичь только ситуаций Н,

— выигрывающая ситуация есть ситуация П.

Игра происходит переходами между ситуациями Н и П. Победитель определяется природой — принадлежностью классу Н или П — начальной ситуации и, таким образом, определяется тем, кто начинает.

В игре в спички Бергсона ситуация характеризуется двумя целыми числами p , q :

p — число спичек, оставшихся в куче;

q — число спичек, взятых на предыдущем шаге. Тогда можно взять от 1 до 2 q спичек.