Неизвестно - Prolog

На рис. 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 ходов; иначе может быть объявлена ничья.

Проект

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

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

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

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

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

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

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

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

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

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

% поиска

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

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

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

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

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

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

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