DemonScript: Волк, коза и капуста

Постановка задачи

Решаем стандартную головоломку о перевозке голодных волка, козы и капусты из места $1 в место $2. Если волк и коза находятся в одном месте без фермера, то волк съедает козу. Аналогичная, ситуация для козы и капусты. Первоначально все объекты находятся в месте $1. Фермеру необходимо перевезти волка, козу и капусту в место $2 без потерь. Для перевозки он может взять только один объект.

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

Знания об объектах

Будем использовать следующие отношения:
X on Y означает, что объект X расположен в месте Y;
X hold Y - объект X (это всегда будет человек) имеет ("держит" в руках) объект Y (это будет животное);
X want Y - истинно, если животное X готово съесть животное Y;
X link Y - истинно, если из места X есть дорога в место Y.
Определим соответствующие типы рёбер: 

edges on, hold, want                              // находится в месте, иметь объект, хотеть съесть
edges link                                        // два места связаны дорогой

Для удобства введём три абстрактных класса: людей, животных (к которым будем относить и капусту) и класс мест. Эти классы храним в графе Sen: 

var Sen = GRAPH("Sen")                            // создаём граф абстрактных классов
Sen.nodes $human, $animal, $place                 // человек, животное, место

global Sen                                        // граф будет доступен в демонах

Создадим граф начального состояния Start с узлами, соответствующими фермеру, животным и двум местам: 

var Start = GRAPH("Start")                        // граф начального состояния
GRAPH = Start                                     // делаем текущим и добавляем узлы:
nodes f, w, g, c                                  // фермер, волк, коза, капуста
nodes $1, $2                                      // различные места мира

Start.verbose(0)                                  // не будет вывода информации об изменении рёбер
Зададим "знания" о сущностях мира (принадлежность к классам, кто кого готов съесть и наличие дорог между местами): 
[f]     isa Sen=>$human;                          // принадлежность к классам isa
[w,g,c] isa Sen=>$animal; 
[$1,$2] isa Sen=>$place;

w  want g;   g  want c;                           // кто кого хочет
$1 link $2;  $2 link $1;                          // геометрия мира: 1<->2
Дальнейший код универсален и работа скрипта будет полностью зависеть от сделанных выше определений. Можно увеличить число мест, животных или фермеров, определив отношения между ними.

Поместим всех людей и животных в начальное положение: 

for X in X.isa(Sen=>$human) | X.isa(Sen=>$animal):
   X on $1;                                       // все в месте $1

Основные действия

Определим вспомогательного демона, который возвращает положение (место) объекта X в состоянии, описываемом графом G. В нём используется функция exists, которая ищет первое Z для которого условие, записанное во втором аргументе функции, будет истинным. Если такого Z нет, демон вернёт логическое значение Undef (все демоны так поступают, если не сработал ни один return): 

def place(G, X)
{
   GRAPH = G
   if exists(Z, X on Z) : return Z
}

Основным действуюшим агентом в задаче является человек (фермер в базовой постановке). Он может взять животное, положить его и перейти в другое место. Каждое действие опишем демоном, который будет возвращать логическое значение: True - если действие может быть выполнено (и оно тогда совершается) или False - если действие выполнено быть не может (оно тогда и не делается)

Демон взятия животного A человеком H в состоянии G имеет вид: 

def take(G, H, A)
{
   GRAPH = G
   if exists(Z, H hold Z)  : return False         // H уже кого-то носит
   var P = place(G, H)                            // место, где находится человек H
   if (A on P) != True     : return False         // H и A в разных местах

   H hold A;                                      // человек берёт A
   A on P  = Undef                                // A уже не в P (а у человека)
   return True
}
Демон, который избавляет человека H от его ноши в состоянии G имеет вид: 
def put(G, H)
{
   GRAPH = G
   if !exists(Z, H hold Z)  : return False        // никого не носит

   H hold Z = Undef                               // человек теперь не имеет Z
   var P = place(G, H) 
   Z on P;                                        // Z там же, где человек
   return True
}
Обратим внимание на строку H hold Z = Undef. Можно было бы написать False, но тогда в графе начнут появляться False рёбра hold. Это приведёт к росту различных состояний, которые по факту являются одним и тем же состоянием. Поясним это на примере. Создадим копию G начального состояния Start. Пусть фермер f берёт и сразу кладёт волка w: 
 
var G = Start.copy()
take(G, f, w); put(G, f)
out G == Star
Очевидно, что ничего не поменялось и при наличии Undef графы будут равны (G==Start истинно). Однако, если Undef заменить на False, то сравнение вернёт ложь. Стоит вывести структуру графов Start и G в обоих случаях.

Демон перемещения человека H в место P2 чуть более сложный. Он не допускает этого действия, если в покидаемом месте остаются животные, готовые друг друга съесть и там нет других людей: 

