Ищем убийцу на Прологе

Original author: Ahmed Youssef
  • Translation
Каждое воскресенье в нашей компании принято устраивать весёлые викторины, это одна из них.

Загадка


Чтобы найти убийцу мистера Бодди, нужно узнать, где находился каждый человек и какое оружие было в комнате. Подсказки разбросаны по всей викторине (вы не можете ответить на первый вопрос, пока не прочитаете все десять).

  • Для начала, представим подозреваемых. Есть три мужчины (Джордж, Джон, Роберт) и три женщины (Барбара, Кристина, Иоланда). Каждый человек находится в отдельной комнате (ванная, столовая, кухня, гостиная, кладовая, кабинет). В каждой комнате найдено подозрительное оружие (сумка, огнестрельное оружие, газ, нож, яд, верёвка). Вопрос: кого нашли на кухне?
  • Подсказка 1. При мужчине на кухне нет ни верёвки, ни ножа, ни сумки. Оружие не является огнестрельным. Вопрос: какое оружие найдено на кухне?

  • Подсказка 2. Барбара либо в кабинете, либо в ванной, а Иоланда — в другой комнате из двух названных. В какой комнате нашли Барбару?
  • Подсказка 3. Человек с сумкой — это ни Барбара, ни Джордж, и он не был ни в ванной, ни в столовой. У кого была сумка?
  • Подсказка 4. Женщина с верёвкой найдена в кабинете. Кто это?
  • Подсказка 5. Оружие в гостиной принадлежит либо Джону, либо Джорджу. Какое оружие в гостиной?
  • Подсказка 6. Ножа не было в столовой. Где был нож?
  • Подсказка 7. Иоланды не было ни в кабинете, ни в кладовой с соответствующим оружием для этих комнат. Какое оружие у Иоланды?
  • Подсказка 8. У Джорджа найдено огнестрельное оружие. В какой комнате?
  • Было обнаружено, что мистера Бодди отравили газом в кладовой. Подозреваемый в той комнате был убийцей. Кто же это?

Я тащусь от таких головоломок (вообще-то почти от любых головоломок). Они могли бы занять часы и часы размышлений, но всегда на помощь приходит Prolog! Посмотрим, как он помогает решить такие задачи на рассуждения.

Prolog 101


Установка SWI-Prolog


~> swipl
Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 6.6.6)
Copyright (c) 1990-2013 University of Amsterdam, VU Amsterdam
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.
 
For help, use ?- help(Topic). or ?- apropos(Word).
 
?- write('Hello, World!').
Hello, World!
true.
?- write('Hello,'), nl, write('world').
Hello,
world
true.
?- X is 3*4 + 2.
X = 14.

  • swipl — программа-интерпретатор Prolog
  • write называется функтором, а представление write/1 означает, что он принимает 1 аргумент (та же концепция в Erlang и Elixir для добавления количества аргументов к имени функции)
  • nl используется для печати новой строки
  • последовательность команд разделяется запятыми, которые также заменяют оператор AND
  • за оператором присвоения is следует математическое выражение
  • переменные пишутся заглавными X, а не x

База знаний


Суть Prolog — в констатации фактов, составлении фактов и их запросе.

Создание файла hello.pl:

friend(john, julia).
friend(john, jack).
friend(julia, sam).
friend(julia, molly).
 
loves(john, julia).
loves(julia, sam).
loves(sam, julia).
 
male(brad).
male(john).
male(jim).
male(alfred).
female(marry).
child(brad, alfred).
child(john, jim).
child(john, marry).

  • для загрузки используем [hello].: обратите внимание на точку в конце
  • listing перечисляет все факты в базе знаний

?- [hello].
% hello compiled 0.00 sec, 3 clauses
true.
 
?- listing(friend).
friend(john, julia).
friend(john, jack).
friend(julia, sam).
friend(julia, molly).
 
true.
 
?- listing(loves).
loves(john, julia).
loves(julia, sam).
loves(sam, julia).
 
true.

Запрос фактов


После изложения фактов в базе знаний можем пойти дальше и задавать вопросы об истинности фактов, а также о том, какие выводы можно из них сделать.

?- friend(john, julia).
true .
 
?- friend(john, jack).
true.
 
?- loves(john, julia).
true.
 
?- loves(john, sam).
false.

Можем составлять и более сложные вопросы. Например, кто дружит с Джоном или кто любит Джулию.

?- friend(john, Who).
Who = julia ;
Who = jack.

