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

Поэтому если ваш компьютер не допускает функции, дающей стохастическое число, я вижу только одно решение [3] См. предыдущую сноску. — Примеч. ред. : введите сами случайное число в ваш компьютер. Как это сделать? Вот предложение. Вы берете колоду из 52 карт, перетасовываете. Затем вы делите колоду на верхнюю и нижнюю части и берете из нижней части три верхние карты. Небольшая и очень простая программа читает три целых числа x , y , z . В качестве значений этих целых чисел вы задаете численные значения трех выбранных карт, считая туза за 1, валета — за 11, даму — за 12, короля — за 13. Компьютер вычисляет значение

(((x − 1)/13 + у − 1)/13 + z − 1)/13.

Например, если вы достанете, как только что случилось со мной, семерку бубен, десятку червей и еще шестерку бубен, то

x =7 y = 10 z = 6

и компьютер получит 0.440601.

Эго значение не является воистину непредсказуемым. Как только вы достанете карты, вы уже сможете понять порядок величины результата. С другой стороны, таким способом вы не сможете получить более 13³ = 2197 различных чисел. Но этого на самом деле достаточно для приложений, которые мы рассматриваем в этой книге. А если вы и в самом деле хотите получить что-либо непредсказуемое, прочтите следующий раздел.

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

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

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

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

? ALE (0.1)

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

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

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

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

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

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

( x + 3.14159) 8= 32311.5437

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

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

( x + 3.14159) 8= 32315.0736

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

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

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

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

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

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

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

2 13= 8192 < 9488 < 2 14= 16384

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

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

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

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

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

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

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

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

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

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

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

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