Программирование на языке Пролог для искусственного интеллекта

% Процедуры для отображения позиций
отобр( Поз) :-
 nl,
 коорд( Y), nl,
 коорд( X),
 печ_фиг( X : Y, Поз),
 fail.
отобр( Поз) :-
 чей_ход( Поз, ЧХ), глуб( Поз, Г),
 nl, write( 'ЧейХод='), write( ЧХ),
 write( 'Глубина='), write( Г), nl.
печ_фиг( Клетка, Поз):-
 бк( Поз, Клетка), !, write( 'Б');
 бл( Поз, Клетка), !, write( 'Л');
 чк( Поз, Клетка), !, write( 'Ч');
 write( '.').
показать_ход( Ход) :-
 nl, write( Ход), nl.

Рис. 15.10. Библиотека предикатов для окончания 'король и ладья против короля'.

Проект

Рассмотрите какой-нибудь другой простой эндшпиль, например 'король и пешка против короля', и напишите для него программу на языке AL0 (вместе с определениями соответствующих предикатов).

Резюме

• Игры двух лиц поддаются формальному представлению в виде И/ИЛИ-графов. Поэтому процедуры поиска в И/ИЛИ-графах применимы для поиска в игровых деревьях.

• Простой алгоритм поиска в глубину в игровых деревьях легко программируется, но для игр, представляющих интерес, он не эффективен. Более реалистичный подход — минимаксный принцип в сочетании с оценочной функцией и поиском, ограниченным по глубине.

• Альфа-бета алгоритм является эффективной реализацией минимаксного принципа. Эффективность альфа-бета алгоритма зависит от порядка, в котором просматриваются варианты ходов. Применение альфа-бета алгоритма приводит, в лучшем случае, к уменьшению коэффициента ветвления дерева поиска, соответствующему извлечению из него квадратного корня.

• В альфа-бета алгоритм можно внести ряд усовершенствований. Среди них: продолжение поиска за пределы ограничения по глубине вплоть до спокойных позиций, последовательное углубление и эвристическое отсечение ветвей.

• Численная оценка позиций является весьма ограниченной формой представления знаний о конкретной игре. Более богатый по своим возможностям метод представления знаний должен предусматривать внесение в программу знаний о типовых ситуациях. Язык Советов (Advice Language) реализует такой подход. На этом языке знания представляются в терминах целей и средств для их достижения.

• В данной главе мы составили следующие программы: программная реализация минимаксного принципа и альфа-бета процедуры, интерпретатор языка AL0 и таблица советов для окончания 'король и ладья против короля'.

• Были введены и обсуждены следующие понятия:

  игры двух лиц с полной информацией

  игровые деревья

  оценочная функция, минимаксный принцип

  статические оценки, рабочие оценки

  альфа-бета алгоритм

  последовательное углубление,

  эвристическое отсечение,

  эвристики для обнаружения спокойных позиций

Языки Советов

  цели, ограничения, элементарные советы,

  таблица советов

Литература

Минимаксный принцип, реализованный в форме альфа-бета алгоритма, — это наиболее популярный метод в игровом программировании. Особенно часто он применяется в шахматных программах. Минимаксный принцип был впервые предложен Шенноном (Shannon 1950). Возникновение и становление альфа-бета алгоритма имеет довольно запутанную историю. Несколько исследователей независимо друг от друга открыли либо реализовали этот метод полностью или частично. Эта интересная история описана в статье Knuth and Moore (1978). Там же приводится более компактная формулировка альфа-бета алгоритма, использующая вместо минимаксного принципа принцип 'него-макса' ('neg-max' principle), и приводится математический анализ производительности алгоритма. Наиболее полный обзор различных минимаксных алгоритмов вместе с их теоретическим анализом содержится в книге Pearl (1984). Существует еще один интересный вопрос, относящийся к минимаксному принципу. Мы знаем, что статическим оценкам следует доверять только до некоторой степени. Можно ли считать, что рабочие оценки являются более надежными, чем исходные статические оценки, из которых они получены? В книге Pearl (1984) собран ряд математических результатов, имеющих отношение к ответу на этот вопрос. Приведенные в этой книге результаты, касающиеся распространения ошибок по минимаксному дереву, объясняют, в каких случаях и почему минимаксный принцип оказывается полезным.

Сборник статей Bramer (1983) охватывает несколько аспектов игрового программирования. Frey (1983) — хороший сборник статей по шахматным программам. Текущие разработки в области машинных шахмат регулярно освещаются в серии Advances in Computer Chess и в журнале ICCA.

Метод Языка Советов, позволяющий использовать знания о типовых ситуациях, был предложен Д. Мики. Дальнейшее развитие этого метода отражено в Bratko and Michi (1980 a, b) и Bratko (1982, 1984, 1985). Программа для игры в эндшпиле 'король и ладья против короля', описанная в этой главе, совпадает с точностью до незначительных модификаций с таблицей советов, корректность которой была математически доказана в статье Bratko (1978). Ван Эмден также запрограммировал эту таблицу советов на Прологе (van Emden 1982).

Среди других интересных экспериментов в области машинных шахмат, преследующих цель повысить эффективность знаний (а не перебора), следует отметить Berliner (1977), Pitrat (1977) и Wilkins (1980).

Advances in Computer Chess Series (M.R.B. Clarke, ed). Edinburgh University Press (Vols. 1-2), Pergamon Press (Vol. 3).

Berliner M. A. (1977); A representation and some mechanisms for a problem solving chess program. In: Advances in Computer Chess 1 (M.R.B. Clarke, ed). Edinburgh University Press.

Bramer M. A; (1983, ed). Computer Game Playing: Theory and Practice. Ellis Horwood and John Wiley.

Bratko I. (1978) Proving correctness of strategies in the AL1 assertional language. Information