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

(4) перейти в другое место.

Рис. 2.12. Исходное состояние обезьяньего мира, представленное в виде структурного объекта. Его четыре компоненты суть горизонтальная позиция обезьяны, вертикальная позиция обезьяны, позиция ящика, наличие или отсутствие у обезьяны банана.

Не всякий ход допустим при всех возможных состояниях мира. Например, ход 'схватить' допустим, только если обезьяна стоит на ящике прямо под бананом (т.е. в середине комнаты) и еще не имеет банана. Эти правила можно формализовать в Прологе в виде трехместного отношения ход:

ход( Состояние1, М, Состояние2)

Три аргумента этого отношения определяют ход, следующим образом:

Состояние1 --------> Состояние2
                М

Состояние1 это состояние до хода, М — выполняемый ход, и Состояние2 — состояние после хода.

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

ход( состояние( середина, наящике, середина, неимеет),
           % Перед ходом
 схватить, % Ход
 состояние( середина, наящике, середина, имеет) ).
           % После хода

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

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

ход( состояние( P1, наполу, В, H),
 перейти( P1, Р2), % Перейти из P1 в Р2
 состояние( Р2, наполу, В, H) ).

Заметим, что в этом предложении делается много утверждений и, в частности:

• выполненный ход состоял в том, чтобы 'перейти из некоторой позиции P1 в некоторую позицию Р2';

• обезьяна находится на полу, как до, так и после хода;

• ящик находится в некоторой точке В, которая осталась неизменной после хода;

• состояние 'имеет банан' остается неизменным после хода.

Рис. 2.13. Рекурсивная формулировка отношения можетзавладеть.

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

Два других типа ходов: 'подвинуть' и 'залезть' — легко определить аналогичным способом.

Главный вопрос, на который должна ответить наша программа, это вопрос: 'Может ли обезьяна, находясь в некотором начальном состоянии S, завладеть бананом?' Его можно сформулировать в виде предиката

можетзавладеть( S)

где аргумент S — состояние обезьяньего мира. Программа для можетзавладеть может основываться на двух наблюдениях:

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

можетзавладеть( состояние( _, _, _, имеет) ).

(2) В остальных случаях требуется один или более ходов. Обезьяна может завладеть бананом в любом состоянии S1, если для него существует ход из состояния P1 в некоторое состояние S2, такое, что, попав в него, обезьяна уже сможет завладеть бананом (за нуль или более ходов). Этот принцип показан на рис. 2.13. Прологовская формула, соответствующая этому правилу, такова:

можетзавладеть( S1) :-
 ход( S1, М, S2),
 можетзавладеть( S2).

Теперь мы полностью завершили нашу программу, показанную на рис. 2.14.

Формулировка можетзавладеть рекурсивна и совершенно аналогична формулировке отношения предок из гл. 1 (ср. рис. 2.13 и 1.7). Этот принцип используется в Прологе повсеместно.

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

?- можетзавладеть( состояние( удвери, наполу, уокна, неимеет) ).

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

% Разрешенные ходы
ход( состояние( середина, на ящике, середина, неимеет),
 схватить,           % Схватить банан
 состояние( середина, наящике, середина, имеет)).
ход( состояние( P, наполу, P, H),
 залезть,            % Залезть на ящик
 состояние( P, наящике, P, H) ).
ход( состояние( P1, наполу, P1, H),
 подвинуть( P1, Р2), % Подвинуть ящик с P1 на Р2
 состояние( Р2, наполу, Р2, H) ).
ход( состояние( P1, наполу, В, H),
 перейти( P1, Р2),   % Перейти с P1 на Р2
 состояние( Р2, наполу, В, H) ).
% можетзавладеть(Состояние): обезьяна может завладеть
% бананом, находясь в состоянии Состояние
можетзавладеть( состояние( -, -, -, имеет) ).
% может 1:  обезьяна уже его имеет
можетзавладеть( Состояние1) :-
 % может 2:  Сделать что-нибудь, чтобы завладеть им
 ход( Состояние1, Ход, Состояние2),