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

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

% Библиотека предикатов для окончания

% "король и ладья против короля"

% Позиция представлена стуктурой:

% ЧейХод..Бх : Бу..Лх : Лу..Чх : Чу..Глуб

% ЧейХод - с чьей стороны ход в этой позиции ('б' или 'ч')

% Бх, Бу - координаты белого короля

% Лх, Лу - координаты белой ладьи

% Чх, Чу - координаты черного короля

% Глуб - глубина, на которой находится эта позиция в дереве

% поиска

% Отношения выбора элементов позиции

чей_ход( ЧейХод.._, ЧейХод).

бк( _..БК.._, БК). % Белый король

бл( _.._..БЛ.._, БЛ). % Белая ладья

чк( _.._.._..ЧК.._, ЧК). % Черный король

глуб( _.._.._.._..Глуб, Глуб).

восст_глуб( ЧХ..Б..Л..Ч..Г, ЧХ..Б..Л..Ч..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 - Лх ),