?- listing(child).
child(brad, alfred).
child(john, jim).
child(john, mary).
 
true.
 
?- child(john, X).
X = jim ;
X = mary.

Джон во френдзоне?


Мы установили дружественные отношения Джона с Джулией (friend(john, julia)), но для Prolog это не значит, что Джулия дружит с Джоном: нужно добавить ещё один факт friend(julia, john). Также мы уже указали, у кого какие дети, и явно не хотим дублировать код, отдельно указывая родителей каждого ребёнка. Мы не хотим писать что-то вроде

child(brad, alfred).
child(john, jim).
child(john, mary).

parent(alfred, brad).
parent(jim, john).
parent(mary, john).

Prolog помогает избежать дублирования с помощью правил логического заключения:

rule :- stmt1, stmt2,...

Правило истинно, если все внутренние утверждения истинны (перечислены и логически сложены через запятую).

friend(X, Y) :- friend(Y,X).
parent(X, Y) :- child(Y,X).
father(X, Y) :- child(Y,X), male(X).
mother(X, Y) :- child(Y,X), female(X).
friendzoned(X) :- loves(X, Y), \+ loves(Y,X).

  • правило friend(X,Y) справедливо при friend(Y,X)
  • parent(X,Y) справедливо при установленном child(Y,X)
  • father(X,Y) справедливо при установленных parent(X,Y) и male(X)
  • mother(X,Y) справедливо при установленных parent(X,Y) и female(X)
  • friendzoned(X) справедливо, если X любит SOMEONE Y, а Y не любит X (заметили скрытую переменную Y?)

?- friend(julia, john).
true .
?- male(jim).
true.
 
?- parent(jim,X).
X = john.
 
?- father(jim, X).
X = john.
 
?- mother(X, john).
X = marry.
 
?- mother(marry,X).
X = john.
 
?- mother(marry, john).
true.

?- loves(julia, X).
X = sam.
 
?- friendzoned(julia).
false.
 
?- friendzoned(john).
true.

Хорошо, теперь у нас есть все необходимые знания. Потренируемся на раскраске карты.

Раскраска карты


Начнём с известной математической проблемы. Требуется, чтобы ни у каких смежных областей не было одинакового цвета.



Поэтому рассуждения должны быть такие, у нас есть три вещи:

  1. Переменные — области, которые мы хотим раскрасить: A, B, С, D, Е.
  2. Домен — диапазон значений, которые можно присвоить переменным: красный, синий, зелёный.
  3. Ограничение, что смежные области не могут быть одинакового цвета.

Домен


Определим домен наших областей (красный, зелёный, синий).

color(red).
color(green).
color(blue).

Это всё.

Спрашиваем решение


colorify(A,B,C,D,E) :-
   
    color(A), color(B), color(C), color(D), color(E),
    \+ A=B, \+ A=C, \+ A=D, \+ A=E,
    \+ B=C, \+ C=D, \+ D=E.

Здесь мы определяем решение как правило colorify с пятью переменными А, B, С, D, Е, а внутри правила назначаем доменный цвет (красный, синий, зелёный) для переменных и устанавливаем ограничения, что А не равно B, не равно С… и т. д.

\+ X=Y означает, что X не равно Y

Prolog продолжит генерировать значения, пока не найдёт вариант, удовлетворяющий правилу с учётом ограничений.

?- [mapcoloring]
|    .
true.

?- colorify(A,B,C,D,E)
|    .
A = red,
B = D, D = green,
C = E, E = blue ;
A = red,
B = D, D = blue,
C = E, E = green ;
A = green,
B = D, D = red,
C = E, E = blue ;
A = green,
B = D, D = blue,
C = E, E = red ;
A = blue,
B = D, D = red,
C = E, E = green ;
A = blue,
B = D, D = green,
C = E, E = red 

color(red).
color(green).
color(blue).

colorify(A,B,C,D,E) :-
    color(A), color(B), color(C), color(D), color(E),
    \+ A=B, \+ A=C, \+ A=D, \+ A=E,
    \+ B=C, \+ C=D, \+ D=E.

… но мы здесь не картинки раскрашиваем, а ищем убийцу.

Убийство


Для начала, представим подозреваемых. Есть три мужчины (Джордж, Джон, Роберт) и три женщины (Барбара, Кристина, Иоланда). Каждый человек находится в отдельной комнате (ванная, столовая, кухня, гостиная, кладовая, кабинет). В каждой комнате найдено подозрительное оружие (сумка, огнестрельное оружие, газ, нож, яд, верёвка).

