Навеянное Prolog-ом коммерческое решение пробыло больше 10 лет в эксплуатации
Для большинства программистов которые хотя бы слышали про Prolog это только странный артефакт из времён когда компьютеры были размером с динозавров. Некоторые сдали и забыли в институте. И лишь узкие как листочек A4 специалисты сталкивались с чем-то подобным в современном мире. Так уж получилось, что далёком 2003-ем году я использовал некоторые решения подчерпнутые из Prolog-а, в коммерческих играх на Flash и больше десятилетия они радовали французов. Причём применил я это полудекларативное решение не потому что прочитал книжку Братко и впечатлился, а потому что это было реально нужно нашему проекту. Я до сих пор регулярно порываюсь воспроизвести то решение на современном уровне, потому что оно очень много где было бы полезным в современном игрострое, но, к сожалению, каждый раз находятся дела поважнее… В общем об этом всём и расскажу.
Скриншот той самой флэшовой игры до сих пор приветствует вас на сайте toox.com/jeux/jeux-de-cartes/coinche
Постановка задачи и её актуальность
Квош, Белот и Таро — национальные французские игры. По правилам это примерно как игра в преферанс в закрытую, причём играют пара на пару, так что по тому сколько взяток и на каком козыре во время торга за прикуп предлагает объявить игру твой напарник можно примерно понять что у него за карты. Игра длинная и существование AI способного кое как довести игру до конца в ней просто жизненно необходимо, потому что один из игроков может просто выйти из-за стола решив, что он безнадёжно проигрывает, а победителю естественно хочется додавить до финального счёта на табло. В этом случае за потерявшегося игрока доигрывает AI. Но раз уж у нас есть AI почему бы нам не разрешить начинать игру досадив на пустующие места AI-шки. И вот мы запустили эти прекрасные игры в массы и быстро выяснили, что в основном есть два варианта как нравится играть французам. Примерно половина всех столов до победного ждёт заполнения живыми людьми, а половина приходит потупить и стартует игру против трёх AI, как на скриншоте выше.
В принципе, так как игра идёт в закрытую, люди готовы простить роботам мелкие просчёты и альтернативную одарённость. В основном потому что карт робота не видят. «Под игрока с симака», «под вистуза с туза» и тому подобные простые правила, которые я вытряхнул из нашего французского заказчика позволили сделать минимально приемлемого кидателя карт. Он был нафигчен за неделю прямо на if-ах. С другой стороны игра идёт «двое на двое», очки считаются для пары, и вполне естественно игрок не хочет, чтобы его тупой напарник заходил «со второго короля», то есть имея на руках короля и ещё какую-то мелкую карту делал ход в эту масть, вместо того чтобы дать противнику сыграть туза, пропустив его мелкой картой и забрать следующий ход в эту масть своим королём. (На самом деле в этих играх вторая по старшинству карта — 10, но тут и дальше я буду говорить в понятных русским терминах). Но если туз по какой-то причине вышел из игры, а у вас Дама и ещё что-то мелкое, то это же почти как второй король. Особенно если предварительно прорядить козырей. А ещё вы, например, играете не в Белот, где используется 32 карты, а в Таро, в которой игра идёт колодой в 78 карт, (той самой, по которой некоторые гадают). И там в некоторых случаях забрать взятку может даже не третья дама, а четвёртый валет. В общем всё это порождает такое количество граничных случаев, что тупой болванчик на if-ах становится уже как-то совсем неприемлемо сложным. И вот на этом месте я сказал: «Ба! Да я же начитался Братко и впечатлился!» Дальше я на несколько дней сбежал из офиса, сел с ноутбуком в кафешке и спустя несколько дней породил нечто.
Основные идеи
На чём, декларативно говоря основан Пролог? На фактах, например:
мама('Галя', 'Ира').
мама('Ира', 'Алиса').
и на термах, или правилах, например если А мама Б, то А девочка:
девочка(А) :- мама(А, Б).
Я конечно понимаю, что в наше время не всё так однозначно, и вообще говорить такое даже немного неприлично, но во времена когда люди верили в формальную логику в таких примерах ещё не было ничего предосудительного. Давайте для толерантности скажем:
предок(A, B) :- мама(A, B).
предок(А, В) :- предок(А, С), предок(С, В).
А потом ты такой Спрашиваешь:
?- предок (X, 'Алиса')
А страшно логичный Пролог тебе и отвечает:
X = 'Ира'
X = 'Галя'
Идея была в том, том, чтобы пользователь не грел себе голову тем в какой последовательности и в каком количестве пролог система применит правила к фактам чтобы прийти к ответу. Но, конечно же, всё не так просто. Пролог оброс костылями, функциональными дополнениями, отсекателями разных веток рассуждений и тому подобным, и всё равно регулярно убегает в бесконечную рекурсию.
В книжке того самого воодушевляющего Братко целая глава была посвящена тому как внутри реализовывается пролог-машина. Если коротко она обходит дерево всех правил в глубину, пытаясь применить по очереди каждое из правил к множеству всех известных ей фактов и переменных чтобы получить новое состояние, и если применить правило не удаётся откатывается к предыдущему шагу и пытается попробовать другой вариант.
При этом если что-то полезное наскрести удаётся — машина берёт список правил начинает на следующем шаге искать правилам применение с самого начала списка. При этом если в правилах встречается переменная, машина запоминает какие с учётом уже применённых правил могут быть состояния этих переменных. Это называется конкретизация. Если удаётся найти конкретизацию переменных при которой заданные вопрос — истина, она печатает эту конкретизацию. Потом она может пойти искать следующую конкретизацию и так далее. В приведённом выше насквозь искусственном примере система нашла две конкретизации удовлетворяющие условиям.
Вот хотелось бы как-то похоже формулировать правила игры, но конечно не буквально. Имея определённый опыт отладки программ на Прологе я совершенно не горел желанием сталкиваться этой отладкой и этими накладными расходами у себя на проде.
Общие хотелки
Во-первых, всё это должно работать не над кучей разрозненных фактов, а над деревом состояния игры — моделью и применять результаты своей работы тоже к этому же дереву. Во-вторых, хочется записывать правила так чтобы в одной же позиции могло быть и конкретное значение, и переменная, и арифметическое выражение и система должна это соответствующим образом обработать не задавая программисту дополнительных вопросов и не требуя дополнительного синтаксиса. В-третьих, конечно жизненно важно отказаться от бесконечной рекурсии, но некоторые повторения применения правил все же необходимо оставить. В-четёвртых, система правил должна записываться в каком-то очень удобном человекочитаемом формате, так чтобы при одном взгляде на них было понятно что хотел сказать автор. Ну и наконец, в-пятых, всему этому нужно прикрутить какой-нибудь удобный инструмент логирования и отладки, чтобы было легко следить за рассуждениями этой системы и понимать почему те или иные правила не срабатывают вопреки ожиданиям.
Это уже, конечно получается никакой не универсальный решатель логики предикатов первого порядка, а просто удобная декларативная система правил игры. Что в практическом смысле тоже очень неплохо. Название Logrus я для этого придумал сильно позже на одном из следующих проектов. Я буду описывать сразу конечную версию минуя все промежуточные стадии развития движка.
Получившийся в итоге синтаксис бибилотеки Logrus
Щаз будет очень много синтаксиса.
1) В рантайме дерево решения хранится в виде некоторых классов, но первое, что я к нему приделал, как только оно заработало — Import и Export в JSON. Оказалось, что это удобно ещё и потому, что если у вас не сильно поменялась страктура данных обновление правил можно накатить из файлом без перекомпиляции. Запись в виде JSON оказалось на столько удобной, что на одном из следующих проектов программисты когда торопились иногда вместо того чтобы писать нормальную команду делали просто state.AplayJSON("..."); и в нём нужное действие вставляли в виде JSON строки. На производительности это, конечно, сказывалось не очень хорошо, но если не регулярно и только в ответ на нажатие пользователя, то не страшно… Всё дальше я буду иллюстрировать сразу JSON-ами. JSON-ы воспроизвожу примерно и по памяти, потому что шибко давно дело было. Строго говоря, JSON не гарантирует порядок следования нод в объекте, но большинство библиотек все-же его соблюдают, и здесь и далее порядок нод активно используется.
2) Основной структурной единицей движка стало Правило. Правило состоит из условия и действия. Обычно правила шли массивами и применялись одно за другим каждое один раз.:
[{"condition":{}, "action":{}},
{"condition":{}, "action":{}}]
3) В каждом правиле содержится условие — это шаблон дерева, возможно содержащий переменные. Система поищет совпадает ли дерево состояния с шаблоном при каких-нибудь значениях переменных. И если найдёт такую конкретизацию вызовет действие. Например:
{"condition":{
"player":{
"$X":{"gold" : "<20", "name":"$NAME"}
}},
"action":{}}
Такая конструкция будет означать, что для того чтобы было вызвано действие в дереве должна иметься на верхнем уровне нода «player» в которой одна или несколько дочерних нод, в каждой из которых есть поля «gold» со значением меньше 20 и «name». Если такое условие будет выполнено, то будет вызвано действие, причём в качестве входных данных ему будут переданы в переменной X — ключ ноды, а в переменной NAME имя игрока. Если подходящих нод и соотвественно возможных конкретизаций окажется несколько, то действие вызвано будет несколько раз с каждой из найденных конкретизаций на входе.
4) Первоначально там всё было чуть-чуть менее гибко, но потом Valyard, которого многие знают по многочисленным выступлениям на конференциях про Unity, прикрутил нам синтаксический анализатор, разбирающий арифметические выражения в шустрое дерево решений и гибкость окончательно расцвела буйным цветом.
5) C $ начинаются имена переменных. Они могут встречаться как в виде ключа, такого как $X и тогда будет выбрано несколько конкретизаций, в виде значения листа, такого как $NAME, могут вставляться в арифметические выражения: например так: {«gold»:»< $X * 10"}И тогда использоваться для проверки условий, проверку пройдёт только те игроки, у которых золота больше чем их порядковый номер умноженный на 10, и наконец Они могут непосредственно вычисляться в каком-нибудь выражении, например так:{«gold»: "$X = 3 + $this"} где $this это значение текущей точки в которой вызвано вычисление. Прохождение этого узла конкретезирует значение переменной $X как 3+количество золота у игрока. Из возможностей, которые приходили в голову не реализована была только одна — переменная не может впервые встречаться в правой части арифметического выражения, это будет ошибка, к моменту использования в качестве аргумента она уже должна быть конкретизирована одним из нескольких других способов.
6) Переменная в выражении может встречаться сколько угодно раз, при этом первое упоминание её конкретизирует, а следующие будут проверкой на равенство. Например такая конструкция возьмёт первого игрока, проверит его на наличие денег, потом поищет другого игрока для которого первый бы был целью. Если не найдет, откатится к точке конкретизиции X выберет следующего игрока, проверит на деньги и так далее пока не переберёт все допустимые варианты X и Y. Поменяв строки местами программист изменит порядок проверок, но не конечный результат:
{ "player":{
"$X":{"gold":">20"},
"$Y":{"target":"$X"}
}}
7) Действие также представляет из себя шаблон дерева, могущий содержать переменные и арифметические выражения, и дерево состояния игры будет изменено так чтобы ему соответствовать. Например этот шаблон, назначит игроку X противника в виде игрока Y, но если бы по какой-то причине игрока Y не существовало он был бы создан. А игрок «superfluous» вообще будет удалён. На момент создания игры со скриншота признаком удаления было значение null, но потом я заменил его на зарезервированное слово, на случай если кому-то потребуется по ключу вставить пустое значение. В целом принцип, думаю, понятен, и смысл совершаемых с игрой действий в основном тоже.
{
"condition":{
"player":{
"$X":{"gold":">20"},
"$Y":{"target":"$X"}}},
"action":{
"$X":{"target":"$Y"},
"superfluous":"@remove"}
}
8) Действием также может являться не шаблон дерева, а массив в свою очередь правил. Каждое из них будет проверяться не с нуля, а именно с той первоначальной конкретизацией, с которой было вызвано действие. То-есть там может быть целая группа правил, и все они будут использовать переменную X.
{
"condition":{
"player":{
"$X":{}, "$Y":{"target":"$X"}}},
"action":[
{"condition":{}, "action":{}},
{"condition":{}, "action":{}}]
}
9) Дочернее правило может применяться не от корня дерева состояния, а от какой-то точки, достигнутой в ходе применения действия. В этом случае все условия и все действия будут использовать эту точку в качестве корня. Выглядит это примерно так:
{
"condition":{
"player":{
"$X":{}, "$Y":{"target":"$X"}}},
"action":{
"$X":{"@rules":[
{"condition":{}, "action":{}},
{"condition":{}, "action":{}}]}
}
10) Повторение правила могло быть задано в качестве ещё одной ноды, этим достигалась, если надо, рекурсия ограниченной глубины. Но на практике такое решение обычно не было необходимым. Его можно использовать так же чтобы повторять пачку правил сколько нужно, поместив его в action:
{
"condition":{},
"action":{},
"repeat":5
}
11) Дерево правил можно было грузить из нескольких файлов JSON, их древовидная структура просто накладывалась одна на другую. Это было удобно чтобы разбить правила на отдельные осмысленные блоки. Наверное полезен был бы и какой-нибудь Include, сейчас уже не помню как у нас оно было устроено.
12) Логирование! Любое правило могло иметь ноду »@log»: true, что приводило к тому, что это правило начинало очень подробно срать в лог описанием процесса решения. Какие конкретизации пробуем, какие ветки рассуждений пресекаются и почему. Логирование было иерархическое, то есть вложенное правило могло быть »@log»: false и всё что происходит в нём и ниже в лог не попадёт. В идеале я бы хотел чтобы эту ноду можно было оставляь вообще у любом месте дерева условий, чтобы смотреть только на происходящее в одном уровне шаблона, но такое расширение я так, кажется, и не доделал. Возможно отладка и без него проходила нормально, поэтому его и откладывали на «когда-нибудь».
13) Типизация. Игрушка была на столько старой, что некоторые из нынешних программистов тогда ещё не родились. Написана она была на языке ActionScript2, в котором была динамическая типизация и наследование через прототипы доступное прямо в рантайме. Из современных языков которые на слуху, так устроен только Python. Однако к данной идее прикрутить типизацию не представляет особой сложности. Я бы сделал это используя ключевой символ ':' например так:»$X: int» однако тут может возникнуть хитрость если первое вхождение переменной не имело никого указанного типа. А кроме того может возникнуть путаница с тернарным оператором.
Как говорится, гладко было на бумаге, но практическое использование потребовало некоторого количества разнообразных костылей. Вот те из них, которые я помню:
14) Одна и та же нода могла проверяться не одним, а несколькими условиями. Например такое условие сначала проверяло, что денег больше 20, а потом конкретизировало переменную в которой это количество денег представлено. Служебный символ '@' если он расположен не в начале строки означал повторных вход в ноду, идущий дальше идентификатор повторного входа никак не пригодился. Возможно служебный символ использовался и какой-то другой, но ничего, по-моему, не мешает тому чтобы использовать этот:
{
"player":{
"$X":{"gold":"<20", "gold@cnt":"$COUNT"}
}
}
15) Потребовались арифметические операции, которые можно было выполнять вообще без использования какой-то ноды. По традиции пролога они обозначались '_' и их можно быть много:
{
"_":"$SUM=$A+$B",
"_@check":"@SUM <20"
}
16) Раз есть проход проверки вверх по дереву, потребовался и спуск вниз, делающийся через ключевое слово »@parent». Читаемости это, конечно, не прибавляло, но обойтись без этого никак не получалось. Тут, конечно, прямо напрашивается какой-то аналог функции path который бы переадресовывал на указанное место в дереве, но я не помню, успел я его реализовать его в итоге или нет:
{
"condition":{
"player":{
"$X":{}, "$Y":{"target":"$X"}}},
"action":{
"$X":{"rules":[
{
"condition":{
"@parent":{"@parent":{"…":"…"}}
}
]},
}
}
17) У действия появилась возможность непосредственно подёргать какой-нибудь метод класса. Это такой пинок под дых читаемости, и я бы предпочёл какой-нибудь аналог #include, но уж как есть, из песни слов не выкинешь. Интересно, смогу ли я без этого обойтись на практике если реанимирую библиотеку сейчас на C#?
18) У правила появилась дополнительная настройка повторять действие не для всех найденных конкретизаций, а только для первой. Не помню сейчас как называлась, но зачем-то этот костыль был полезен для каких-то правил.
Результаты использования
Как только библиотека начала активно использоваться на неё быстро перевели все AI-шки и это сделало возможным иметь вдвое более умные AI тратя при этом в три раза меньше программистских ресурсов. Очень помогло этому то, что промежуточные данные AI-шка хранила прямо в дереве. В частности информация о вышедших из игры картах каждой масти правила сами прописывали прямо в дерево состояния игры.
Уже в следующем проекте на этот же движок переехала и проверка правил игры и составление возможных из каждой позиции ходов. И вообще не только для быстрого прототипирования, но и для игр в которых просто много правил это было бы прям очень полезной штукой. В конце конов загружаемыми JSON-ами с логикой можно заменить половину того что программисты делают кодом, ещё и в гибкости выиграть.
Конечно по скорости выполнения это всё заметно уступало мешанине if-ов, особенно в реализации на AS2 с его прототипами и динамическими объектами, но не на столько, чтобы это нельзя было выкатить в прод.
Следующим шагом должен был стать перенос проверки правил и определение действия за AI на клиентский компьютер. Чтобы игроки проверяли друг друга. И я даже придумал такой алгоритм, чтобы делать это не смотря на то что значения карт противника нам не известны, но это была уже совсем другая история.
Прошло много лет, я поменял работу десяток раз и каждый раз обновляя резюме я заходил на toox.com и с удивлением обнаруживал своё поделие всё ещё в строю. Даже заходил сыграть партию другую. И один раз в Belot мне случайно попался набор карт дающий максимально возможное количество очков. Вероятность выпадения такого набора — один на три миллиона.
Когда-нибудь я соберу волю в горсть и сделаю современный ремейк Logrus-а под C# и Unity3d, например для гексагональной стратегички, о которой мечтаю. Но это будет не сегодня, сегодня я пойду спать. Долг по распространению идей, которые стоят того чтобы их распространять успешно выполнен.
В заключение пара анекдотов
Расположены мы были в новосибирском Академгородке. Арендовали офис в институте. А заказчик француз, с местными нравами совершенно не знакомый. И вот на третий или четвёртый месяц совместной работы приезжает он к нам в гости, знакомиться. Заселился на выходных в местную гостиницу «Золотая Долина» и в понедельник, говорит менеджеру, давай в десять утра встречай меня на такси, поедем с программистами знакомиться. А Вовчик возьми да и приедь в 10. В общем подъезжают они к институту, стучаться в дверь, а с той стороны приходит бабушка вахтёрша и совершенно ничего не понимая на них смотрит из-за закрытой на замок двери. В такую рань ни научных сотрудников, ни арендующих офисы программистов в здании отродясь не бывало. Они её буквально разбудили.
А вот тоже другой случай. Звонит как то наш Себастьян Перейра к менеджеру и говорит, что они тут чудом смогли прорваться в телевизор и скоро нас с нашим сайтом покажут по телевизору. Через 8 часов примерно. Так что вы там сделайте чтобы он работал понадёжнее… На часах 2 января… Не важно какое время… И вот Вовчик берёт такси, начинает по общагам и квартирам собирать программистов совершенно в состоянии размазни, и свозить их в офис. Я в тот день впервые вы жизни увидел нашего сисадмина. До этого момента он всё делал исключительно удалённо. И вот мы каждый подкрутили кто что мог. Я, в частности выломал всю эту систему поставив на её место назад пачку if-ов и вот сидим мы, смотрим на график посещаемости и вдруг видим как он начинает переть вверх. Где-то на отметке x15 сервак грохнулся. Но админ сказал, что всё хорошо, упал аккуратно, сейчас сам поднимется. За тот день сервак падал ещё трижды.
