Они мертвы? Они живы? Она его тетя? Вместо того, чтобы возвращаться к 2011 году, избавьтесь от усталости и создайте собственного эксперта с помощью Prolog.

Обязательная игра "Игра престолов" ПРЕДУПРЕЖДЕНИЕ ДЛЯ СПОЙЛЕРА! Включены события до 7-го сезона, без учета всего, что происходит только в книгах. Если вы не в курсе, действуйте осторожно. Но Пролог остается неизменным с 1972 года, без поворотов сюжета и простой структуры, которой вам поможет этот учебник.

Установить факты

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

Упростите ситуацию, запустив базу данных с одним набором фактов, который можно применить ко всем персонажам. Для генеалогического древа хорошее место для начала - это связать персонажей через их родителей. Возьмем случай с Арьей Старк:

parent(eddard_stark, arya_stark).
parent(catelyn_stark, arya_stark).

Здесь были определены два отдельных факта, говорящих о том, что Эддард и Кейтилин являются родителями Арьи. Затем вы можете экстраполировать эти запросы на всю вселенную Game of Thrones, для всех домов, чтобы создать полную базу данных (или переманивать весь набор данных из моего GitHub). Одних этих фактов достаточно, чтобы начать задавать вопросы. Самый простой запрос проверяет, присутствует ли факт в базе данных.

?-parent(eddard_stark, arya_stark).
true

Если вы вводите отношения, которых нет в базе данных, возвращается false. Вы также можете запрашивать переменные в Прологе, используя заглавные буквы. Чтобы узнать, кто родители Арьи, спросите:

?-parent(Parent, arya_stark).
Parent = eddard_stark ;
Parent = catelyn_stark.

Эддард возвращается первым в этом примере, поскольку это первый истинный факт, указанный в базе данных. Нажатие точки с запятой ведет к поиску дальнейших истинных ответов (catelyn_stark), пока не останется ни одного. Точка завершает поиск все вместе. Используйте символы подчеркивания в качестве анонимных переменных, чтобы отфильтровать информацию, которая не имеет значения. Например, если вы хотите узнать, что у Арьи есть родители, но вам все равно, кто они, запросите следующее:

?-parent(_, arya_stark).
true

Создать правила

Теперь, когда в базе данных есть факты, приступим к созданию правил. Правила зависят от фактов. Связывание фактов вместе создает правила. Из нашего последнего примера составьте простое правило из родительского факта, чтобы определить дочерние отношения; X является дочерним элементом Y если (в Прологе обозначается как : -) Y является родительским элементом X.

child(X, Y) :-
    parent(Y, X).

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

status(X, dead) :-
    not(status(X, alive)).

Здесь я расширил базу данных, включив в нее набор правил для каждого живого персонажа. Запрос ищет в базе данных все экземпляры, где жив человек X. not указывает на то, что, если обнаружено, что X не жив, то X мертв. Это правило эффективно для Игры престолов, поскольку требует лишь нескольких фактов для тех немногих, кто еще жив.

Более интересные и конкретные правила создаются путем объединения фактов. Например, чтобы создать отношения матери и отца, необходимо больше фактов о поле каждого персонажа в «Игре престолов». После этого создается правило для идентификации матерей:

mother(X, Y) :-
    parent(X, Y),
    female(X).

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

До сих пор мы рассмотрели путешествие вверх и вниз по генеалогическому древу, но не коснулись слева направо. Создав одно родственное правило, можно делать запросы по всему генеалогическому древу Игры престолов:

sibling(X, Y) :-
    parent(Z, X),
    parent(Z, Y),
    dif(X, Y).

С точки зрения непрофессионала, это означает, что два человека (X и Y) являются братьями и сестрами, если у них обоих один и тот же родитель (Z). Функция diff здесь важна, чтобы программа не возвращала себя как своего собственного брата. ОДНАКО, у этого подхода есть ограничения. Запрашивая это, будут оцениваться оба родителя X и оба родителя Y (часто, но не всегда, одни и те же люди), следовательно, полный поиск вернет дубликаты. Это можно исправить, введя списки.

Составление списков

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

