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


              

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

        то [мат_2, потеснить, приблизиться,
                                                        сохранить_простр, отделить].

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

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

        совет( ИмяСовета,
                    ГлавнаяЦель:
                    ЦельПоддержка:
                    ХодыИгрока:
                    ХодыПротивника).

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

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

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

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

        совет( мат_2,
                    мат:
                    не потеря_ладьи:
                    (глубина = 0) и разреш затем
                    (глубина = 2) и ход_шах :
                    (глубина = 1) и разреш ).

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

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

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

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









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