— это логическое выражение, состоящее из имен предикатов, соединенных между собой логическими связками
и
,
или
,
не
.
СписокСоветов
— список имен элементарных советов. Приведем пример правила под названием "правило_края" из окончания "король и ладья против короля":
правило_края:
если король_противника_на_краю и короли_рядом
то [мат_2, потеснить, приблизиться,
сохранить_простр, отделить].
В этом правиле говорится:
если в текущей позиции король противника находится на краю доски, а король игрока расположен близко к королю противника (точнее, расстояние между королями меньше четырех клеток), то попытаться выполнить в указанном порядке предпочтения следующие советы: "мат_2", "потеснить", "приблизиться", "сохранить_простр", "отделить". Элементарные советы расположены в порядке убывания их "притязаний" на успех: сначала попытаться поставить мат в два хода, если не получится — "потеснить" короля противника в угол и т.д. Обратите внимание на то, что при соответствующем определении операторов наше правило станет синтаксически корректным предложением Пролога.
Для представления элементарных советов в виде прологовских предложений предназначен еще один формат:
совет( ИмяСовета,
ГлавнаяЦель:
ЦельПоддержка:
ХодыИгрока:
ХодыПротивника).
Цели представляются как выражения, состоящие из имен предикатов и логических связок
и
,
или
,
не
. Ограничения на ходы сторон — это тоже выражения, состоящие из имен предикатов и связок
и
и
затем
: связка
и
имеет обычный логический смысл, а
затем
задает порядок. Например, ограничение, имеющее вид
Огр1 затем Огр2
означает: сначала рассмотреть ходы, удовлетворяющие ограничению
Oгp1
, а затем — ходы, удовлетворяющие
Огр2
.
Например, элементарный совет, относящийся к мату в два хода в окончании "король и ладья против короля", записанный в такой синтаксической форме, имеет вид:
совет( мат_2,
мат:
не потеря_ладьи:
(глубина = 0) и разреш затем
(глубина = 2) и ход_шах :
(глубина = 1) и разреш ).
Здесь главная цель —
мат
, цель-поддержка
не потеря_ладьи
. Ограничение на ходы игрока означает: на глубине 0 (т.е. в текущей позиции) попробовать любой разрешенный ход и затем на глубине 2 (следующий ход игрока) пробовать только ходы с шахом. Глубина измеряется в полуходах. Ограничение на ходы противника: любой разрешенный ход на глубине 1.
В процессе игры таблица советов используется многократно вплоть до окончания игры, при этом выполняется следующий основной цикл: построить форсированное дерево, затем играть в соответствии с этим деревом, пока не произойдет выход из него; построить другое форсированное дерево и т.д. Форсированное дерево строится каждый раз таким образом: берется текущая позиция
Поз
и просматриваются одно за другим все правила таблицы советов; для каждого правила сопоставляется
Поз
с предварительным условием этого правила и просмотр прекращается, когда будет обнаружено правило, для которого
Поз
удовлетворяет предварительному условию. В этом случае надо рассмотреть список советов найденного правила: обработать элементарные советы один за другим, пока не будет построено форсированное дерево, представляющее собой детальную стратегию игры в этой позиции.
Следует обратить внимание на существенность того порядка, в котором перечисляются правила в таблице советов. Правило, которое реально используется, — это первое из тех правил, предварительные
условия которых согласуются с текущей позицией. Для любой возможной позиции должно существовать по крайней мере одно такое правило. Из него берется список советов, и первый из выполнимых советов списка используется в игре.
Таким образом, таблица советов это программа в высшей степени непроцедурного характера. Интерпретатор языка AL0 принимает на входе некоторую позицию, а затем, "исполняя" таблицу советов, строит форсированное дерево, определяющее стратегию игры в этой позиции.
15.6. Программа на языке AL0 для игры в шахматном эндшпиле
При реализации какой-либо игровой программы на языке AL0 ее можно для удобства разбить на три модуля:
(1) интерпретатор языка AL0,
(2) таблица советов на языке AL0,
(3) библиотека предикатов, используемых в таблице советов (в том числе предикаты, задающие правила игры).
Эта структура соответствует обычной структуре системы, основанной на знаниях:
• Интерпретатор AL0 выполняет функцию машины логического вывода.
• Таблица советов вместе с библиотекой предикатов образует базу знаний.
15.6.1. Миниатюрный интерпретатор языка AL0
Реализация на Прологе миниатюрного, не зависящего от конкретной игры интерпретатора языка AL0 показана на рис. 15.6. Эта программа осуществляет также взаимодействие с пользователем во время игры. Центральная задача этой программы — использовать знания, записанные в таблице советов, то есть интерпретировать программу на языке советов AL0 с целью построения форсированных деревьев и их "исполнения" в процессе игры. Базовый алгоритм порождения форсированных деревьев аналогичен поиску с предпочтением в И/ИЛИ-графах гл. 13, при этом форсированное дерево соответствует решающему И/ИЛИ-дереву. Этот алгоритм также напоминает алгоритм построения решающего дерева ответа на вопрос пользователя, применявшийся в оболочке экспертной системы (гл. 14).
Программа на рис. 15.6 составлена в предположении, что она играет белыми, а ее противник — черными. Программа запускается процедурой
игра( Поз)
где
Поз
— выбранная начальная позиция. Если в позиции
Поз
ходит противник, то программа принимает его ход, в противном случае — "консультируется" с таблицей советов, приложенной к программе, порождает форсированное дерево и делает свой ход в соответствии с этим деревом. Так продолжается до окончания игры, которое обнаруживает предикат
конец_игры
(например, если поставлен мат).
% Миниатюрный интерпретатор языка AL0
%
% Эта программа играет, начиная с заданной позиции,
% используя знания, записанные на языке AL0
:- op( 200, xfy, :).
:- op( 220, xfy, ..).
:- op( 185, fx, если).
:- op( 190, xfx, то).
:- op( 180, xfy, или).
:- op( 160, xfy, и).
:- op( 140, fx, не).
игра( Поз) :- % Играть, начиная с Поз
игра( Поз, nil).
% Начать с пустого форсированного дерева
игра( Поз, ФорсДер) :-
отобр( Поз),
( конец_игры( Поз), % Конец игры?
write( 'Конец игры'), nl, !;
сделать_ход( Поз, ФорсДер, Поз1, ФорсДер1), !,
игра( Поз1, ФорсДер1) ).
% Игрок ходит в соответствии с форсированным деревом