Кого нашли на кухне?

Домен


Из этого можно сделать вывод, что у нас пять доменов: man, woman, person или подозреваемый, location и weapons, а наши переменные (A, B, C, D, E, F) должны представлять и человека, и место, и оружие с некоторыми ограничениями, которые будут выявлены в предстоящих подсказках.

man(george). man(john). man(robert).
woman(barbara). woman(christine). woman(yolanda).
person(X):- man(X).
person(X):- woman(X).
location(bathroom). location(dining). location(kitchen). location(livingroom). location(pantry). location(study).
weapon(bag). weapon(firearm). weapon(gas). weapon(knife). weapon(poison). weapon(rope).

Правило uniq_ppl генерирует уникальные значения для наших переменных.

uniq_ppl(A,B,C,D,E,F):- person(A), person(B), person(C), person(D), person(E), person(F),  \+A=B, \+A=C, \+A=D, \+A=E, \+A=F, \+B=C, \+B=D, \+B=E, \+B=F, \+C=D, \+C=E, \+C=F, \+D=E, \+D=F, \+E=F.

Решение


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

Обратите внимание, что у нас по-прежнему шесть подозреваемых.

Вступление


murderer(X) :-
   uniq_ppl(Bathroom, Dining, Kitchen, Livingroom, Pantry, Study),
   uniq_ppl(Bag, Firearm, Gas, Knife, Poison, Rope),

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

  • Ванная — оно же подозреваемый (мужчина или женщина) в ванной
  • Огнестрельное оружие — оно же подозреваемый (мужчина или женщина) с огнестрельным оружием
  • и так далее… можете представить это как решётку

Теперь продолжаем добавлять ограничения после последней запятой в правиле murderer.

Подсказка 1


При мужчине на кухне нет верёвки, ножа или сумки. Оружие не является огнестрельным. Какое оружие найдено на кухне?

% 2. Clue 1: The man in the kitchen was not found with the rope, knife, or bag.
% Which weapon, then, which was not the firearm, was found in the kitchen?

   man(Kitchen), 
   \+Kitchen=Rope, \+Kitchen=Knife, \+Kitchen=Bag, \+Kitchen=Firearm,

Здесь мы говорим, что переменная Kitchen удовлетворяет факту man (определено в нашем домене), и заявляем, что кем бы ни был человек на кухне, у него нет ничего из перечисленного: Rope, Knife, Bag, Firearm.

Подсказка 2


Подсказка 2. Барбара либо в кабинете, либо в ванной, а Иоланда — в другой комнате из двух названных. В какой комнате нашли Барбару?

Таким образом, мы можем сказать, что woman есть и в кабинете, и в ванной, И это не Кристина, а также вычёркиваем остальные варианты для Барбары и Иоланды (кухня, столовая, гостиная, кладовая).

% % 3. Clue 2: Barbara was either in the study or the bathroom; Yolanda was in the other.
% % Which room was Barbara found in?
    woman(Bathroom), woman(Study), \+christine=Bathroom, \+christine=Study, 
    \+barbara=Dining, \+barbara=Kitchen, \+barbara=Livingroom, \+barbara=Pantry,

Подсказка 3


Человек с сумкой — это ни Барбара, ни Джордж, и он не был ни в ванной, ни в столовой. У кого была сумка?

% % 4. Clue 3: The person with the bag, who was not Barbara nor George, was not in the bathroom nor the dining room.
% % Who had the bag in the room with them?

    \+barbara=Bag, \+george=Bag, \+Bag=Bathroom, \+Bag=Dining,

Подсказка 4


Женщина с верёвкой найдена в кабинете. Кто это?

% % 5. Clue 4: The woman with the rope was found in the study.
% % Who had the rope?
   
  woman(Rope), Rope=Study,  

Подсказка 5


Подсказка 5. Оружие в гостиной принадлежит либо Джону, либо Джорджу. Какое оружие в гостиной?

man in Livingroom
Livingroom isn’t robert
% % 6. Clue 5: The weapon in the living room was found with either John or George.
% % What weapon was in the living room?
    man(Livingroom), \+Livingroom=robert,

Подсказка 6


Ножа не было в столовой. Где был нож?

% % 7. Clue 6: The knife was not in the dining room.
% % So where was the knife?
    \+Knife=Dining,

Подсказка 7


Подсказка 7. Иоланды не было ни в кабинете, ни в кладовой. Какое оружие в комнате у Иоланды?

