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

Если вы знаете, как сделать предыдущее упражнение, то это для вас уже не задача. Нужно подделать кости, иначе говоря — сделать так, чтобы одна из граней выпадала чаще остальных. Это должно означать, таким образом, что вместо того, чтобы делить интервал (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.

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

u_i = f(u_i−1),

Сказать, что последовательность u_i становится периодической — то же, что сказать, что существует некоторое p, для которого

u_i+p = u_i

для достаточно больших i. Но если это выполняется для данного i, то

u_i+p+1 = f(u_i+p) = f(u_i) = u_i+1

и, следовательно, u_j+p = u_j для любого j, большего i. Пусть r — наименьший из индексов, для которых u_r+p = u_r.

От вас не требуют найти число r, нужно найти только число p. Можно предложить два решения:

— если i — достаточно большое число, кратное p, то u_2i = u_i;

— выберите исходное значение d и длину интервала h. Для любого i от d + 1 до d + h посмотрите, не равно ли соответствующее значение u числу u_d. Если равно, то вы нашли период и все закончилось. Если же никакого равенства не получается, то либо d меньше, чем r, либо h меньше p, либо и то, и другое. Попытайтесь сделать то же еще раз с бо́льшими d и h.

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

Головоломка 2.

Совершенно ясно, что вы не можете начинать проводить какие-либо статистические подсчеты до того, как вы реализуете m бросаний. Наш маленький вундеркинд хотел бы сделать единственный цикл, в котором m − 1 первых ходов подвергаются специальной обработке. Это — совершенно бесполезная сложность. Составьте первый цикл по данным m первым ходам. Затем — второй цикл, проводящий статистику.

Наш маленький вундеркинд совершил и вторую ошибку, для меня еще более необъяснимую: он объединил последовательные ходы в таблицу. Но это совершенно бесполезно. В любой момент единственное, в чем вы нуждаетесь, это в результатах m последних бросаний. С каждым новым бросанием результат наиболее старого из учитывающихся ранее бросаний теряет силу. Поэтому вы можете его упразднить, Если и есть таблица, то ее размер m, а не n!

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