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

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

Может случиться, что используемый вами язык предоставляет эту возможность непосредственно в виде одной из конструкций языка.

Так, на LSE команда ALE(x) дает число, лежащее в интервале (0, 1), значение которого зависит от x, но непредвиденным образом и, кроме того, не специфицированным в языке: значение будет различным на разных машинах. Если вы трижды зададите один и тот же вопрос

вы каждый раз получите один и тот же ответ, но между ALE(0.1) и ALE(0.2) нет простого соотношения.

На Бейсике функция RND играет ту же самую роль. Она порождает непредсказуемую последовательность, значения которой зависят только от начального числа — оно одно и то же для данного компьютера. Инструкция RANDOM дает случайное число и ставит его начальным элементом последовательности, что позволяет порождать различные последовательности.

Может быть, интересно посмотреть, как можно строить подобные последовательности. Вот метод, предложенный А. Энгелем [ENG]. Если x — число между 0 и 1, то следующий за x элемент последовательности есть

дробная часть ((x + 3.14159)⁸)

Конечно, восьмая степень вычисляется тремя последовательными возведениями в квадрат! Она дает число между 9488 (для x = 0) и 86564. Очень небольшое изменение x вызывает сильное изменение (x + π)⁸, и, в частности, оно может перейти через ближайшее целое, так что новое значение (дробная часть результата) может оказаться меньше предыдущей.

Возьмем, например, x = 0.52000; тогда

(x + 3.14159)⁸ = 32311.5437

так что за 0.5200 следует 0.5437.

Но для x = 0.52005 имеем

(x + 3.14159)⁸ = 32315.0736

и за 0.52005 следует 0.0736.

Так как мы берем дробную часть, то полученное число, разумеется, лежит между 0 и 1.

Упражнение 1. Поведение последовательности.

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

Составьте программу для проверки зтого утверждения. Начальное значение может, например, вводиться в начале каждого вычисления.

Упражнение 2. Поиск других последовательностей.

Число π, использованное при вычислении наших последовательностей, не обладает никаким специальным свойством, и можно спросить себя, действительно ли выбор этого числа является наилучшим возможным. Числа (x + π)⁸ довольно велики, а берем мы от них только дробную часть. При этом мы отбрасываем значащие цифры целой части, и — поскольку вычисления на компьютере проводятся с фиксированным количеством значащих цифр — на дробную часть остается относительно небольшое количество цифр. Предположим, что числа представляются с помощью 24 двоичных цифр. Нужно 14 двоичных цифр, чтобы записать 9488, так как

2¹³ = 8192 < 9488 < 2¹⁴ = 16384

и 17 цифр, чтобы записать 86564, так что остается лишь от 7 до 10 двоичных цифр на дробную часть.

Используя (x + a)⁸ вместо (x + π)⁸ с меньшим значением a, можно ожидать сохранения большего количества значащих цифр для дробной части. Но нельзя взять a слишком близко к 1, так как тогда распределение чисел в интервале (0, 1) окажется плохим. Можете ли вы объяснить, почему?

Например, почему нельзя взять a = ⁸√2?

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

— постоянной а,

— начального значения последовательности.

На своем микрокомпьютере я выяснил, что а = 1.226 дает достаточно хорошие результаты. Но это наблюдение может меняться от машины к машине, так как все это очень чувствительно к способу, которым осуществляются умножения; в последней двоичной цифре результата умножения есть неопределенность, существенно влияющая на рассматриваемый процесс.

Азартные игры

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

Упражнение 3. «Орел» или «решка».

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

— она спрашивает вас, что вы загадали, «орла» или «решку», и читает ваш ответ;

— она порождает случайное число и затем сообщает вам, выиграли вы или проиграли.

Единственная трудность; генератор случайных чисел дает вам, быть может, число, содержащееся между 0 и 1 (это так в случае функции ALE языка LSE и для генератора из разд. 1.2. Имеются противоречивые сведения о языке Бейсик, возможности которого существенно меняются от машины к машине). Следовательно, нужно перейти от вещественного числа в интервале 0 : 1 к чему-либо принимающему не более двух значений, например 0 и 1. Вы сопоставляете по своему усмотрению «орла» одному из них, а «решку» — другому.

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

Сделайте программу, реализующую большое число испытаний, и подсчитайте число выпаданий орла.

Упражнение 4. Игральные кости.

Вместо игры в «орла» или «решку» заставьте компьютер играть в кости. Напишите программу, симулирующую большое число выбрасываний двух костей, и подсчитайте, сколько раз будет выпадать каждая комбинация от 2 до 12. Знаете ли вы, сколько раз должна выпасть каждая из них, если генератор случайных чисел идеален, а число бросаний действительно велико?

Перед вами — та же задача, что и в предыдущем упражнении: перейти от некоторого числа в интервале (0, 1) к целому числу от 1 до 6 включительно. Но если вы знаете, как сделать это для 2, то вы сможете сделать и для 6…

Игра 1. Фальшивые кости.

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

Здесь мошенником пусть будет компьютер. Он играет одной-единственной костью и бросает ее столько раз, сколько вы требуете. Он дает вам число выпаданий единицы, двойки, …, шестерки. Вы сообщаете ему, верите ли вы, что кости поддельные, и если да, то какая грань выпадает чаще других. Компьютер отвечает вам, выиграли вы или проиграли, и случайным образом оценивает ваш выигрыш. Совершенно ясно, что если вы потребуете 40000 бросаний, то у вас будет больше шансов обнаружить истину, чем если вы потребуете 20 бросаний…

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

Вспомогательная задача: выбрать функцию оценки для выигрыша.

? Игра 2. Стратегия для одной игры в кости.

Ж.-К. Бейиф [BAI] предложил игру в кости с двумя игроками. Каждый игрок в свою очередь хода бросает кость столько раз, сколько хочет. Если он не выбрасывает единицу, то он записывает за этот ход сумму выпавших за бросания этого хода очков. Если же он выбрасывает единицу, то он не записывает ничего (и его ход кончается с выбрасыванием единицы). Выигравшим считается тот, кто первым наберет (или превысит) 100 очков.