Книга: Программирование игр и головоломок
1. Случайные числа
1. Случайные числа
Упражнение 2.
Нужно изучить поведение дробной части (x + a)8, когда x меняется от 0 до 1. Нарисуйте, хотя бы приближенно, кривую, представляющую эту функцию. Рассмотрите интервал на оси x, в котором значение функции меняется от некоторого целого числа до следующего за ним. Отметьте на кривой точку, в которой ордината равна этому целому, увеличенному на 0,5. Она разбивает область изменения x на два интервала. Равны ли между собой эти две половинки? Если одна из них больше другой — и если это одна и та же половинка для всех интервалов — то у вас больше шансов получать числа, меньшие (или большие, вам будет видно самим), чем 0,5.
Но что касается выбора a, то напомним, что следует избегать соотношения
дробная_часть ((x + a)8) = x,
иначе вы вместо случайной последовательности получите постоянную последовательность. Проверьте числа x = 0, x = 0,5 и x = 1.
Упражнение 4.
Вы располагаете генератором случайных чисел, дающим число, содержащееся между 0 и 1, и вы хотите получить случайным образом число между 1 и 6, включая границы. Тогда остается сказать, что вам нужно различать 6 случаев и приписать каждому из случаев значение одного из этих целых чисел.
Почему не разделить интервал (0, 1) на 6 частей?
Или еще по-другому: почему бы не умножить выше случайное число на 6. Тогда оно окажется в интервале (0, 6), исключая 6. Если вы возьмете целую часть результата, то вы получите целое число от 0 до 5, включая границы, с равными вероятностями для каждого числа… Завершить следует вам, я уже сказал слишком много!
Игра 1.
Если вы знаете, как сделать предыдущее упражнение, то это для вас уже не задача. Нужно подделать кости, иначе говоря — сделать так, чтобы одна из граней выпадала чаще остальных. Это должно означать, таким образом, что вместо того, чтобы делить интервал (0, 1) на 6 равных Частей, нужно взять 5 частей равных между собой, а шестую побольше. Легко! Наиболее простое решение состоит в умножении случайного числа на целое, большее 6, и в присвоении новых значений грани,; которую вы решили предпочесть.
Элементарно, мой дорогой Ватсон!
Игра 2.
Х.-К. Байи упростил задачу, указав две возможные стратегии:
— бросать кость до тех пор, пока не будет достигнута некоторая намеченная заранее сумма (по крайней мере если игрок не будет остановлен по дороге выбрасыванием единицы);
— бросать кость определенное число раз, намеченное заранее.
В первом случае предположим, что уже имеющаяся у вас сумма равна n и что вы собираетесь осуществить еще одно бросание. У вас есть один шанс из 6 получить каждое из следующих шести чисел: 0, n + 2, n + 3, n + 4, n + 5, n + 6. Если вероятный выигрыш не увеличивает полного выигрыша (если среднее из этих чисел меньше n), то играть не следует. Вы должны получить n = 20.
Если вы бросаете кость 6 раз, то — поскольку все грани имеют равные шансы выпасть — вы должны проиграть. Это не слишком строгое рассуждение, но короткое… Если единица вам не выпала, то у вас один шанс из пяти получить числа от 2 до 6, что дает в среднем 4. За 5 ходов получаем 20. Это — еще один способ получить оценку для числа ходов.
Но есть и другие возможные стратегии. Вы можете, в частности, решить останавливаться в зависимости от того, какое из двух событий наступает первым: сумма, большая 19, или число ходов, равное 5.
Используйте ваш компьютер, чтобы произвести соответствующие опыты.
Если вы хотите взглянуть на это с точки зрения искусственного интеллекта, то вы можете также снабдить вашу программу механизмом самообучения. Вы помещаете в вашу программу три упомянутые выше стратегии. Розыгрыш определяет случайным образом ту, которая будет использована в каждой из партий. Вначале все три стратегии имеют равные вероятности. Если выбранная стратегия выигрывает, то вероятность ее применения увеличивается. Если она проигрывает, то ее вероятность уменьшается. Чем больше вы играете, тем чаще компьютер должен выигрывать. После очень большого числа партий полученные частоты применения стратегий скажут вам, какая из них является наилучшей.
Головоломка 1.
Это — нетрудная программа, разве что вы не взяли па себя заботу четко сформулировать задачу. Последовательность целых чисел, порождаемая этой программой, является так называемой возвратной последовательностью, каждый член которой полностью определяется значением предыдущего члена:
ui = f(ui?1),
Сказать, что последовательность ui становится периодической — то же, что сказать, что существует некоторое p, для которого
ui+p = ui
для достаточно больших i. Но если это выполняется для данного i, то
ui+p+1 = f(ui+p) = f(ui) = ui+1
и, следовательно, uj+p = uj для любого j, большего i. Пусть r — наименьший из индексов, для которых ur+p = ur.
От вас не требуют найти число r, нужно найти только число p. Можно предложить два решения:
— если i — достаточно большое число, кратное p, то u2i = ui;
— выберите исходное значение d и длину интервала h. Для любого i от d + 1 до d + h посмотрите, не равно ли соответствующее значение u числу ud. Если равно, то вы нашли период и все закончилось. Если же никакого равенства не получается, то либо d меньше, чем r, либо h меньше p, либо и то, и другое. Попытайтесь сделать то же еще раз с бо?льшими d и h.
Есть много способов реализовать вторую из этих стратегий. По крайней мере в некоторых случаях она быстрее первой.
Головоломка 2.
Совершенно ясно, что вы не можете начинать проводить какие-либо статистические подсчеты до того, как вы реализуете m бросаний. Наш маленький вундеркинд хотел бы сделать единственный цикл, в котором m ? 1 первых ходов подвергаются специальной обработке. Это — совершенно бесполезная сложность. Составьте первый цикл по данным m первым ходам. Затем — второй цикл, проводящий статистику.
Наш маленький вундеркинд совершил и вторую ошибку, для меня еще более необъяснимую: он объединил последовательные ходы в таблицу. Но это совершенно бесполезно. В любой момент единственное, в чем вы нуждаетесь, это в результатах m последних бросаний. С каждым новым бросанием результат наиболее старого из учитывающихся ранее бросаний теряет силу. Поэтому вы можете его упразднить, Если и есть таблица, то ее размер m, а не n!
Но не очевидно, каким образом хранить в таблице m бросаний. Вы можете представить их в виде m символов, образующих цепочку. На каждом ходе цепочка теряет свой последний символ и получает новый первый символ.
Но можно сделать еще и по-другому. Речь идет об «орле» и «решке». Нам нужно только два различных символа, например, 0 и 1. Эти m символов 0 и 1 могут рассматриваться как цифры числа в двоичной записи. Тогда вам не нужна ни таблица, ни цепочки символов. В соответствии с выбором нужно выполнить либо умножение на 2 (что сводится к одному сложению), либо деление на 2.
Относительные успехи трех наших решений зависят от используемой вами системы. В зависимости от управления, принятого для таблиц и цепочек, в зависимости от искусства программиста, составившего систему интерпретации вашего языка высокого уровня, либо таблица одолевает цепочки, либо наоборот.
В составленной мною системе на языке LSE использованы двоичные числа, дающие несколько лучший результат, чем полученные с помощью цепочки., которые, в свою очередь, дают заметно лучший результат, чем полученный с помощью таблиц.
Игра 3.
Единственная трудность в этой программе: перетасовать карты. Я уже упомянул об этом, описывая условия игры. Есть много возможных идей:
— приготовить сначала карточную колоду, затем вытаскивать их из стопки одну за другой. В этом случае у вас будет выбор, как поступать:
либо расположить карты в таблицу в 52 полями, либо создать цепочку ив 52 символов. Но нужно ли это на самом деле? Почему бы не исходить из простой начальной ситуации: упорядоченной таблицы или отсортированной цепочки, затем выбирать элемент этого множества с помощью случайного бросания, вынимать его из множества и повторять процедуру с меньшим количеством элементов.
Если так поступать, то применение таблицы становится тонкой задачей: как изъять элемент из множества?
Его можно изъять «физически». Все элементы, расположенные выше него, спускаются в таблице вниз на одну ступеньку. Это сохраняет порядок оставшихся элементов.
Но нужно ли это? Почему бы, что гораздо проще, не переставить выбранный элемент с последним элементом таблицы в процессе выполнения операции?
Как только мы это обнаружили, становится очевидно, что в перетасовывании карт, исходя из начальной колоды, больше никаких трудностей нет: вы размещаете колоду в упорядоченную таблицу из n карт, вы выбираете случайным образом целое число между 1 и n, вы меняете местами соответствующий элемент с элементом n, затем вы уменьшаете n на единицу и повторяете процедуру.
Элементарно, когда все испробовано!
Игра 4.
Я уже дал все необходимые пояснения, кроме порождения лабиринта. Первую попытку я предпринял со следующим алгоритмом:
— поставить i в начальное положение (правый нижний угол),
— выбрать случайным образом направление перемещения (целое от 1 до 8); если это перемещение невозможно — перейти к следующему перемещению, пока не будет найдено возможное перемещение;
— передвинуть i в соответствии с этим перемещением;
— если i оказался на поле прибытия, то все закончено, в противном случае повторить процедуру.
Опыт показывает, что чаще всего эта программа не останавливается.
Так как есть основное направление перемещения, подлежащее реализации (диагональ игры), то я изменил случайный выбор так, чтобы сделать более частными перемещения влево и вверх или вверх и влево.
Так как у меня еще были и другие задачи, я решил останавливать случайный выбор, когда i оказывается в маленьком прямоугольнике вверху слева. Полученный реестр (сделанный из таблицы или цепочки символов) дает тогда путь, ведущий из каждой из точек этого прямоугольника к полю прибытия.
Остальное просто.
Игра 5.
Эта игра не представляет никаких трудностей. Пусть вы не пытаетесь гарантировать Тони возможность выхода. В программе — никакой стратегии: один ход на два поля, два препятствия на горизонтальной линии на двух свободных полях (вы выбираете клетку случайным образом. Если она или ее соседка справа не свободны, то вы повторяете выбор. Если они свободны — вы их помечаете. Тем хуже для Тони, если он накрыт), два препятствия случайным образом на двух вертикальных полях.
Если вы решили оставить Тони шансы на спасение, действуйте, как в предыдущей программе. Вы случайным образом выбираете путь и обозначаете его так, чтобы никакое препятствие на него сверху не падало. Но вы не выводите на экран этих обозначений.
Оглавление книги
