Выполнимость совета

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

1. Никогда не нарушается требование достижения консервативной цели.

2. Все выполняемые ходы своего игрока удовлетворяют ограничениям своего хода.

3. Чужому игроку разрешается выполнять только те ходы, которые удовлетво­ряют ограничениям чужого хода.

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

• корневым узлом Т является Р;

• все позиции в Т удовлетворяют консервативной цели;

• все терминальные узлы Т удовлетворяют лучшей цели, и ни один внутренний узел в Т не удовлетворяет лучшей цели;

• имеется точно один ход своего игрока из каждой внутренней позиции своего хода в Т, и этот ход должен удовлетворять ограничениям своего хода;

• Т содержит все ходы чужого игрока (которые удовлетворяют ограничениям чужого хода) из каждой незаключительной позиции чужого хода в Т.

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

22.5.3. Объединение элементарных советов в правила
и таблицы советов

В языках советов Advice Language отдельные элементарные советы объединяются в законченную схему представления знаний с помощью следующей иерархии. Эле­ментарный совет является частью правила вывода. Совокупность правил вывода представляет собой таблицу советов. Множество таблиц советов структурируется в виде иерархической сети. Каждая таблица советов играет роль специализированного эксперта, позволяющего справиться с некоторой конкретной подпроблемой из всей этой проблемной области. Примером такого специализированного эксперта является таблица советов, содержащая знания о том, как поставить мат в шахматном энд-

Часть II, Применение языка Prolog в области искусственного интеллекта

шпиле "король и ладья против короля". Эта таблица вызывается на выполнение, ес­ли в игре возникает такое окончание.

Для простоты в данной главе рассматривается сокращенная версия языка Advice Language, в которой разрешается использовать только одну таблицу советов. Назовем эту версию Advice Language 0, или сокращенно AL0. Ниже описана структура языка AL0, синтаксис которого уже был приспособлен для удобства реализации на языке Prolog.

Программа на языке AL0 называется таблицей советов. Таблица советов - это упорядоченная коллекция правил вывода. Каждое правило имеет следующую форму: RuleName :: if Condition then AdviceList

где Condition — логическое выражение, которое состоит из имен предикатов, со­единенных логическими связками and, or, not, a AdviceList — список имен эле­ментарных советов. Ниже приведен пример правила "edgerule" (игра в углу), ко­торое относится к эндшпилю "король и ладья против короля". edge_rule ::

if their king on edge and our king close then [ mate in 2_F squeeze,

approach, keeproom, divide]. _ _ _

Это правило гласит, что если в текущей позиции король чужого игрока находится в углу, а король своего игрока приблизился к нему (или точнее, короли отстоят друг от Друга меньше чем на четыре клетки), то необходимо попытаться выполнить в ука­занном порядке приоритетов следующие элементарные советы: ".mate_irJ_2", "squeeze", "approach", "keeproon", "divide". В этом списке советов заданы эле­ментарные советы в уменьшающемся порядке важности поставленных целей: внача­ле попытаться поставить мат в два хода; если это невозможно, то попробовать "зажать" короля противника в углу, и т.д. Обратите внимание на то, что при соот­ветствующем определении операторов приведенное выше правило представляет собой синтаксически допустимое предложение Prolog.

Каждый элементарный совет можно определить в виде предложения Prolog в форме advice( AdviceName,

BetterGoal: HoldingGoal: Os_Move_Constraints : Them_Move_Constraints).

Цели — это выражения, состоящие из имен предикатов и логических связок and, or, not. Ограничения ходов также являются выражениями, состоящими из имен предикатов и связок and и then, где and имеет обычное логическое значение, a then предписывает упорядоченность. Например, ограничение хода в следующей форме: MCI then MC2

указывает — вначале рассмотреть те ходы, которые удовлетворяют ограничению МС1, а затем те, которые удовлетворяют МС2.

Например, элементарный совет по выполнению мата в 2 хода в эндшпиле "король и ладья против короля", оформленный с применением такого синтаксиса, имеет сле­дующий вид:

advice ( mate in 2, mate : not rooklost: _

(depth - 0) and legal then (depth - 2} and checkmove : (depth - 1) and legal).

В данном случае лучшая цель — mate (мат), а консервативная цель — not rooklcst (предотвращение потери ладьи). В ограничениях своего хода указано, что на глубине О (в текущей позиции на доске) следует попытаться выполнить любой до­пустимый ход, а затем на глубине 2 (на втором ходе своего игрока) пытаться выпол­нять только ходы с шахом. Глубина измеряется в полуходах. Ограничения чужого хода состоят в следующем: любой допустимый ход на глубине 1.

Глава 22. Ведение игры 545

Затем в процессе игры таблица советов используется в форме повторения до конца игры следующего основного цикла: формирование форсирующего дерева, после этого ведение игры в соответствии с этим деревом до тех пор, пока игра не выйдет за пре­делы данного дерева; формирование следующего форсирующего дерева и т.д. Форси­рующее дерево создается каждый раз следующим образом: берется текущая позиция на доске Pos и просматриваются одно за другим правила в таблице советов; для ка­ждого правила позиция Pos согласуется с предварительным условием этого правила, и поиск прекращается после обнаружения такого правила, что Pos удовлетворяет его предварительному условию. Теперь рассматривается список советов этого правила и последовательно обрабатываются элементарные советы из этого списка до тех пор, пока не будет найден элементарный совет, выполнимый в позиции Pos. Это приводит к получению форсирующего дерева, которое представляет собой подробное описание стратегии, реализуемой на игровой доске.

Следует отметить, что при этом важную роль играет упорядочение правил и эле­ментарных советов. Используемым становится такое первое правило, предваритель­ные условия которого соответствуют текущей позиции. Для любой возможной пози­ции в таблице советов должно существовать, по меньшей мере, одно правило, пред­варительное условие которого соответствует этой позиции. Таким образом выбирается список советов. После этого применяется первый найденный выполни­мый элементарный совет из этого списка.

Поэтому таблица советов главным образом представляет собой непроцедурную программу. Интерпретатор языка AL0 принимает на входе некоторую позицию и, выполняя действия над таблицей советов, вырабатывает форсирующее дерево, кото­рое определяет игру в данной позиции.