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