Программирование игр и головоломок - [36]
Элементарно, мой дорогой Ватсон!
Игра 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 символов, образующих цепочку. На каждом ходе цепочка теряет свой последний символ и получает новый первый символ.
Но можно сделать еще и по-другому. Речь идет об «орле» и «решке». Нам нужно только два различных символа, например, 0 и 1. Эти m символов 0 и 1 могут рассматриваться как цифры числа в двоичной записи. Тогда вам не нужна ни таблица, ни цепочки символов. В соответствии с выбором нужно выполнить либо умножение на 2 (что сводится к одному сложению), либо деление на 2.
Относительные успехи трех наших решений зависят от используемой вами системы. В зависимости от управления, принятого для таблиц и цепочек, в зависимости от искусства программиста, составившего систему интерпретации вашего языка высокого уровня, либо таблица одолевает цепочки, либо наоборот.
В составленной мною системе на языке LSE использованы двоичные числа, дающие несколько лучший результат, чем полученные с помощью цепочки., которые, в свою очередь, дают заметно лучший результат, чем полученный с помощью таблиц.
