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

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

• Численная оценка позиций является весьма ограниченной формой представления знаний о конкретной игре. Более богатый по своим возможностям метод представления знаний должен предусматривать внесение в программу знаний о типовых ситуациях. Язык Советов (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 Processing Letters 7 : 223-230.

Bratko I. (1982). Knowledge-based problem solving in AL3. In: Machine Intelligence 10 (J. Hayes, D. Michie, J. H. Pao, eds.). Ellis Horwood (an abbreviated version also appears in Bramer 1983).

Bratko I. (1984). Advise and planning in chess end-games. In: Artificial and Human Intelligence (S. Amarel, A. Elithorn, R. Banerji, eds.). North-Holland.

Bratko I. (1985). Symbolic derivation of chess patterns. In: Progress Artificial Intelligence (L. Steels, J. A. Campbell, eds.). Ellis Horwood and John Wiley.

Bratko I. and Michie D. (1980a). A representation of pattern-knowledge in chess end-games. In: Advances in Computer Chess 2 (M.R.B. Clarke, ed). Edinburgh University Press.

Bratko I. and Michie D. (1980b). An advice program for a complex chess programming task. Computer Journal 23: 353-359.

Frey P. W. (1983, ed.). Chess Skill in Man and Machine (second edition). Springer-Verlag.