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

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

Еще одно обобщение состоит в изменении статической оценочной функции. Часто используют оценку, равную разности числа всех камней на стороне Макса (в калахе и лунках) и числа камней на стороне Мина. Можно применить любую простую линейную функцию от 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. Другие известные функции дают длинные ряды простых чисел, но ни одна не дает сплошь простые. Исследователи проанализировали множество целочисленных функций, однако до сих пор не удалось увидеть закономерность.

Рисунок 15.1. Числа расположены по спирали против часовой стрелки.

Закономерности проявляются, когда целые числа отображаются на плоскость (или в пространство). Одно из возможных отображений показано на рис. 15.1, где числа располагаются вокруг начальной точки по спирали против часовой стрелки. На рис. 15.2 целые числа заполняют треугольник положительного квадранта. Если достаточно далеко расширить рамки этих рисунков, то станет видно, что простые числа располагаются преимущественно вдоль отдельных прямых (в основном по диагоналям) и совершенно игнорируют другие прямые. Частично этот эффект легко объясним* В обоих расположениях целые числа, попадающие на любую диагональ, даются некоторым квадратичным многочленом. Если многочлен, соответствующий какой-либо прямой, разлагается на рациональные линейные множители, то эта прямая будет содержать одни составные числа. Таким образом, простым числам волей-неволей пришлось облюбовать неприводимые прямые. Однако некоторые неприводимые многочлены изобилуют простыми числами, и изобилие это не оскудевает, несмотря на то что плотность простых чисел среди всех целых медленно стремится к нулю. Иными словами, хотя разложение многочленов объясняет в некоторой степени скученность простых чисел, все же существуют многочлены, более богатые простыми числами, чем предсказывает обычный статистический анализ.

Рисунок 15.2. Числа в треугольнике.

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

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

Длительность исполнения. Одному исполнителю на 2 недели.

Литература

Гарднер (Gardner M). Mathematical Games. Scientific American, pp. 120-126, March 1964. [Имеется перевод: Гарднер М. Математические досуги. — М.: Мир, 1972, с. 410.]

Гаусс (Gauss С. F.). Disquisitiones Arithmeticae. Yale University Press, New Haven, CT, 1965.

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

Штейн, Улам, Уэллс (Stein M. L, Ulam S. M., Wells M. В.). A Visual Display of Some Properties of the Distribution of Primes, American Mathematical Monthly, pp. 516–520, May 1964.