% % 8. Clue 7: Yolanda was not with the weapon found in the study nor the pantry.
% % What weapon was found with Yolanda?
    \+yolanda=Pantry, \+yolanda=Study,

Подсказка 8


У Джорджа найдено огнестрельное оружие.

% % 9. Clue 8: The firearm was in the room with George.
% % In which room was the firearm found?
    Firearm=george,

Подсказка 9


Было обнаружено, что мистера Бодди отравили газом в кладовой. Подозреваемый в той комнате был убийцей. Кто это?

% % 10. It was discovered that Mr. Boddy was gassed in the pantry. The suspect found in that room was the murderer.
% % Who, then, do you point the finger towards?
Pantry=Gas, Pantry=X, write("KILLER IS :"), write(X), nl, writeanswers(Bathroom, Dining, Kitchen, Livingroom, Pantry, Study, Bag, Firearm, Gas, Knife, Poison, Rope).

Устанавливаем соответствие для газа, кладовой и убийцы, затем используем write для вывода ответов writeanswers.

writeanswers(Bathroom, Dining, Kitchen, Livingroom, Pantry, Study, Bag, Firearm, Gas, Knife, Poison, Rope):- 
  write("Bathroom: "), write(Bathroom), nl,
  write("Dining: "), write(Dining), nl,
  write("Livingroom: "), write(Livingroom), nl, 
  write("Pantry: "), write(Pantry), nl,
  write("Study: "), write(Study), nl,
  write("Kitchen: "), write(Kitchen), nl,

  write("Knife: "), write(Knife), nl,
  write("Gas: "), write(Gas), nl,
  write("Rope: "), write(Rope), nl, 
  write("Bag: "), write(Bag), nl,
  write("Poison: "), write(Poison), nl,
  write("Firearm: "), write(Firearm), nl.

Кто убийца?


 ?- [crime2].
true.
?- murderer(X).
KILLER IS :christine
Bathroom: yolanda
Dining: george
Livingroom: john
Pantry: christine
Study: barbara
Kitchen: robert
Knife: yolanda
Gas: christine
Rope: barbara
Bag: john
Poison: robert
Firearm: george
X = christine ;

Код опубликован здесь. Вероятно, он мог быть намного лучше, поскольку я не эксперт в Прологе :)
  • +30
  • 7.5k
  • 9
Support the author
Share post

