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

Основное понятие Языка Советов — "элементарный совет". Элементарный совет содержит указание о том, что следует делать (или пытаться делать) в некоторой типовой ситуации. Совет выражается в терминах тех целей , которые необходимо достичь, и тех средств , которые следует применять для этого. Мы называем участников игры "игроком" и "противником"; совет всегда относится к "игроку". Каждый элементарный совет имеет следующие четыре составные части:

• главная цель : цель, к которой нужно стремиться;

• цель-поддержка : цель, которая должна постоянно удовлетворяться в процессе достижения главной цели;

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

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

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

• главная цель : провести пешку;

• цель-поддержка : не потерять пешку;

• ходы игрока : продвигать пешку;

• ходы противника : приближаться королем к пешке.

Мы говорим, что элементарный совет выполним в данной позиции, если игрок может форсированным образом достигнуть главной цели, указанной в совете, при условии, что:

(1) ни разу не нарушается цель-поддержка;

(2) все ходы игрока удовлетворяют наложенным на них ограничениям;

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

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

• корень дерева T — позиция P;

• все позиции из T удовлетворяют цели-поддержке;

• все терминальные позиции из T удовлетворяют главной цели (что, однако, неверно ни для одной внутренней вершины);

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

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

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

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

Мы рассмотрим здесь упрощенную версию Языка Советов, допускающую только одну таблицу советов. Будем называть эту версию Язык Советов 0 или, для краткости, AL0 (Advice Language 0). Ниже описывается структура языка AL0, синтаксически специально приспособленная для удобной реализации на Прологе.

Программа на AL0 называется таблицей советов . Таблица советов представляет из себя упорядоченное множество "если-то"-правил. Каждое правило имеет вид: