Чтение онлайн

Чх > Лх, СторонаХ is 8 - Лх ),

( Чу < Лу, Сторона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. Библиотека предикатов для окончания "король и ладья против короля".

Резюме

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

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

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

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

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