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


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

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

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


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

Будем использовать следующие отношения:

Определим соответствующие типы рёбер:
edges @on, @has, @want                            // находится в месте, иметь объект, хотеть съесть
edges @link                                       // два места связаны дорогой

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

var Sen = GRAPH("Sen")                            // создаём граф абстрактных классов
GRAPH = 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  = True               // принадлежность к классам isa
[$w,$g,$c].@isa.Sen=>$animal = True
[$1,$2]   .@isa.Sen=>$place  = True

$w.@want.$g = $g.@want.$c    = True               // кто кого хочет

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

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

for X in X.isa(Sen=>$human) | X.isa(Sen=>$animal):
   X.@on.$1 = True                                // все в месте $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.@has.Z)    : return False       // H уже кого-то носит
   var P = place(G, H)                            // место, где находится человек H
   if A.@on.P != True        : return False       // H и A в разных местах

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

   H.@has.Z = Undef                               // человек теперь не имеет Z
   Z.@on.(place(G, H)) = True                     // Z там же, где человек
   return True
}
Обратим внимание на строку H.@has.Z = Undef. Можно было бы написать False, но тогда в графе начнут появляться False рёбра @has. Это приведёт к росту различных состояний, которые по факту являются одним и тем же состоянием. Поясним это на примере. Создадим копию 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 = True                                // переезжаем в 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.@has.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 = True                        // объявляем его человеком
$s.@on.$1 = True                                  // отправляем на первое место

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.