Этюды для программистов

Развитие темы. Хотя в литературе, указанной в библиографии, содержится большое число модификаций альфа-бета-процедуры, мы обсудим здесь только две из них. В первой делается попытка повысить эффективность отсечения. Работа альфа-бета-процедуры основана на том, что хорошие ходы (за обоих игроков) прекращают анализ худших ходов. Поэтому, чем раньше мы будем находить хорошие ходы, тем чаще будут отсекаться плохие. Итак, следует попытаться в первую очередь раскрывать хорошие ходы. В методе с фиксированным упорядочением непосредственные преемники узла упорядочиваются с помощью статической оценочной функций до их анализа. Первым раскрывается узел с наилучшей оценкой. Статическая оценочная функция, как мы надеемся, хорошо предсказывает окончательный результат, получаемый с помощью просмотра, следовательно, эта процедура повышает вероятность того, что сначала будут рассматриваться хорошие ходы. В узлах Мина в первую очередь следует рассматривать преемники с минимальной оценкой.

Еще одно обобщение состоит в изменении статической оценочной функции. Часто используют оценку, равную разности числа всех камней на стороне Макса (в калахе и лунках) и числа камней на стороне Мина. Можно применить любую простую линейную функцию от 14 значений для всех лунок. Наилучшую такую функцию можно выбрать при помощи турнира {это было рассмотрено в гл. 5). Не забывайте, однако, что главным фактором, определяющим силу игрока, является, до всей видимости, глубина просмотра.

Литература

Алеф₀ (Aleph₀). Computer Recreations. Software — Practice and Experience, 1, pp. 297–300, 1971.

В этой статье описывается с внешней стороны программа игры в калах и дается некоторый исторический обзор подобных программ. Имеется полезная библиография.

Белл (Bell R, С). Board and Table Games from Many Civilizations. Oxford University Press, London, 1969.

В гл. 4 Белл описывает несколько вариантов игры манкала. Книга представляет интерес для широкого круга читателей благодаря обширным сведениям об играх и об истории культуры.

Нильсон (Nilsson N. J.). Problem-Solving Methods in Artificial Intelligence. McGraw-Hill, New York, NY, 1971. [Имеется перевод: Нильсон H. Искусственный интеллект. Методы поиска решений. — М.: Мир, 1973.]

Книга Нильсона, вероятно, наилучшее введение в эту дисциплину. В гл. 6 очень понятно разобраны минимаксные методы. Даются ценные рекомендации по дальнейшему чтению.

Слэйгл (Slagle J.R.). Artificial Intelligence: The Heuristic Programming Approach. McGraw-Hill, New York, NY, 1971. [Имеется перевод: Слэйгл Дж. Искусственный интеллект. Подход на основе эвристического программирования. — М.: Мир, 1973.]

Слэйгл также дает хороший обзор области искусственного интеллекта. Он экспериментировал с калахом, и поэтому в книге приводится ряд подробностей об этой игре.

* «Наука и жизнь», № 12, 1971.

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

15. Проще простого, или Поиск узоров из простых чисел

Всякий, кто изучает простые числа, бывает очарован ими и одновременно ощущает собственное бессилие. Определение простых чисел так просто и очевидно; найти очередное простое число так легко; разложение на простые сомножители — такое естественное действие. Почему же тогда простые числа столь упорно сопротивляются нашим попыткам постичь порядок и закономерности их расположения? Может быть, в них вообще нет порядка, или же мы так слепы, что не видим его?

Какой-то порядок в простых числах, несомненно, есть. Простые числа можно отсеять от составных решетом Эратосфена. Начнем с того, что 2 — простое число. Теперь выбросим все большие четные числа (делящиеся на 2). Первое из уцелевших за двойкой чисел, 3, также должно быть простым. Удалим все его кратные; останется 5. После удаления кратных пяти останется 7. Будем продолжать в том же духе; все числа, прошедшие через решето, будут простыми. Эта регулярная, хотя и медленная процедура находит все простые числа. Мы знаем, кроме того, что при n, стремящемся к бесконечности, отношение количества простых чисел к составным среди первых целых чисел приближается к ln n/n[21]. К сожалению, этот предел чисто статистический и не помогает при нахождении простых чисел.

Оказывается, что все известные методы построения таблицы простых чисел — не что иное, как вариации унылого метода решета. Эйлер придумал формулу x² + x + 41; для всех x от нуля до 39 эта формула дает простые числа. Однако никакая полиномиальная формула не может давать подряд бесконечный ряд простых чисел, и функция Эйлера терпит фиаско при х = 40. Другие известные функции дают длинные ряды простых чисел, но ни одна не дает сплошь простые. Исследователи проанализировали множество целочисленных функций, однако до сих пор не удалось увидеть закономерность.