Иван Братко - Программирование на языке Пролог для искусственного интеллекта
% Библиотека предикатов для окончания
% "король и ладья против короля"
% Позиция представлена стуктурой:
% ЧейХод..Бх : Бу..Лх : Лу..Чх : Чу..Глуб
% ЧейХод - с чьей стороны ход в этой позиции ('б' или 'ч')
% Бх, Бу - координаты белого короля
% Лх, Лу - координаты белой ладьи
% Чх, Чу - координаты черного короля
% Глуб - глубина, на которой находится эта позиция в дереве
% поиска
% Отношения выбора элементов позиции
чей_ход( ЧейХод.._, ЧейХод).
бк( _..БК.._, БК). % Белый король
бл( _.._..БЛ.._, БЛ). % Белая ладья
чк( _.._.._..ЧК.._, ЧК). % Черный король
глуб( _.._.._.._..Глуб, Глуб).
восст_глуб( ЧХ..Б..Л..Ч..Г, ЧХ..Б..Л..Ч..0).
% Формируется копия позиции, глубина устанавливается в 0
% Некоторые отношения между клетками доски
сосед_чсл( N, N1) :- % Соседнее число "в пределах доски"
( N1 is N + 1;
N1 is N - 1 ),
внутри( N1).
внутри( N) :-
N > 0, N < 9.
сосед_диаг( X : Y, X1 : Y1) :-
% Соседние клетки по диагонали
сосед_чсл( X, X1 ), сосед_чсл( Y, Y1).
сосед_верт( X : Y, X : Y1) :-
% Соседние клетки по вертикали
сосед_чсл( Y, Y1).
сосед_гор( X : Y, X1 : Y) :-
% Соседние клетки по горизонтали
сосед_чсл( X, X1).
сосед( S, S1) :-
% Соседние клетки (предпочтение - диагонали)
сосед_диаг( S, S1);
сосед_гор( S, S1);
сосед_верт( S, S1).
конец_игры( Поз) :-
мат( Поз).
% Предикаты, ограничивающие ходы
% Специализированное генераторы ходов вида:
% ход( Ограничение, Поз, Ход, Поз1)
ход( глубина < Макс, Поз, Ход, Поз1) :-
глуб( Поз, Г),
Г < Макс, !.
ход( глубина = Г, Поз, Ход, Поз1) :-
глуб( Поз, Г), !.
ход( сначала диаг, б..Б..Л..Ч..Г, Б-Б1,
ч..Б1..Л..Ч..Г1) :-
Г1 is Г + l,
сосед( Б, Б1),
% "сосед" порождает сначала диагональные ходы
not сосед( Б1, Ч), % Не попасть под шах
Б1 == Л. % Не столкнуться с ладьей
ход( ход ладьей, б..Б..Лх : Лу..Ч..Г, Лх : Лу-Л,
ч..Б..Л..Ч..Г1) :-
Г1 is Г + 1,
коорд( I), % Число между 1 и 8
( Л = Лх : I; Л = I : Лу),
% По горизонтали или по вертикали
Л == Лх : Лу, % Обязательно двигаться
not мешает( Лх : Лу, Б, Л). % Мешает белый король
ход( ход_шах, Поз, Л-Лх : Лу, Поз1) :-
бл( Поз, Л),
чк( Поз, Чх : Чу),
( Лх = Чх; Лу = Чу),
% Ладья и черный король на одной линии
ход( ход_ладьей, Поз, Л-Лх : Лу, Поз1).
ход( разреш, б..П, М, П1) :-
( Огр = сначала_диаг; Огр = ход ладьей),
ход( Огр, б..П, М, П1).
ход( разреш, ч..Б..Л..Ч..Г, Ч-Ч1, б..Б..Л..Ч1..Г1) :-
Г1 is Г + 1,
сосед( Ч, Ч1),
not шах( б..Б..Л..Ч1..Г1).
разрход( Поз, Ход, Поз1) :-
ход( разреш, Поз, Ход, Поз1).
шах( _..Б..Лх : Лу..Чх : Чу.._ ) :-
сосед( Б, Чх : Чу); % Короли рядом
( Лх = Чх; Лу = Чу),
Лх : Лу == Чх : Чу, % Нет взятия ладьи
not мешает( Лх : Лу, Б, Чх : Чу).
мешает( S, S1, S1) :- !.
мешает( X1 : Y, X2 : Y, Х3 : Y) :-
упоряд( X1, Х2, Х3), !.
мешает( X : Y1, X : Y2, X : Y3) :-
упоряд( Y1, Y2, Y3).
упоряд( N1, N2, N3) :-
N1 < N2, N2 < N3;
N3 < N2, N2 < N1.
коорд( 1). коорд( 2). коорд( 3). коорд( 4).
коорд( 5). коорд( 6). коорд( 7). коорд( 8).
% Предикаты целей
любая_поз( Поз).
ход_противника( б.._ ). % Противник ходит белыми
мат( Поз) :-
чей_ход( Поз, ч),
шах( Поз),
not разрход( Поз, _, _ ).
пат( Поз) :-
чей_ход( Поз, ч),
not шах( Поз),
not разрход( Поз, _, _ ).
уменьш_простр( Поз, КорнПоз) :-
простр( Поз, Пр),
простр( КорнПоз, КорнПр),
Пр < КорнПр.
ладья_под_боем( ЧейХод..Б..Л..Ч.._ ) :-
расст( Б, Л, P1),
расст( Ч, Л, Р2),
( ЧейХод = б, !, P1 > Р2 + 1;
ЧейХод = ч, !, P1 > Р2 ).
ближе_к_клетке( Поз, КорнПоз) :-
расст_до_клетки( Поз, P1),
расст_до_клетки( КорнПоз, Р2),
P1 < Р2.
расст_до_клетки( Поз, Мрасст) :-
% Манхеттеновское расстояние
бк( Поз, БК), % между БК и критической клеткой
кк( Поз, КК), % Критическая клетка
манх_расст( БК, КК, Мрасст).
раздел( _..Бх : Бу..Лх : Лу.. Чх : Чу.._ ) :-
упоряд( Бх, Лх, Чх), !;
упоряд( Бу, Лу, Чу).
l_конфиг( _..Б..Л..Ч.._ ) :- % L - конфигурация
манх_расст( Б, Ч, 2),
манх_расст( Л, Ч, 3).
не дальше_от_ладьи( _..Б..Л.._, _..Б1..Л1.._ ) :-
расст( Б, Л, P),
расст( Б1, Л1, P1),
P =< P1.
простр_больше_2( Поз) :-
простр( Поз, Пр),
Пр > 2.
наш_король_на_краю( _..X : Y.._ ) :-
% Белый король на краю
( X = 1, !; X = 8, !; Y = 1, !; Y = 8).
король_противника_на_краю( _..Б..Л..X : Y.._ ) :-
% Черный король на краю
( X = 1, !; X = 8, !; Y = 1, !; Y = 8).
короли_рядом( Поз) :- % Расстояние между королями < 4
бк( Поз, БК), чк( Поз, ЧК),
расст( БК, ЧК, P),
P < 4.
потеря_ладьи( _..Б..Л..Л.._ )- % Ладья взята
потеря_ладьи( ч..Б..Л..Ч.._ ) :-
сосед( Ч, Л), % Черный король напал на ладью
not сосед( Б, Л). % Белый король не защищает ладью
расст( X : Y, X1 : Y1, P) :- % Расстояние до короля
абс_разн( X, X1, Рх),
абс_разн( Y, Y1, Ру),
макс( Рх, Ру, P).
абс_разн( А, В, С) :-
А > В, !, С is A - В;
С is В - А.
макс( А, В, М) :-
А >= В, !, М = А;
М = В.
манх_расст( X : Y, X1 : Y1, P) :- % Манхеттеновское расстояние
абс_разн( X, X1, Рх),
абс_разн( Y, Y1, Ру),
P is Рх + Ру.
простр( Поз, Пр) :-
% Область, в которой "заперт" черный король
бл( Поз, Лх : Лу),
чк( Поз, Чх : Чу),
( Чх < Лх, СторонаХ is Лх - 1;
Чх > Лх, СторонаХ is 8 - Лх ),
( Чу < Лу, СторонаY is Лу - 1;
Чу > Лу, СторонаY is 8 - Лу ),
Пр is СторонаХ * СторонаY, !;
Пр = 64. % Ладья и черный король на одной линии
кк( _..Б..Лх : Лу.. Чх : Чу.._, Кх : Ку) :-
% Критическая клетка
( Чх < Лх, !, Кх is Лх - 1; Кх is Лх + 1),
( Чу < Лу, !, Ку is Лу - 1; Ку is Лу + 1).
% Процедуры для отображения позиций
отобр( Поз) :-
nl,
коорд( Y), nl,
коорд( X),
печ_фиг( X : Y, Поз),
fail.
отобр( Поз) :-
чей_ход( Поз, ЧХ), глуб( Поз, Г),
nl, write( 'ЧейХод='), write( ЧХ),
write( 'Глубина='), write( Г), nl.
печ_фиг( Клетка, Поз):-
бк( Поз, Клетка), !, write( 'Б');
бл( Поз, Клетка), !, write( 'Л');
чк( Поз, Клетка), !, write( 'Ч');
write( '.').
показать_ход( Ход) :-
nl, write( Ход), nl.
Рис. 15.10. Библиотека предикатов для окончания "король и ладья против короля".
ПроектРассмотрите какой-нибудь другой простой эндшпиль, например "король и пешка против короля", и напишите для него программу на языке AL0 (вместе с определениями соответствующих предикатов).
Резюме
• Игры двух лиц поддаются формальному представлению в виде И/ИЛИ-графов. Поэтому процедуры поиска в И/ИЛИ-графах применимы для поиска в игровых деревьях.
