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

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

Рис. 13.7. Формулировка игровой задачи для игры двух лиц в форме И/ИЛИ- дерева; участники игры: 'игрок' и 'противник'.

13.3. Базовые процедуры поиска в И/ИЛИ-графах

В этом разделе нас будет интересовать какое-нибудь решение задачи независимо от его стоимости, поэтому проигнорируем пока стоимости связей или вершин И/ИЛИ-графа. Простейший способ организовать поиск в И/ИЛИ-графах средствами Пролога — это использовать переборный механизм, заложенный в самой пролог-системе. Оказывается, что это очень просто сделать, потому что процедурный смысл Пролога это и есть не что иное, как поиск в И/ИЛИ-графе. Например, И/ИЛИ-граф рис. 13.4 (без учета стоимостей дуг) можно описать при помощи следующих предложений:

а :- b.    % а - ИЛИ-вершина с двумя преемниками
а :- с.    % b и  с
b :- d, e. % b - И-вершина с двумя преемниками d и e
с :- h.
с :- f, g.
f :- h, i.
d. g. h.   % d, g и h - целевые вершины

Для того, чтобы узнать, имеет ли эта задача решение, нужно просто спросить:

?- а.

Получив этот вопрос, пролог-система произведет поиск в глубину в дереве рис. 13.4 и после того, как пройдет через все вершины подграфа, соответствующего решающему дереву рис. 13.4(b), ответит 'да'.

Преимущество такого метода программирования И/ИЛИ-поиска состоит в его простоте. Но есть и недостатки:

• Мы получаем ответ 'да' или 'нет', но не получаем решающее дерево. Можно было бы восстановить решающее дерево при помощи трассировки программы, но такой способ неудобен, да его и недостаточно, если мы хотим иметь возможность явно обратиться к решающему дереву как к объекту программы.

• В эту программу трудно вносить добавления, связанные с обработкой стоимостей.

• Если наш И/ИЛИ-граф — это граф общего вида, содержащий циклы, то пролог-система, следуя стратегии в глубину, может войти в бесконечный рекурсивный цикл.

Попробуем постепенно исправить эти недостатки. Сначала определим нашу собственную процедуру поиска в глубину для И/ИЛИ-графов.

Прежде всего мы должны изменить представление И/ИЛИ-графов. С этой целью введём бинарное отношение, изображаемое инфиксным оператором '--->'. Например, вершина а с двумя ИЛИ-преемниками будет представлена предложением

а ---> или : [b, с].

Оба символа '--->' и ':' — инфиксные операторы, которые можно определить как

:- op( 600, xfx, --->).
:- op( 500, xfx, :).

Весь И/ИЛИ-граф рис. 13.4 теперь можно задать при помощи множества предложений

а ---> или : [b, с].
b ---> и : [d, e].
с ---> и : [f, g].
e ---> или : [h].
f ---> или : [h, i].
цель( d). цель( g). цель( h).

Процедуру поиска в глубину в И/ИЛИ-графах можно построить, базируясь на следующих принципах:

Для того, чтобы решить задачу вершины В, необходимо придерживаться приведенных ниже правил:

(1) Если  В — целевая вершина, то задача решается тривиальным образом.

(2) Если вершина В имеет ИЛИ-преемников, то нужно решить одну из соответствующих задач- преемников (пробовать решать их одну за другой, пока не будет найдена задача, имеющая решение).

(3) Если вершина В имеет И-преемников, то нужно решить все соответствующие задачи (пробовать решать их одну за другой, пока они не будут решены все).

Если применение этих правил не приводит к решению, считать, что задача не может быть решена.

Соответствующая программа выглядит так:

решить( Верш) :-
 цель( Верш).
решить( Верш) :-
 Верш ---> или : Вершины, % Верш - ИЛИ-вершина
 принадлежит( Верш1, Вершины),
  % Выбор преемника  Верш1  вершины  Верш
 решить( Bepш1).
решить( Верш) :-
 Верш ---> и : Вершины,   % Верш - И-вершина
 решитьвсе( Вершины).
  % Решить все задачи-преемники
решитьвсе( []).
решитьвсе( [Верш | Вершины]) :-
 решить( Верш),
 решитьвсе( Вершины).

Здесь принадлежит — обычное отношение принадлежности к списку.

Эта программа все еще имеет недостатки:

• она не порождает решающее дерево, и

• она может зацикливаться, если И/ИЛИ-граф имеет соответствующую структуру (циклы).

Программу нетрудно изменить с тем, чтобы она порождала решающее дерево. Необходимо так подправить отношение решить, чтобы оно имело два аргумента:

решить( Верш, РешДер).

Решающее дерево представим следующим образом. Мы имеем три случая:

(1) Если Верш — целевая вершина, то соответствующее решающее дерево и есть сама эта вершина.

(2) Если Верш — ИЛИ-вершина, то решающее дерево имеет вид

Верш ---> Поддерево

где Поддерево — это решающее дерево для одного из преемников вершины Верш.

(3) Если Верш — И-вершина, то решающее дерево имеет вид