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

Окончание табл. 22.2

Предикат

Описание

okapproacheficsquare

Король своего игрока приблизился it "критической клетке' (рис. 22.5); это означает, что мвнхэттенское расстояние уменьшилось

lpatt roomgt2

L-образный шаблон (см. рис. 22.5)

Предикаты ограничений хода depth - N legal checkmove rookmove nomove kingdiagf irst

Область свободного пространства (room) для короля чужого игрока состоит больше чем из двух клеток

Ход встречающийся на глубине depth = N в дереве поиска Любой допустимый ход

Проверка хода

Ход ладьи

Цель, которая не достигается при любом ходе

Один из ходов короля, среди которых предпочтительными являются ходы короля по диагонали

S]

В

V

п

^rs

Рис. 22.5. Определение понятия L образного шаблона: а) иллюстрация к по­нятию критической клетки (клетки, наиболее важной в маневрах, имеющих целью ограничить свободное пространство для коралл противника, которая обозначена крестиком); белый король приближается к этой критической клетке, сделав указанный ход; б) три фигуры образуют L-образный шаблон

Параметрами этих предикатов являются либо позиции (предикаты цели), либо ходы (предикаты ограничений ходов). Предикаты цели могут иметь один или два па­раметра. Одним из параметров всегда является текущий узел поиска, а второй пара­метр (если он существует) представляет собой корневой узел дерева поиска. Второй параметр требуется в так называемых предикатах сравнения, которые сравнивают по некоторому признаку корневую и текущую позицию поиска. В качестве примера можно указать предикат newroomsmaller, который проверяет, удалось ли сузить свободное пространство для короля противника (см. рис. 22.4). Эти предикаты, а также шахматные правила для эндшпиля "король и ладья против короля" и проце­дура отображения шахматной доски (show[ Pos)) приведены в программе в листин­ге 22.6.

Листинг 22.6. Библиотека предикатов для эндшпиля "король и ладья против короля" % Библиотека предикатов для эндшпиля "король и ладья против короля"

i Позиция представлена с помощью функтора Side..Wx : Wy..RK : Ry..Bx : By..Depth

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

Side - соперник, имеющий право кода ['W -Wx, Wy - координаты X и Y белого короля Rx, Ry - координаты X и Y белой ладьи Вх, By - координаты X и Y черного короля Depth - глубина позиции в дереве поиска

белый, или 'В'

черный}

%

Селекторные отношения

side ( Side. ._, Side) . % Side - соперник, иметапий право хода в данной позиции
wk( _.,KK.._, WK) . »Координаты белого короля

wr( _••_•.WR.._, WR) . t Координаты белой ладьи

Ыс (._. ^ . _.ВК, ._, ВК) , % Координаты черного короля

depthf _.._.._.._..Depth, Depth). % Глубина позиции в дереве поиска

resetdeptht S..W..R..В..D, S..W..R..В..О) . % Копия позиции с глубиной О

%

Некоторые отношения между клетками

-

% Числовые обозначения соседних клеток должны находиться % в пределах размеров доски

n( N, N1)

( HI is И + 1; HI 15 Я - 1| ,

in( N1) . in[N) :-

% Клетки, соседние по диагонали % Клетки, соседние по вертикали % Клетки, соседние по горизонтали i Соседние клетки, первая диагональ

N > О, N < 9. diagngb( X : Y, XI : Yl) :-

n( X, XI) , n( Y, YD . verngb( X : Y, X : Yl) :-

n( Y, Yl) . borngb( X : Y, XI : Y) :-

n{ X, XI) . ngb( S, SI) :-

diagngbl S, SI) ;

horngb( S, SI) ;

verngbl S, SI). end_of_game( Pos> :-

mate[ Pos) .

% Предикаты ограничений хода

% move! MoveConstr, Pos, Move, HewPos):

% специализированные предикаты для формирования ходов

move( depth < Max, Pos, Hove, Posl) :-depth! Pos, D) , D < Max, ! .

move ( depth » D, Pos, Move, Posl) :-depth{ Pos, D>, !.

move( kingdiagfirst, W..W..R..B..D, W-Wl, b..Wl..R..B..Dl) :-Dl is D + 1,

ngb[ W, Wl) , % Предикат ngb в первую очередь вырабатывает ходы по диагонали
not ngb{ Wl, S) , % Король не должен становиться под шах

Wl \== R. % Его позиция не должка совпадать с позицией ладьи

roove( rookmove, W..W..RK : Ry..B..D, Rx Dl is D + 1, coord! I) ,

( R = Rx : I; R = I : R.y) , R \~~ Rx : Ry, not inway( Rx : Ry, W, R) .

: Ry-R, b..W..R..B..Dl) :-

t Целое число от 1 до В % Код по вертикали или по горизонтали

Ход уже должен быть сделан i На пути нет белого короля

: -

