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

( Чу < Лу, СторонаY is Лу - 1;

Чу > Лу, СторонаY is 8 - Лу ),

Пр is СторонаХ * СторонаY, !;

Пр = 64. % Ладья и черный король на одной линии

кк( _..Б..Лх : Лу.. Чх : Чу.._, Кх : Ку) :-

% Критическая клетка

( Чх < Лх, !, Кх is Лх - 1; Кх is Лх + 1),

( Чу < Лу, !, Ку is Лу - 1; Ку is Лу + 1).

% Процедуры для отображения позиций

отобр( Поз) :-

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 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.

Knuth D. E. and Moore R. W. (1975). An analysis of alpha-beta pruning. Artificial Intelligence 6: 93-326.

Pearl J. (1984). Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley.

Pitrat J. (1977). A chess combination program which uses plans Artificial Intelligence 8: 275-321.

Shannon C.E. (1950). Programming a computer for playing chess. Philosophical Magazine 41: 256-275. [В сб. Шеннон К. Работы по теории информации и кибернетике. — М.: ИЛ., 1963.]