кк( Поз, КК), % Критическая клетка
манх_расст( БК, КК, Мрасст).
раздел( _..Бх : Бу..Лх : Лу.. Чх : Чу.._ ) :-
упоряд( Бх, Лх, Чх), !;
упоряд( Бу, Лу, Чу).
l_конфиг( _..Б..Л..Ч.._ ) :- % L - конфигурация
манх_расст( Б, Ч, 2),
манх_расст( Л, Ч, 3).
не дальше_от_ладьи( _..Б..Л.._, _..Б1..Л1.._ ) :-
расст( Б, Л, Р),
расст( Б1, Л1, Р1),
Р =< Р1.
простр_больше_2( Поз) :-
простр( Поз, Пр),
Пр > 2.
наш_король_на_краю( _..Х : Y.._ ) :-
% Белый король на краю
( X = 1, !; X = 8, !; Y = 1, !; Y = 8).
король_противника_на_краю( _..Б..Л..Х : Y.._ ) :-
% Черный король на краю
( X = 1, !; X = 8, !; Y = 1, !; Y = 8).
короли_рядом( Поз) :- % Расстояние между королями < 4
бк( Поз, БК), чк( Поз, ЧК),
расст( БК, ЧК, Р),
Р < 4.
потеря_ладьи( _..Б..Л..Л.._ )- % Ладья взята
потеря_ладьи( ч..Б..Л..Ч.._ ) :-
сосед( Ч, Л), % Черный король напал на ладью
not сосед( Б, Л). % Белый король не защищает ладью
расст( X : Y, X1 : Y1, Р) :- % Расстояние до короля
абс_разн( X, X1, Рх),
абс_разн( Y, Y1, Ру),
макс( Рх, Ру, Р).
абс_разн( А, В, С) :-
А > В, !, С is A - В;
С is В - А.
макс( А, В, М) :-
А >= В, !, М = А;
М = В.
манх_расст( X : Y, X1 : Y1, Р) :- % Манхеттеновское расстояние
абс_разн( X, X1, Рх),
абс_разн( Y, Y1, Ру),
P is Рх + Ру.
простр( Поз, Пр) :-
% Область, в которой "заперт" черный король
бл( Поз, Лх : Лу),
чк( Поз, Чх : Чу),
( Чх < Лх, СторонаХ is Лх - 1;
Чх > Лх, СторонаХ 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 и таблица советов для окончания "король и ладья против короля".
Были введены и обсуждены следующие понятия:
игры двух лиц с полной информацией
игровые деревья
оценочная функция, минимаксный принцип
статические оценки, рабочие оценки
альфа-бета алгоритм
последовательное углубление,
эвристическое отсечение,