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

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

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

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

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

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

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

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

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

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

мат мат королю противника пат пат королю противника потеря_ладьи король противника может взять ладью ладья_под_боем король противника может напасть на ладью прежде, чем наш король сможет ее защитить уменьш_простр уменьшилось "жизненное пространство" короля противника, ограничиваемое ладьей раздел ладья занимает вертикальную или горизонтальную линию, разделяющую королей ближе_к_клетке наш король приблизился к "критической клетке" (см. рис. 15.9), т.е. манхеттеновское расстояние до нее уменьшилось l_конфиг "L-конфигурация" (рис. 15.9) простр_больше_2 "жизненное пространство" короля противника занимает больше двух клеток

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

глубина = N ход на глубине N дерева поиска разреш любой разрешенный ход ход_шах ход, объявляющий шах ход_ладьей ход ладьей нет_хода ни один ход не подходит сначала_диаг ход королем, преимущественно по диагонали

% Окончание "король и ладья против короля" на языке 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 ходов; иначе может быть объявлена ничья.

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