def move(G, H, P2)
{
   GRAPH = G
   var P1 = place(G, H)                           // где сейчас находится человек H
   if P1 == P2             : return False         // уже тут и находится
   if (P1 link P2) != True : return False         // нет пути P1 -> P2

   // если людей больше в P1 нет:
   if !exists(F, F.isa(Sen=>$human) & (F on P1) & F != H) :             
      for A in A.isa(Sen=>$animal){               // по всем носимым животным
         if (A on P1) != True : continue           
         for B in (A want B) & (B on P1) : 
            return False                          // нельзя оставлять животных и их жертв
      }

   H on P1 = Undef;                               // покидаем P1
   H on P2;                                       // переезжаем в P2
   return True
}

Генератор переходов

При поиске решения нам потребуется создавать все возможные состояния (графы) в которые можно перейти из состояния G. Этим занимается демон all_actions(G), который возвращает массив графов, совершая последовательно все разрешённые в состоянии G действия. После каждого успешного действия по .copy создаётся граф Next в котором осуществляется очередное действие. Этот граф добавляется в массив Grpahs, который возвращает демон. В имени графа Next (метод .name) мы сохраняем действие, накапливая их последовательность: 

def all_actions(G)
{
   GRAPH = G
   var Graphs = []
   var Next = G.copy(); 
   for H in H.isa(Sen=>$human) {                  // по всем людям
      if put(Next, H) {                           // может положить, что имеет
         Next.name(Next.name()+";"+H.string()+".p");  
         Graphs.push(Next)
         Next = G.copy()
      }
      for A in A.isa(Sen=>$animal) :              // по всем животным
         if take(Next, H, A) {                    // его можно взять
            Next.name(Next.name()+";"+H.string()+".t."+A.string()); 
            Graphs.push(Next)
            Next = G.copy()
         }
      for P in P.isa(Sen=>$place) :               // по всем местам
         if move(Next, H, P) {                    // туда можно перейти
           Next.name(Next.name()+";"+H.string()+".m."+P.string());  
           Graphs.push(Next)
           Next = G.copy()
         }
      }
   return Graphs
}

Последний вспомогательный демон будет выяснять, является ли состояние G целевым. Это происходит, если все люди и животные собрались на финальном месте $2 и люди совершили действие put (выложили животное) 

def target_state(G)
{
   GRAPH = G
   for X in X.isa(Sen=>$human) | X.isa(Sen=>$animal) {
      if (X on $2) != True  : return False        // не все на финальном месте
      if exists(Z, X hold Z): return False        // некоторые не положены
   }   
   return True
}

Поиск решения

Поиск решения головоломки проведём в ширину. Это не самый эффективный метод, однако он гарантированно найдёт наилучшее решение. Как обычно, при помощи массивов, вводим две очереди. В очереди Open будем хранить состояния в которых дальше планируется совершить действия. В очереди Close сохраняем все состояния в которых мы уже были. Начинаем поиск со стартового состояния Start: 

def solver(Start)
{
   var Open  = []                                 // очередь состояний для обследования
   var Close = []                                 // состояния в которых уже были
   Open.push(Start)                               // помещаем стартовое
   Close.push(Start)                               
   while !Open.empty() {                          // пока очередь не пустая 
      var G = Open.pop()                          // извлекаем из конца

      var Gs = all_actions(G)                     // графы после всех возможных действий
      for Gi in Gs {                              // бежим по ним

         if target_state(Gi) {                    // это целевое состояние
            out "Close:",Close.size()
            return Gi                             // конец поиска
         }
         if Close.is(Gi) :                        // в этом состоянии уже были
            continue
         Open.unshift(Gi)                         // в начало очереди (поиск в ширину)
         Close.push(Gi)                           // запоминаем, что уже были
      }
   }
}

Тестирование

Запустим решатель для начального состояния: 

var Finish = solver(Start)    
out  Finish==Undef ? "Can't find solution" : Finish.name()
На экране появится: 
f.t.g;f.m.$2;f.p;f.m.$1;f.t.w;f.m.$2;f.p;
f.t.g;f.m.$1;f.p;f.t.c;f.m.$2;f.p;f.m.$1;f.t.g;f.m.$2;f.p
Это означает, что фермер берёт козу , едет в место $2, кладёт её и т.д.

Можно добавить ещё одного фермера: 

GRAPH = Start                                     // делаем текущим Start
nodes s                                           // добавляем в него узел
$s isa Sen=>$human;                               // объявляем его человеком
$s on $1;                                         // отправляем на первое место

Finish = solver(Start)                            // запускаем решатель
out  Finish.name()
Результат будет несколько короче: 
f.t.w;f.m.$2;f.p;f.m.$1;f.t.g;f.m.$2;f.p;$s.t.c;$s.m.$2;$s.p

Если стоит цель найти не одно, решение, можно в цикле for демона solver заменить return Gi на 

out Gi.name(); Close.push(Gi); continue
Впрочем, все возможные решения не будут найдены, так как в Close мы сохраняем состояния в которых мы уже были. Однако, попасть в данное состояние можно различным образом. Если мы уже попадали в состояние, то все другие способы попадания в него будут блокированы. Ситуацию можно несколько изменить, если упомянутые выше Undef заменить на False (но не в демоне put, который приводит к слишком большому ветвлению). Впрочем, классическая задача имеет только одно решение.

Полный код этого примера находится в файле wolf.ds.