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

Программа на рис. 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, … — форсированные поддеревья для каждого из этих ответов.

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

Повторять циклически, пока не будет поставлен мат (постоянно проверяя, что не возникла патовая позиция и что нет нападения на незащищенную ладью):

(1) Найти способ поставить королю противника мат в два хода.

(2) Если не удалось, то найти способ уменьшить ту область доски, в которой король противника "заперт" под воздействием ладьи.

(3) Если и это не удалось, то найти способ приблизить своего короля к королю противника.