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

Таким образом, таблица советов это программа в высшей степени непроцедурного характера. Интерпретатор языка 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) ).

% Игрок ходит в соответствии с форсированным деревом

сделать_ход( Поз, Ход .. ФДер1, Поз1, ФДер1) :-

 чей_ход( Поз, б),    % Программа играет белыми

 разрход( Поз, Ход, Поз1),

 показать_ход( Ход).

% Прием хода противника

сделать_ход( Поз, ФДер, Поз1, ФДер1) :-

 чей_ход( Поз, ч),

 write( 'Ваш ход:'),

 read( Ход),

 ( разрход( Поз, Ход, Поз1),

   поддер( ФДер, Ход, ФДер1), !;

    % Вниз по форс. дереву

 write( 'Неразрешенный ход'), nl,

 сделать_ход( Поз, ФДер, Поз1, ФДер1) ).

% Если текущее форсированное дерево пусто, построить новое

сделать_ход( Поз, nil, Поз1, ФДер1) :-

 чей_ход( Поз, б),

 восст_глуб( Поз, Поз0),

  % Поз0 = Поз с глубиной 0

 стратегия( Поз0, ФДер), !,

  % Новое форсированное дерево

 сделать_ход( Поз0, ФДер, Поз1, ФДер1).

% Выбрать форсированное поддерево, соответствующее Ход'у

поддер( ФДеревья, Ход, Фдер) :-

 принадлежит( Ход . . Фдер, ФДеревья), !.

поддер( _, _, nil).

стратегия( Поз, ФорсДер) :-

  % Найти форс. дерево для Поз

 Прав : если Условие то СписСов,

  % Обращение к таблице советов

 удовл( Условие, Поз, _ ), !,

  % Сопоставить Поз с предварительным условием

 принадлежит( ИмяСовета, СписСов),

  % По очереди попробовать элем. советы

 nl, write( 'Пробую'), write( ИмяСовета),

 выполн_совет( ИмяСовета, Поз, ФорсДер), !.

выполн_совет( ИмяСовета, Поз, Фдер) :-

 совет( ИмяСовета, Совет),

  % Найти элементарный совет

 выполн( Совет, Поз, Поз, ФДер).

% "выполн" требует две позиции для сравнивающих предикатов

выполн( Совет, Поз, КорнПоз, ФДер) :-

 поддержка( Совет, ЦП),

 удовл( ЦП, Поз, КорнПоз),

  % Сопоставить Поз с целью-поддержкой

 выполн1( Совет, Поз, КорнПоз, ФДер).

выполн1( Совет, Поз, КорнПоз, nil) :-

 главцель( Совет, ГлЦ),

 удовл( ГлЦ, Поз, КорнПоз), !.

  % Главная цель удовлетворяется

выполн1( Совет, Поз, КорнПоз, Ход .. ФДеревья) :-

 чей_ход( Поз, б), !, % Программа играет белыми

 ходы_игрока( Совет, ХодыИгрока),

  % Ограничения на ходы игрока

 ход( ХодыИгрока, Поз, Ход, Поз1),

  % Ход, удовлетворяющий ограничению

 выполн( Совет, Поз1, КорнПоз, ФДеревья).

выполн1( Совет, Поз, КорнПоз, ФДеревья) :-

 чей_ход( Поз, ч), !, % Противник играет черными

 ходы_противника( Совет, ХодыПр),

 bagof ( Ход .. Поз1, ход( ХодыПр, Поз, Ход, Поз1), ХПспис),

 выполн_все( Совет, ХПспис, КорнПоз, ФДеревья).

  % Совет выполним во всех преемниках Поз

выполн_все( _, [], _, []).

выполн_все( Совет, [Ход .. Поз | ХПспис], КорнПоз,

 [Ход .. ФД | ФДД] ) :-

 выполн( Совет, Поз, КорнПоз, ФД),

выполн_все( Совет, ХПспис, КорнПоз, ФДД).

% Интерпретация главной цели и цели-поддержки:

% цель - это И / ИЛИ / НЕ комбинация. имен предикатов

удовл( Цель1 и Цель2, Поз, КорнПоз) :- !,

 удовл( Цель1, Поз, КорнПоз),

 удовл( Цель2, Поз, КорнПоз).

удовл( Цель1 или Цель2, Поз, КорнПоз) :- !,

 ( удовл( Цель1, Поз, КорнПоз);

   удовл( Цель2, Поз, КорнПоз) ).

удовл( не Цель, Поз, КорнПоз) :- !,

 not удовл( Цель, Поз, КорнПоз ).

удовл( Пред, Поз, КорнПоз) :-

 ( Усл =.. [Пред, Поз];

  % Большинство предикатов не зависит от КорнПоз

   Усл =.. [Пред, Поз, КорнПоз] ),

 call( Усл).

% Интерпретация ограничений на ходы

ход( Ходы1 и Ходы2, Поз, Ход, Поз1) :- !,

 ход( Ходы1, Поз, Ход, Поз1),

 ход( Ходы2, Поз, Ход, Поз1).

ход( Ходы1 затем Ходы2, Поз, Ход, Поз1) :- !,

 ( ход( Ходы1, Поз, Ход, Поз1);

   ход( Ходы2, Поз, Ход, Поз1) ).

% Доступ к компонентам элементарного совета

главцель( ГлЦ : _, ГлЦ).

поддержка( ГлЦ : ЦП : _, ЦП).

ходы_игрока( ГлЦ : ЦП : ХодыИгрока : _, Ходы Игрока).

ходы_противника( ГлЦ : ЦП: ХодыИгр : ХодыПр :_,

 ХодыПр).

принадлежит( X, [X | Спис]).

принадлежит( X, [Y | Спис]) :-

 принадлежит( X, Спис).

Рис. 15.6. Миниатюрный интерпретатор языка AL0.

Форсированное дерево — это дерево ходов, представленное в программе следующей структурой:

Ход .. [ Ответ1 .. Фдер1, Ответ2 .. Фдер2, ... ]

Здесь ".." — инфиксный оператор; Ход — первый ход "игрока"; Ответ1, Ответ2, … — возможные ответы противника; Фдер1, Фдер2, … — форсированные поддеревья для каждого из этих ответов.

15.6.2. Программа на языке советов для эндшпиля "король и ладья против короля"

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