Указания исполнителю. Несмотря на многословное описание, сама программа для игры в калах довольно проста. Основную трудность составляет построение структуры данных для представления игровых деревьев и обеспечение должного порядка создания и уничтожения этих деревьев. Вам, вероятно, придется написать свои собственные программы, которые будут выделять пространство для деревьев и собирать освобождающуюся память. Требование эффективности по времени работы накладывает ограничение на глубину просмотра; учитывайте это в программах порождения дерева. Вероятно, имеет смысл обеспечить относительную независимость минимаксной процедуры от остальной части программы, с тем чтобы изменения минимаксной процедуры не влияли на всю программу.
Инструментовка. Здесь мы еще раз встречаемся с задачей, для решения которой требуются, по-видимому, противоречивые свойства языка: мощные структуры данных, удобные управляющие структуры и эффективность выполнения. В этом смысле наиболее удачным языком представляется Паскаль, в особенности если избегать широкого использования его возможностей по выделению и освобождению памяти для данных. Для реализации поиска по дереву сами собой напрашиваются рекурсивные процедуры, но они дороги. Попробуйте применить вместо них средства языка, позволяющие преобразовать рекурсию в итеративный обход структур данных.
Длительность исполнения. Одному исполнителю на 4 недели.
Развитие темы. Хотя в литературе, указанной в библиографии, содержится большое число модификаций альфа-бета-процедуры, мы обсудим здесь только две из них. В первой делается попытка повысить эффективность отсечения. Работа альфа-бета-процедуры основана на том, что хорошие ходы (за обоих игроков) прекращают анализ худших ходов. Поэтому, чем раньше мы будем находить хорошие ходы, тем чаще будут отсекаться плохие. Итак, следует попытаться в первую очередь раскрывать хорошие ходы. В методе с фиксированным упорядочением непосредственные преемники узла упорядочиваются с помощью статической оценочной функций до их анализа. Первым раскрывается узел с наилучшей оценкой. Статическая оценочная функция, как мы надеемся, хорошо предсказывает окончательный результат, получаемый с помощью просмотра, следовательно, эта процедура повышает вероятность того, что сначала будут рассматриваться хорошие ходы. В узлах Мина в первую очередь следует рассматривать преемники с минимальной оценкой.
Еще одно обобщение состоит в изменении статической оценочной функции. Часто используют оценку, равную разности числа всех камней на стороне Макса (в калахе и лунках) и числа камней на стороне Мина. Можно применить любую простую линейную функцию от 14 значений для всех лунок. Наилучшую такую функцию можно выбрать при помощи турнира {это было рассмотрено в гл. 5). Не забывайте, однако, что главным фактором, определяющим силу игрока, является, до всей видимости, глубина просмотра.
Алеф0 (Aleph0). 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.