Пр 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 и таблица советов для окончания