list_siblings(X, Siblings) :-
    setof(Y, sibling(X, Y), Siblings);
    Siblings = none.

setof объединяет все возможные результаты для sibling(X, Y)query и сохраняет их в списке под названием Siblings. Если братьев и сестер нет, компонент или (представленный точкой с запятой в Прологе) ничего не возвращает. setof также удаляет все дубликаты, сохраняя только уникальные значения, что улучшает предыдущий запрос. Теперь, когда список братьев и сестер можно сгенерировать для любого символа, отдельный запрос может определить, являются ли 2 символа братьями и сестрами:

siblings(X, Y) :-
    list_siblings(X, Siblings),
    member(Y, Siblings).

При запросе создается список Siblings для X и используется member, чтобы определить, входит ли Y в список Siblings.

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

Рекурсия

Родословные в «Игре престолов» охватывают гораздо больше, чем просто ближайших родственников. Можно пойти дальше и установить связи между более отдаленными отношениями. Используя родительский предикат, Prolog может рекурсивно оценивать базу данных, чтобы найти предков. Настройте рекурсию, включив в базу данных следующие 3 раздела:

  1. Завершающая секция - эта секция должна находиться перед секцией цикла, чтобы программа не зацикливалась бесконечно:
ancestor(X, Y) :-
    parent(X, Y).

2. Секция зацикливания - эта секция вызывает себя многократно, пока не будет выполнено условие завершения, указанное выше:

ancestor(X, Y) :-
    parent(X, Z),
    ancestor(Z, Y).

3. Раздел вызова - запрос? -Ancestors (X, Ancestor_of), чтобы начать сохранение списка предков через каждую рекурсию, как определено выше:

ancestors(X, Ancestor_of) :-
    findall(A, ancestor(X, A), Ancestors_of).

Функция findall здесь работает аналогично setof, но не исключает дубликатов и возвращает список того, кто X является предком.

Печать и форматирование

Если вы ищете универсальный магазин, где можно получить всю информацию об одном персонаже, вам потребуется форматирование, чтобы упорядочить ее. Чтобы вернуть кучу информации за один раз, вызовите ранее определенные правила в правиле:

tell_me_about(X) :-
    alive_or_dead(X),
    parents(X, Parents),
    format("Parents: ~w", [Parents]), nl, 
    children(X, Children),
    format("Children: ~w", [Children]), nl,
    list_siblings(X, Siblings),
    format("Siblings: ~w", [Siblings]), nl,
    !.

формат возвращает любой вывод из квадратных скобок вместо ~ w и печатает все, что заключено в кавычки. nl представляет новую строку. Функция вырезания (!) в Прологе предотвращает возврат, поэтому заставляет программу прекращать поиск дополнительных решений после того, как первое было найдено. В приведенном выше примере это гарантирует, что все будет напечатано один раз. Запрос на это у Станниса Баратеона дает следующее:

Функцию print также можно использовать вместо форматирования, когда нет переменных для вывода.

Использование арифметики

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

aryas_list :-
    print("ARYAS TOP SECRET LIST. KEEP OUT."), nl,
    findall(X, on_list(X), MainList),
    ticked_off(List),
    format("Done: ~w", [List]), nl,
    not_dead_yet(AnotherList),
    format("Still to go: ~w", [AnotherList]), nl,
    length(AnotherList, LCompletedList),     
    length(MainList, LMainList),
    Percent is ((LMainList - LCompletedList) / LMainList) * 100,
    Percentage is round(Percent),         
    format("Percentage complete: ~w%", [Percentage]), nl.

В aryas_list я использовал следующие операторы:

  • * Умножить
  • - вычесть
  • / Делить
  • длина(). Создать длину списка
  • круглый(). Округлить до ближайшего целого числа

Результат выглядит следующим образом:

Со всеми описанными инструментами есть еще множество интересных способов исследовать вселенную Игры престолов в Prolog. Или полностью отказаться от просмотра шоу после того, как с помощью бесспорного логического программирования выяснилось, кто должен сидеть на Железном троне.

rightful_heir(X) :-
    parent(robert_baratheon, X),
    status(X, alive).

Результаты говорят сами за себя…

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

Следите за моим LinkedIn для будущих проектов.