Дополнительные источники информации. Принцип минимакса, реализованный в виде альфа-бета-алгоритма, представляет собой один из подходов, наиболее часто используемых для создания игровых про­грамм

Принцип минимакса, реализованный в виде альфа-бета-алгоритма, представляет собой один из подходов, наиболее часто используемых для создания игровых про­грамм, особенно шахматных. Принцип минимакса был предложен в [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 в области искусственного интеллеш