Принцип минимакса, реализованный в виде альфа-бета-алгоритма, представляет собой один из подходов, наиболее часто используемых для создания игровых программ, особенно шахматных. Принцип минимакса был предложен в [144]. История разработки метода, основанного на использовании альф а-бета-алгоритма, является довольно запутанной, так как несколько исследователей открыли или реализовали этот метод или, по меньшей мере, его часть независимо друг от друга. Эта интересная история описана в [74], где также представлена более компактная формулировка альфа-бета-алгоритма с использованием принципа "neg-max" (в отличие от принципа минимакса, в котором применяются максимальные значения в множестве оценок дочерних узлов на нечетных уровнях и минимальные значения на четных уровнях, принцип "neg-max" предусматривает использование на каждом уровне взятых с обратным знаком (neg) максимальных значений оценок дочерних узлов (max)) вместо минимакса и приведены результаты математического анализа его производительно-
Плэва 22, Ведение игры
сти. Результаты всестороннего исследования нескольких алгоритмов на основе ми-нимакса и их анализа приведены в [118]. В [69] приведем также обзор алгоритмов поиска. В [124] дано описание наиболее современных вариантов алгоритма альфа-бета-поиска. В этой работе рассматривается еще один интересный вопрос, касающийся принципа минимакса: "Если известно, что статическая оценка достоверна лишь в определенной степени, не следует ли из этого, что зафиксированные минимаксные значения являются более достоверными, чем сами статические значения?" В [118] приведен также сборник результатов математического анализа задач, которые относятся к данной проблеме.
Результаты исследования процесса распространения ошибок в деревьях минимакса показывают, когда и почему становится выгодно использовать метод минимаксного опережающего просмотра.
В [11], [54] и [95] приведены сборники статей по ведению на компьютерах сложных игр, особенно шахмат. Современные результаты исследований по компьютерным шахматам публикуются в серии Advances in Computer Chess [1] и в журнале ICCA.
Подход к использованию в шахматах знаний, представленных в виде образцов на языке советов Advice Language, был предложен Мичи (Michie) и получил дальнейшее развитие в [19], а также в [14], [16], [17]. Приведенная в данной главе программа ведения эндшпиля "король и ладья против короля", основанная на использовании таблицы советов, содержит немного измененную таблицу советов, правильность которой доказана математически в [13].
К другим интересным экспериментам в области шахмат, основанным на использовании знаний (в отличие от подходов, опирающихся на применении средств поиска), относятся [7], [123] и [168], Создается впечатление, что в последнее время интерес к разработке шахматных программ, основанных на использовании знаний, угасает, вероятно, из-за их поражения в конкурентной борьбе с шахматными программами, которые основаны главным образом на использовании вычислительных мощностей и отыскивают решение путем перебора. В результате резкого улучшения характеристик компьютерных аппаратных средств, включая шахматные аппаратные средства специального назначения, появилась возможность просматривать до нескольких сотен миллионов позиций в секунду, поэтому отсутствие более тонких знаний компенсируется за счет грубой силы. Кульминацией подхода, основанного на использовании грубой силы, явился проигрыш одного из ведущих шахматистов мира Гарри Каспарова в матче с программой Deep Blue ([65]}. Но этот успех в конкурентной борьбе не позволяет устранить известный недостаток программ, основанных на использовании примитивного перебора: они не способны описать свою игру в концептуальных терминах. Поэтому с точки зрения объяснения результатов, комментирования и обучения остается необходимым подход, основанный на использовании знаний. С другой стороны, создается впечатление, что игра го, если судить по тем же простым показателям успеха в конкурентной борьбе, демонстрирует необходимость использования подхода, основанного на использовании знаний. При составлении программ для этой игры решения, основанные на использовании простого перебора, оказались гораздо менее удачными, чем в шахматах, из-за значительно более высокой комбинаторной сложности.
Часть II. Применение языка Prolog в области искусственного интеллеш
