Миниатюрный интерпретатор ALO

Миниатюрный, независимый от конкретной игры интерпретатор AL0, реализо­ванный на языке Prolog, показан в листинге 22.4. Эта программа осуществляет так­же взаимодействие с пользователем в процессе игры. Основное назначение этой про­граммы состоит в использовании знаний из таблицы советов AL0; это означает, что программа интерпретирует таблицу советов ALO, формирует форсирующие деревья, а затем применяет их в игре. Основной алгоритм формирования форсирующего дерева аналогичен алгоритму поиска в глубину в графах AND/OR {см. главу 13); форси­рующее дерево соответствует дереву решения AND/OR, С другой стороны, этот про­цесс напоминает также формирование дерева доказательства в экспертной системе (см. главу 15).

Часть II. Применение языка Prolog в области искусственного интеллекта

Листинг 22.4. Реализация миниатюрного интерпретатора языка Advice Language О

Ъ Реализация миниатюрного интерпретатора языка Advice Language О %

i Эта программа проводит игру из заданной начальной позиции, используя знания,
% представленные на языке советов Advice Language О
:- opl 200, xfy, [:,::].
:- op<220,xfy,..).
:- op{ 185, ix, if).
:- op[ 190, Hfx, then).
:- op(1ES0, xfy, or).
:- op(160, xfy, and).
:- op (140, fx, notj.
playgame! Pos):- % Провести игру начиная с позиции Pos

playgame! Pos, nil). % Начать с пустого форсирующего дерева

playgame! Роз, ForcingTree): -show! Pos),

(end_of_game(Pos), % Игра окончена?

writef 'End of game'), nl,!

playmove(Pos, ForcingTree, Posl, ForcingTreel),!, playgame! Posl, ForcingTreel)

% Выполнить ход за своего игрока в соответствии с форсирующим деревом playmove(Pos, Move..FTreel, Posl, FTreel):-

side(Pos, w)r % Своим является игрок, который

% играет Оелыми фигурами

legalmove.(Pos, Move, Posl),

showmove(Move). I Прочитать ход, сделанный чужим игроком playmove(Pos, FTree, Posl, FTreel):-

side(Pos, b),

write('Your move: '),

read(Move),

(legalmove (Pos, Move, Posl), subtree,- FTree, Move, FTreel),! % Перейти вниз по форсирующему дереву

write [ 'Illegal move'), nl,
playmove(Pos, FTree, Posl, FTreel)
).
: Если текущее форсирующее дерево является пустым, сформировать новое
playmove(Pos, nil, Posl, FTreel):-
side(Pos, w),
resetdepth! POS, POSOI, % Позиция PosO - это позиция Pos

% с глубиной О
strategy! PosO, FTree), \, % Сформировать новое форсирующее дерево

playmove(PosO, FTree, Posl, FTreel).

% ВыОрать форсирующее поддерево, соответствующее ходу Move

subtree! FTrees, Move, FTreel:-

member,- (Move.. FTree, FTtees },!. subtree[_, _, nil).

strategy! Pos, ForcingTree):- % Най?и форсирующее дерево для позиции Pos Rule;: if Condition then AdviceList, % Получить консультацию

% no таблице советов holds! Condition, Pos, _),'., % Согласовать Pos с предварительным условием member! AdviceUame, AdviceList), % Поочередно проверить применимость

Ъ элементарных советов nl, write('Trying¹!, write! AdviceHame),

satisfiable{ AdviceName, Pos, ForcingTree),!. % Выполнить совет AdviceHame

% в позиции Pos satisfiable(AdviceKame, Pos, FTree):-

advice! AdviceKame, Advice), % Извлечь из таблицы один элементарный совет sat! Advice, Pos, Pos, FTree). % В предикате sat необходимо задавать две

s позиции, которые передаются в предикаты сравнения

Глава 22. Ведение игры

sat(Advice, Pos, RootPos, FTcee):-

holdinggoal(Advice, HG),

holds[ HG, Pos, RootPosI, % Требование достижения консервативной цели

% соблюдается

satl(Advice, Pos, RootPos, FTree). Satl{ Advice, POS, Root.Pos, nil):-

bettergoaK Advice, BG),

holds[ BG, POS, RootPos),!. i Требование достижения лучшей цели соблюдается satl(Advice, Pos, RootPos, Move..FTrees):-

side[ Pos, w),!, * Своим является игрок, который играет белыми

usmoveconstrl Advice, UMC),

move[ UMC, Pos, Move, Posl), % Ход удовлетворяет ограничениям хода

sat( Advice, Posl, RootPos, FTrees). Satl(Advice, Pos, RootPos, FTrees}:-