Comments 9

    +1
    Интересно, что факты «location» и «weapon» не понадобились вообще для итогового решения, а оказались в именах переменных.
    PS: сколько времени занял подсчет? Меньше секунды или больше?
      0
      Таким образом, мы можем сказать, что woman есть и в кабинете, и в ванной, И это не Кристина, а также вычёркиваем остальные варианты для Барбары и Иоланды (кухня, столовая, гостиная, кладовая).

      При этом в коде Иоланду вычеркнуть забыли!
        +1
        Кстати ещё. В на сколько я помню, в институте, когда нам давали пролог, было требование: Условия должны быть записаны именно так, как они звучат в задаче. Тут это правило нарушено. например:
        % % 6. Clue 5: The weapon in the living room was found with either John or George.
        % % What weapon was in the living room?
        man(Livingroom), \+Livingroom=robert,


        Пользуясь случаем хочу передать привет 609 кафедре МАИ (за давностью лет, забыл… кажется преподаватель Махорин Андрей Олегович) Тогда я не понимал, что от меня требуют… и пытался писать на прологе, как на родных Си. Теперь понял! :)
        +1
        Всегда было интересно, зачем же нужен prolog. Так вот зачем!
          0
          Ну да, Пролог это система вывода заключений из фактов и теорем, и прекрасно подходит к задачам, где задано множество фактов, и из них нужно извлечь какое-либо непрямое следствие. ИМХО на Прологе самое то писать SAT-решатели, практически один в один можно перенести условие в код.
            +3
            Мне кажется сила и великолепие пролога недооценены во всяких РПГ для обсчета внутренней логики сложных квестов. Кроме того в таких играх часто есть дифференциация отношения NPC к игроку в зависимости от его «кармы», персонажа, выполненных квестов, сделанном выборе в той или иной ситуации и прочего. Даже очень крутые игры часто грешат, например, несоразмерностью выдаваемых квестов и уровня персонажа. Так игрок, который заполучил чуть ли не самый мощный артефакт и занимает не последнее место в гильдии покорно идёт освобождать подвал какого-нибудь купца от крыс…
            Это лишь вершина айсберга. Думаю с помощью пролога можно было бы сделать квесты гораздо более логичными и гибкими.

            Кто-нибудь слышал о применении пролога в геймдеве?
              0

              Можно какой-нибудь пример? Я не понял, как особенности пролога помогут писать квесты.


              Вот я могу императивно написать что-то типа:


              quest.isAvailable = player.level in 10..20 && questsFinished(a, b, c)
              quest.reward += Gold(100 + 50 * player.level + 10 * sigmoid(player.karma))
              if questA.isFinished && questA.isPlayerChosenSmth 
                  quest.reward += Weapon.random(sword, level=player.level)

              Что изменится при появлении пролога?


              Мне кажется, что примитивность квестов — просто косяк тех, кто их придумывал. В том же ведьмаке практически все квесты можно по-разному пройти c разным результатом и с разным порядком прохождения самих квестов. Мне кажется, такой подход требует большего бюджета на разработку и отладку квестов, но ничего принципиально нового не содержит.

                +4
                То, что вы написали в примере, легко реализуется и в декларативном и в императивном стиле. Более сложные же квесты способны првевратиться в императивный ад нечитаемого распределённого кода, пронизанного паразитной связностью и багами.
                Здесь у вас расчитывается возможность взятия квеста и награда на довольно примитивном уровне.
                Я же говорил о сложных многоступенчатых сюжетных квестах. Делая такие квесты уже не обойтись без концепции конечных автоматов, каких-то вариаций сетей Петри и прочего. Но с какого-то момента код квестов становится слишком большим, нежелательная связность слишком высокой, а контекст размазанным по куче мест, отчего ошибки так и норовят создать имбалансные ситуации и петли бесконечной прибыли.
                Возможно без императивного описания каикх-то вещей и не обойтись, но декларативный слой, явно описывающий глобальные (в мире или на уровне персонажа) и локальные (на уровне квеста или связанной группы квестов) ограничения определённо сделает более управляемым, понятным и предсказуемым процесс построения и отладки действительно сложных сюжетных квестов.

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

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

                • Контекст персонажа:
                  • Часть предиктов будет получено от класса персонажа
                  • Часть предикатов будут перекрывать вышестоящие контексты
                  • Отдельно может быть описано индивидуальное отношение к классу игрока, к самому игроку и тегам, которыми наделили его выполненные квесты.

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



                У меня нет готовых рецептов и простых пирмеров для вас. Для простых случаев такая логика не нужна, а сложные в двух словах не изложить… хотя…
                Я как-то писал сравнительно несложный квест для ММОРПГ в маленькой но дерзкой студии в коллективе таких же неопытных геймдев-разработчиков как я. Там система квестов задумывалась как относительно изолированная часть, котороую смогли бы наполнять менее квалифицированные и опытные программисты, нежели разработчики ядра. Квестовая система была построена на конечных автоматах и событийной модели.
                Так вот, был там один парный квест, который становился доступным когда кто-то в другом городе брал комплиментарный ему квест. Что-то вроде «сопроводить караван» / «перехватить караван». Вариации комплиментарных пар были довольно широки, там можно было сопровождать конкретного NPC или группу, атаковать или защищать локацию и много дургих кейсов.
                При этом часть NPC управлялись простыми «рефлексами», а часть логикой квеста.
                Легко представить себе сколько исключительных и нештатных ситуаций может породить такая сложная мультиагентная система из двух параллельно работающих конечных автоматов и нескольких десятков юнитов со своими рефлексами и задачами. Но всё становится на порядок интереснее, когда с обеих сторон есть живые люди.

                Как-то разумно и внятно учесть вклад и добросовестность выполнения такого квеста — это та ещё задачка. И эта задачка куда понятнее описывается декларативно и логически, чем императивно алгоритмически.

                «Фишка» пролога в том, что на этом языке мы описываем не решение задачи, а лишь её условие. Если задача имеет решение, то оно будет логически выведено… рано или поздно.

                Кроме того логическими предикатами можно сравнительно несложно описать правила по которым можно вычислить «знает» ли тот или иной NPC о том или ином событии. Например, игрок только что заранее выполнил условие квеста, который только собирается получить. NPC должен всё же дать ему этот квест, если у него не было возможности (даже теоретической) «узнать» о том, что условие выплнено. Грубо говоря нет смысла давать задание убить старосту, если в деревне уже поднялась паника по этому поводу.
            0
            Версия пролога — огонь. Всегда нравился этот язык.

            Only users with full accounts can post comments. Log in, please.