Книга: Программирование на языке Пролог для искусственного интеллекта

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

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

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

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

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

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

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

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

(5) Если ни одна из целей 1, 2, 3 или 4 не достижима, то найти способ получить позицию, в которой ладья занимает вертикальную или горизонтальную линию, отделяющую одного короля от другого.

Описанные выше принципы реализованы во всех деталях в таблице советов на языке AL0, показанной на рис. 15.7. Эта таблица может работать под управлением интерпретатора рис. 15.6. Рис. 15.8 иллюстрирует смысл некоторых из предикатов, использованных в таблице советов, а также показывает, как эта таблица работает.

В таблице используются следующие предикаты:

Предикаты целей

Предикаты, ограничивающие ходы

% Окончание "король и ладья против короля" на языке AL0
% Правила
правило_края:
 если король_противника_на_краю и короли_рядом
 то [мат_2, потеснить, приблизиться,
     сохранить_простр, отделить_2, отделить_3].
иначе_правило
 если любая_поз
 то [ потеснить, приблизиться, сохранить_простр,
      отделить_2, отделить_3].
% Элементарные советы
совет( мат_2,
       мат :
       не потеря_ладьи и король_противника_на_краю:
       (глубина = 0) и разреш
       затем (глубина = 2) и ход_шах :
       (глубина = 1) и разреш ).
совет( потеснить,
       уменьш_простр и не ладья_под_боем и
       раздел и не пат :
       не потеря_ладьи :
       (глубина = 0) и ход_ладьей :
       нет_хода ).
совет( приблизиться,
       ближе _к_клетке и не ладья_под_боем и
       (раздел или l_конфиг) и
       (простр_больше_2 или не наш_король_на_краю):
       не потеря_ладьи :
       (глубина = 0) и сначала_диаг :
       нет_хода ).
совет( сохранить_простр,
       ход_противника и не ладья_под_боем и раздел
       и не_дальше_от_ладьи и
       (простр_больше_2 или не наш_король_на_краю):
       не потеря_ладьи :
       (глубина = 0) и сначала_диаг :
       нет_хода ).
совет( отделить_2,
       ход_противника и раздел и не ладья_под_боем:
       не потеря_ладьи :
       (глубина < 3) и разреш :
       (глубина < 2) и разреш ).
совет( отделить_3,
       ход_противника и раздел и не ладья_под_боем:
       не потеря_ладьи :
       (глубина < 5) и разреш :
       (глубина < 4) и разреш ).

Рис. 15.7. Таблица советов на языке AL0 для окончания "король и ладья против короля". Таблица состоит из двух правил и шести элементарных советов.

Рис. 15.8. Фрагмент шахматной партии, полученный с использованием таблицы советов рис. 15.7 и иллюстрирующий применение стратегии оттеснения короля в угол доски. В этой последовательности ходов выполнялись элементарные советы: сохранить_ простр (выжидающий ход, сохраняющий "жизненное пространство" черного короля) и потеснить (ход, сокращающий "жизненное пространство"). Область, в которой заключен черный король, выделена штриховкой. После выполнения последнего совета потеснить эта область сократилась с восьми до шести клеток.

Рис. 15.9. (а) "Критическая клетка" отмечена крестиком. Она используется при маневрировании с целью оттеснить черного короля. Белый король приближается к "критической клетке", двигаясь, как указано на рисунке. (б) Три фигуры образуют конфигурацию, напоминающую букву L.

Аргументами этих предикатов являются либо позиции (в предикатах целей), либо ходы (в предикатах, ограничивающих ходы). Предикаты целей могут иметь один или два аргумента. Первый из аргументов — это всегда текущая вершина поиска; второй аргумент (если он имеется) — корневая вершина дерева поиска. Второй аргумент необходим в так называемых сравнивающих предикатах, которые сравнивают корневую и текущую позиции в том или ином отношении. Например, предикат уменьш_простр проверяет, сократилось ли "жизненное пространство" короля противника (рис. 15.8). Эти предикаты вместе с шахматными правилами (применительно к окончанию "король и ладья против короля"), а также процедура для отображения текущего состояния игровой доски (отобр( Поз)) запрограммированы на рис. 15.10.

На рис. 15.8 показано, как играет наша программа, основанная на механизме советов. При продолжении игры из последней позиции рис. 15.8 она могла бы протекать так, как в приведенном ниже варианте (в предположении, что "противник" ходит именно так, как указано). Здесь использована алгебраическая шахматная нотация, в которой вертикальные линии пронумерованы, как 'а', 'b', 'с', … а горизонтальные — как 1, 2, 3, …. Например, ход ЧК b7 означает: передвинуть черного короля на клетку, расположенную на пересечении вертикальной линии 'b' с горизонтальной линией 7.

…        ЧК b7

БК d5  ЧК с7

БК с5  ЧК b7

БЛ с6  ЧК а7

БЛ b6  ЧК а8

БК b5  ЧК а7

БК с6  ЧК а8

БК с7  ЧК а7

БЛ с6  ЧК а8

БЛ а6  мат

Теперь уместно задать некоторые вопросы. Во-первых, является ли наша программа-советчик корректной в том смысле, что она ставит мат при любом варианте защиты со стороны противника и при любой начальной позиции, в которой на доске король и ладья против короля? В статье Bratko (1978) приведено формальное доказательство того, что таблица советов, практически совпадающая с таблицей рис. 15.7, действительно является корректной в указанном смысле.

Другой возможный вопрос: является ли программа оптимальной, то есть верно ли, что она ставит мат за минимальное число ходов? Нетрудно показать на примерах, что игру нашей программы в этом смысле нельзя назвать оптимальной. Известно, что оптимальный вариант в этом окончании (т.е. предполагающий оптимальную игру с обеих сторон) имеет длину не более 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 - Лх ),
 ( Чу < Лу, Сторона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 (вместе с определениями соответствующих предикатов).

Оглавление книги