side I Pos, b),!, i Чужим является игрок, который играет черными

themmoveconstr(Advice, TMC),

bagof(Move..Posl, move(TMC, Pos, Move, Posl!, MPlist),

satall (ftdvice, MPlist, RootPos, FTreesl. % Совет выполним во

% всех позициях-преемниках satall{ _, [], _, []). satall { Advice, [Hove..Pos! MPlist], RootPos, (Move..FT I MFTs]):-

sat(Advice, Pos, RootPos, FT),

satall(Advice, MPlist, RootPos, MFTs).

* Толкование понятий консервативной и лучшей целей: люОая цель - это комбинация % имен предикатов, сформированная с помощью связок AND/OR/KOT

holds! Goall and Goal2, Pos, RootPos):-!, holds[ Goall, Pos, RcotPos), holds (Goal2, Pos, RootPos!.

holds{ Goall or Goal2, Pos, RootPos):-!, (holds(Goall, Pos, RootPcs)

holds(Goal2, Pos, RootPo3)). holds[ not Goal, Pos, RootPos); -!,

not holds[ Goal, Pos, RootPos). holds(Pred, Pos, RootPos):-

(Cond =..[ Pred, Pos] \ Большинство предикатов не зависит от RootPos

i

Cond =..[ Pred, Pos, RootPos]), call(Cond).

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

move! MCI and M.C2, Pos, Move, Posl):-!, novel MCI, Pos, Move, Posl), move 1 MC2, Pos, Move, Posl). move! MCI then MC2, Pos, Move, Posl):-!, (move! MCI, Pos, Move, Posl) i

move! MC2, Fos, Move, Posl)). % Селекторы для компонентов элементарного совета

better-goal [ BG: _, BG!. hoidinggoai(BG: HG: _, HG). usmoveconstrf BG: HG: UMC: _, UMC). theramoveconstrl BG: HG: UMC; ТИС, TMC). member! x, [X IL]). member! X, [Y I L] }:-member (X, L),

548

Часть II. Применение языка Prolog в области искусственного интеллет

Для простоты в программе, приведенной в листинге 22.4, предполагается, что свой игрок играет белыми фигурами, а чужой игрок - черными. Программа вызы-яается на выполнение с помощью процедуры playgame(Pos)

где Pos — выбранная начальная позиция в игре, которая должна быть проведена компьютером. Если в позиции Pos очередь хода принадлежит чужому игроку, то программа считывает ход, введенный пользователем. В противном случае программа консультируется по таблице советов, прилагаемой к этой программе, формирует фор­сирующее дерево и делает свой ход в соответствии с этим деревом. Такие действия Продолжаются до тех пор, пока не будет достигнут конец игры, как определено пре­дикатом end_of_game (например, будет поставлен мат).

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

Move..[ Replyl..Ftreel, Reply2,,Ftree2,...]

где ".." - инфиксный оператор, Move - первый ход своего игрока, Replyl, Reply2 и т.д. - возможные ответы чужого игрока, a Ftreel, Ftree2 и т.д. - форсирующие поддеревья, которые относятся к каждому из ответов чужого игрока.

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

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

Следя за тем, чтобы ни при каких условиях не возникала патовая ситуация или ладья не оставалась незащищенной от нападения короля чужого игрока, повторно выполнять перечисленные ниже действия до тех пор, пока не будет поставлен мат.

1. Искать способ поставить королю чужого игрока мат в два хода.

2. Если указанное выше невозможно, то искать способ больше ограничить область на шахматной доске, в которой короля чужого игрока удерживает ладья своего игрока.

3. Если указанное выше невозможно, то искать способ продвинуть короля своего игрока ближе к королю чужого игрока.

4. Если ни один из приведенных выше элементарных советов 1, 2 или 3 не выпол­ним, то искать способ сохранения текущих достижений в рамках элементарных советов 2 и 3 (т.е. сделать выжидательный ход). ■

5. Если не выполним ни один из элементарных советов 1, 2, 3 или 4, то искать способ получения позиции, в которой ладья своего игрока разделяет двух коро­лей либо по вертикали, либо по горизонтали.

Подробная реализация этих принципов в виде таблицы советов AL0 приведена в листинге 22.5. Эта таблица может быть вызвана на выполнение интерпретатором AL0 (см. листинг 22.4). На рис. 22.4 иллюстрируется смысл некоторых из предика­тов, используемых в этой таблице, и показан способ применения самой таблицы.

Глава 22. Ведение игры

 

		о
			w
			:	:

Операция squeeze

 

		V
				В
			<s?

 

 

Г

¹'11,(1-: ■■! | -III IK

J

 

			V
				a
			<S>-