Моделирование поведения генно-нечёткими системами

2009.01.01

Это название моей курсовой работы за 6 семестр.

Пока я учился в универе, я понял, что мне хочется решить какую-то свою задачу, что-то, не спущенное мне “сверху”.

На шестом семестре я созрел для выбора темы. В то время я наткнулся на довольно старую компьютерную игру из Японии, которая поразила моё воображение.

Этой игрой была Princess Maker 2, в каком-то фанатском неофициальном переводе.

Сценарий игры заключался в следующем. В волшебном мире старому герою-рыцарю богиня доверила на воспитание девочку 12 лет, чудесное дитя с необъяснённым прошлым. Когда девочке исполнится 18, богиня придёт за ней снова и будет судить, насколько хорошо у рыцаря получилось воспитать ребёнка.

Суть игры в том, что неделя за неделей игрок составляет расписание для девочки, и далее пассивно наблюдает, как она развивается. Развитие заключается в изменении большого количества численных “характеристик”.

Когда девочке наступает 18 лет, в зависимости от характеристик и от множества других факторов игра показывает одну из почти сотни концовок, судеб этого ребёнка в будущем.

В дополнение к этой базовой формуле игра включала в себя множество случайных событий, приключения в походах за сокровищами, сбор и покупку разных предметов, которые все влияли на другие случайные события, но это всё было мишурой, которая делала эту игру игрой.

Я же сосредоточился на ключевой механике игры: составлению расписания для того, чтобы привести подопечную к желаемой концовке. Я решил написать решатель для Princess Maker 2.

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

Однако, как исследовательским проектом, я горжусь этой работой искренне и до сих пор. Если меня когда-нибудь хватит на диссертацию, я напишу её на основе этой курсовой работы.

Решение я написал на языке Visual Prolog 7.1. В то время я поддался речам своего научного руководителя и, должен признать, был приятно удивлён возможностями этой среды разработки, по сравнению с другими альтернативами, которые мы использовали: C++98 и Delphi/Pascal.

Ниже ссылка на PDF файл самой курсовой работы, где третьекурсник пытается писать научным стилем, и у него не очень получается.

Исходный код работы я выложил на гитхаб:

Суть метода

Так как я не мог скопировать один к одному числа из игры, то мне пришлось всё придумать самому. В центре находился персонаж, описанный набором числовых характеристик. Каждый “ход” программа выбирала из определённого множества список “действий”, которые персонаж будет делать. Каждое “действие” меняло несколько характеристик – обычно увеличивало, но иногда некоторые и уменьшались.

После определённого количества выбранных “действий” персонаж приходил к определённому состоянию, определённым значениям характеристик.

Задача заключалась в том, чтобы, указав целевое, желаемое состояние персонажа, и, зная исходное состояние, получить последовательность “действий”, которые приведут персонажа к целевому состоянию.

Пространство вариантов получалось просто невероятно огромным, поэтому полный перебор исключался.

В то время я наткнулся на чудесный труд по генетическим алгоритмам, и заинтересовался возможностью использовать этот метод для поиска решения. Однако, напрямую генетический алгоритм не подходил для поиска решения. То, что ищется в поставленной задаче – это список “действий”, и он может быть произвольной длины, плюс к тому, список доступных для выбора “действий” потенциально тоже очень велик (возможно, сотни действий). В таком виде пространство поиска нисколько не уменьшалось.

Поэтому я решил добавить понятие “склонностей” в схему. В зависимости от “склонностей” персонаж принимал решение, какие действия предпринять.

В таком случае задача сводилась к подбору значений “склонностей”, которые приводили к “действиям”, которые приводили персонаж максимально близко к желаемому состоянию.

Набор склонностей был невелик (меньше десятка), и склонности имели небольшой разброс значений, что делало их идеальным кандидатом для генома, искомого в генетическом алгоритме.

Оставалось только связать склонности и действия. К этому моменту я прочитал другой труд, на этот раз по нечёткой логике, и увидел в нём возможность очень “реалистично” описать, как склонности могут влиять на принятие решений.

Суть сводилась к тому, что я могу собрать нечёткий контроллер, в который будут загружены правила, составленные в человекопонятной манере: “если аггрессивность высока, то желание учиться фехтовать высокое, а желание заниматься музыкой низкое”. Или более сложные, включающие в себя ещё и текущие значения параметров: “если склонность к искусствам высока, умение танцевать высоко, то желание учиться танцевать низкое, а желание работать танцором высокое”.

В итоге получилась так называемая генно-нечёткая система, работающая на двух уровнях. Имея набор “склонностей”, персонаж, стартовые характеристики которого были всегда зафиксированы, раз за разом принимал решения на основе вычислений нечёткого контроллера. На определённом моменте – после, скажем, тысячи принятых решений – этот цикл останавливался и конечное состояние персонажа сравнивалось с желаемым. Вычислялось отклонение, или “ошибка”, как обычно.

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

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

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