Назад | Содержание| Вперёд 15. 5. Знания о типовых ситуациях имеханизм "сов...

Назад | Содержание| Вперёд

15. 5. Знания о типовых ситуациях имеханизм "советов"

В этом разделе рассматривается методпредставления знаний о конкретной игре сиспользованием семейства Языков Советов. ЯзыкиСоветов (Advice Languages) дают возможность пользователюдекларативным способом описывать, какие идеиследует использовать в тех или иных типовыхситуациях. Идеи формулируются в терминах целей исредств, необходимых для их достижения.Интерпретатор Языка Советов определяет припомощи перебора, какая идея "работает" вданной ситуации.

15. 5. 1. Цели и ограничения на ходы

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

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

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

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

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

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

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

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

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

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

15. 5. 2. Выполнимость совета

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

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

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

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

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

корень дерева Т - позиция Р;

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

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

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

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

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

15. 5. 3. Правила и таблицы советов

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

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

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

ИмяПравила: если Условие то СписокСоветов

Условие - это логическоевыражение, состоящее из имен предикатов,соединенных между собой логическими связками и,или, не. СписокСоветов- список имен элементарных советов. Приведемпример правила под названием "правило_края"из окончания "король и ладья против короля":

правило_края:

есликороль_противника_на_краю и короли_рядом

то [мат_2, потеснить,приблизиться,

сохранить_простр, отделить].

В этом правиле говорится: если в текущейпозиции король противника находится на краюдоски, а король игрока расположен близко к королюпротивника (точнее, расстояние между королямименьше четырех клеток), то попытаться выполнить вуказанном порядке предпочтения следующиесоветы: "мат_2", "потеснить","приблизиться", "сохранить_простр","отделить". Элементарные советы расположеныв порядке убывания их "притязаний" на успех:сначала попытаться поставить мат в два хода, еслине получится - "потеснить" короля противникав угол и т.д. Обратите внимание на то, что присоответствующем определении операторов нашеправило станет синтаксически корректнымпредложением Пролога.

Для представления элементарных советов в видепрологовских предложений предназначен еще одинформат:

совет( ИмяСовета,

ГлавнаяЦель:

ЦельПоддержка:

ХодыИгрока:

ХодыПротивника).

Цели представляются как выражения, состоящиеиз имен предикатов и логических связок и, или, не. Ограниченияна ходы сторон - это тоже выражения, состоящие изимен предикатов и связок и и затем: связка и имеет обычныйлогический смысл, а затем задаетпорядок. Например, ограничение, имеющее вид

Огр1 затем Огр2

означает: сначала рассмотреть ходы,удовлетворяющие ограничению Oгp1, азатем - ходы, удовлетворяющие Огр2.

Например, элементарный совет, относящийся кмату в два хода в окончании "король и ладьяпротив короля", записанный в такойсинтаксической форме, имеет вид:

совет( мат_2,

мат:

не потеря_ладьи:

(глубина = 0) и разреш затем

(глубина = 2) и ход_шах :

(глубина = 1) и разреш ).

Здесь главная цель - мат,цель-поддержка не потеря_ладьи.Ограничение на ходы игрока означает: на глубине 0(т. е. в текущей позиции) попробовать любойразрешенный ход и затем на глубине 2 (следующийход игрока) пробовать только ходы с шахом.Глубина измеряется в полуходах. Ограничение находы противника: любой разрешенный ход наглубине 1.

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

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

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

Назад | Содержание| Вперёд

Оглавление