move[ cbeckmove, Pos, R-Rx : Ry, Posl) wr( Pos, R) , bk[ Pos, Bx : By) ,

% Ладья и черный король стоят на одной линии Ry, Posl) .

(Rx - Вх; Ry = By) , move( rookreove, Pos, R-R

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

rookmovej ,

B-Bl, w.-W..K,,B1.,D1)

move( legal, w..P, M, PI) :-( MC - kingdiagfirst; MC = movef MC, w..P, M, PI}.

move! legal, b..W..R..B..D, Dl is D + 1, ngbl B, Bl) , not check( w.,W. .R. .B1..D1)

: -

legalmove[ Pos, Move, Posl) :-move! legal, Роз, Move, Posl}.

check(_.-W..Rx:Ry..Bx:By.._) :-ngb( W, Bx : By!;

( Rx - Bh; Ry = By] , Rx : Ry \== Bx : By, not inwayl Rx : Ry, W, Bx : By) .

inwayt S, SI, SI) :- !.

% Король находится слишком близко % Ладья не взята

inwayt XI

!

У, Х2 : Y, ХЗ: Y)

ordered! X1_E X2, ХЗ)

: -

inwayl X : Y1, X : Y2 , X : Y3) : -ordered! Yl, Y2, Y3) .

ordered! N1, N2, N3) :-N1 < N2 , N2 < КЗ ; N3 < N2, N2 < HI.

coord(l) . coord(21 coord(5) . coord(6) % Целевые предикаты true[ Pos) . themtomovel b.._) .

coord(3) . coord it). coord(7) . coord[8) .

Очередь хода принадлежит чужому игроку, черными фигурами

mate( Pos) : -

side[ Pos, b) ,

_) .

check ( Pos) ,

not legalmovef Pos, stalemate! Posl :-

side[ Pos, b) ,

not check( Pos) ,

_, _ ) -RootPos)

: -

not legalmove[ Pos, newroomsmallerf Pos,

room( Pos, Room},

room! RootPos, RootRoom) ,

: -

Room < RootRoom. rookexposed [ Side..W..R..B.._

distf W, R, Dl) ,

dist( B, R, D2) , [Side = w, ! , Dl > D2 + 1

Side = b, !, Dl > D2) .

который играет

-

okapproachedcsguaref Pos, RootPos} okcsguaremdist( Pos, Dl) , okcsguaremdist( RootPos, D2) , Dl < D2 .

okcsguaremdistl Pos, Mdist)

Манхэттенское расстояние между

белым королем WK и критической клеткой

i Критическая клетка

-

wk[ Pos, WK) , сз( Pos, CS), manhdistf W<, CS, Mdist). rookdivides( _.-WK : Hy..Rx

Ry..Bx : By.. )

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

% L-образный шаблон : -

orcteredt Vx, Rx, Bx) , ! ;

ordered! Wy, Ry, By) . lpatt( _. .W..R..B.._) :-

manhdist( W, B, 2) ,

roanhdistlR, B, 3) . Okorndle( _..W..R.._, _..Wl. -Rl.._ )

dist( W, R, DJ,

dist[ wi, Rl, Dl) ,

D -< Dl. roomgt2 ( Pos) : -room( Pos, Room], Roam > 2 .

our_king_edge( _..X : Y.._) :- % Белый король в углу

( X -l, !; X = 8, \/ Y - 1, !; Y = 8) . their_king_edge[_..W..R..X : Y.._) :- % Черный король в углу

[Х- 1, !;Х= 8, ! ; Y - 1, !; Y = В ) .
kings_close( Роз} :- *" Расстояние между королями меньше к

wk[ Pos, WK) , bk( Pos, BK) ,

dist [ WK, BK, D) ,

% Ладья взята i Черный король нападает на ладью * Белый король ее не защищает % Расстояние в ходах королей

D < 4 . rooklost( _..W..B..B.._) . rooklost(b..N.-R.,B.•_) :-

ngb( Ъ, К) ,

not ngb( w, R) . dist ( X : Y, XI : У1_Г D) :-

absdiff(X, XI, Dx) ,

absdifft Y, Yl, Dy) ,

max( Dx, Dy, D) . absdiff [ A, B, D) :-

A > B, ! , D is A - B;

D is В - A, max[ А, В, М) :-

A > = Б, ! , M = A;

K = Б.
manhdist( X : Y, XI : Yl, D> : - % Нанхэттенское расстояние

absdifft X, XI, Dx) ,

absdifft Y, Yl, Dy] ,

D is Dx + Dy.
room! Pos, Room) :- % Область, в которой ограничен черный король

wr( POS, Rx : Ry) ,

bk( Pos, Bx : By) , ( Bx < Rx, SideX is Rx - 1; Bx > Rx, SideX is в - Rx) , ( By < Ry, SideY is Ry - 1; By > Ry, SideY is 8 - Ry) ,

Room is SideX • SideY, !

Room is 64. % Ладья находится на одной линии с черным королем

cs( _..W..Rx : Ry..Bx : Ву.._, Сх : Су) :- t "Критическая клетка"

[ Bx < Rx, !, Сх is Rx - 1; Сх is Rx + 1) ,

[ Ву< Ry, !, Су is Ry - 1; Су is Ry + 1) .

% Процедуры вывода данных

show! Pos] :-nl,

coord! Y) , nl, coord( X) ,

writepiece( X : У, Роз) , fail.

show( Pos) :-

side( Pos, S) , depth( Pos, D) ,

nl, write ( 'Side= ' ) , write ( S) ,

write! 'Depths ' ) , write ( D) , nl . writepiece( Sguare, Pos) :-

wk( Pos, Sguare), !, write! '»') ;

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

wr ( Eos, Square) , !, write( 'R') ; bk( Pos, Square) , !, write( ' В') ; write! ' . ' ) • showmovet Move} :-nl, write I Move) , nl.

Пример того, как играет эта программа, основанная на использовании таблицы советов, показан на рис. 22.4. Игра продолжается с последней позиции (см. рис. 22.4), как в следующем варианте (при условии, что чужой игрок делает те ходы, которые указаны в этом варианте). Здесь используется буквенно-цифровая шахматная система обозначений, согласно которой вертикали шахматной доски обо­значены буквами "а", "Ь", "с" и т.д., а горизонтали •- цифрами 1, 2, 3 и т.д. Первая прописная буква обозначает цвет (В - черный, w - белый), а вторая прописная бук­ва - фигуру (К - король, R - ладья). Например, ход "ЗК Ь7" означает: передвинуть черного короля на клетку, которая находится на пересечении вертикали "Ь" и гори­зонтали 7.

,..ВК Ь7 НК d5 ВК с7 ИК с5 ВК Ь7 WR сб вк а7 HR Ь6 ВК аЭ WK Ь5 ВК а7 WK Сб ВК а8 WK С7 ВК а7 W R сб ВК а8 "WB а6 мат

Теперь необходимо найти ответы на некоторые вопросы. Прежде всего, является ли эта программа, основанная на использовании таблицы советов, правильной в том смысле, что она ставит мат, несмотря ни на какие оборонительные действия, если игра начинается с любой позиции эндшпиля "король и ладья против короля"? В [13] посредством формального доказательства показано, что в этом смысле таблица сове­тов, по сути, аналогичная приведенной в листинге 22.5, является правильной.

Еще один вопрос состоит в том, действительно ли эта программа, основанная на таблице советов, является оптимальной в том отношении, что она всегда ставит мат за наименьшее количество ходов? Можно легко показать на примерах, что с этой точки зрения игра программы не является оптимальной. Как известно, в этом энд­шпиле оптимальные варианты (в которых оба игрока выбирают самые сильные ходы) имеют длину не больше 16 ходов. Хотя игра по рассматриваемой здесь таблице сове­тов может оказаться довольно далекой от этого оптимума, было показано, что коли­чество необходимых ходов при использовании этой таблицы советов все еще доста­точно далеко от опасного предела, равного 50. Это важно потому, что в шахматах действует правило 50 ходов: в таких эндшпилях, как "король и ладья против коро­ля", сильнейшая сторона должна поставить мат за 50 ходов; в противном случае мо­жет быть объявлена ничья.

Проект

Рассмотрите некоторые другие простые шахматные эндшпили, такие как "король и пешка против короля", и напишите программу AL0 (вместе с соответствующими определениями предикатов) для поиска игровых продолжений в этих эндшпилях.

Резюме

• Игры с двумя участниками соответствуют формальному определению графов AND/OR. Поэтому для поиска в деревьях игры могут использоваться процеду­ры поиска AND/OR.

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

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

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

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

• Числовая оценка представляет собой весьма ограничительную форму примене­ния знаний о конкретной игре. Б любом подходе к ведению игры, основанном на использовании большего объема знаний, должно быть предусмотрено при­менение знаний в виде готовых образцов действий. Такой подход может быть реализован с помощью так называемых языков советов Advice Language, в ко­торых знания представлены в виде целей и средств достижения этих целей.

• В настоящей главе рассматриваются следующие программы: реализация принципа минимакса и альфа-бета-алгоритма, интерпретатор языка Advice Language О и таблица советов для ведения шахматного эндшпиля "король и ладья против короля'⁷.

• В данной главе рассматривались следующие понятия:

• игры с двумя участниками, с полной информацией;

• деревья игры;

• функция оценки, принцип минимакса;

• статические значения, зафиксированные значения;

• альфа-бета-алгоритм;

• последовательное углубление, эвристическое отсечение, эвристические функции поиска спокойных позиций;

• эффект горизонта;

• языки советов Advice Language;

• цели, ограничения, элементарный совет, таблица советов.