Всем привет!
Прошло целых полтора года с момента написания моей первой статьи на Хабре. С тех пор проект FOTM претерпел ряд изменений. В начале пройдёмся вкратце по всем модернизациям, а затем перейдём к детальному разбору основной фичи — AI.

В первой части своего рассказа я поведаю вам о последних изменениях в проекте и попытке реализовать AI с помощью нейросети. А из следующей статьи вы узнаете о дереве решений и планах на будущее. Итак, начнём!

Было бы неплохо сделать...

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

• Чат. Так как игра почти полностью построена на сокетах, создание чата было делом быстрым и лёгким.
• Бой в ничью. Теперь спустя 50 ходов игра заканчивается ничьёй, чтобы не тянуть время и нервы противника.
• Ролики. Моим другом было записано несколько обучающих видео по настройке персонажей и механике боя. Ролики сейчас доступны на YouTube канале игры.
• Gulp. Вооружившись новоприобретёнными знаниями об этом сборщике, я облегчил и слегка ускорил клиент.
• Переезд логики на сторону сервера. Эта задача оказалась весьма тяжёлой и кропотливой. Большая часть механик располагалась именно на стороне клиента, что в корне не правильно. Основная часть фидбэка по игре касалась именно этого аспекта. Тем не менее, перенос позволил не только сделать игру менее доступной для злых хацкеров, но и дал возможность зарефакторить некоторые страшные вещи.

На вышеперечисленные улучшения у меня ушло примерно полгода ленивой работы. Как только хабраэффект миновал, я понял, что заходящим в игру людям не с кем играть. Они пишут в пустой чат, встают в очередь на арену и… закрывают игру. Ведь если ты один на сервере, то и драться не с кем :-(

Нейро-fotm

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

Сперва я реализовал функцию формирования списка доступных в каждом ходу действий. Всего их может быть 3:

• Передвижение
• Использование способности
• Завершение хода

На каждое действие тратиться ресурс – энергия, количество которой ограничено за ход. Представим, что у игрока в распоряжении 1000 энергии: передвижение стоит 300 энергии, использование способности «огненный шар» – 400. Значит в свой ход можно выполнить, например, такие действия: Передвижение -> Передвижение -> Огненный шар -> Завершение хода. После этого энергия персонажа восполняется до максимума, и ходит следующий игрок.

Ради эксперимента я сделал выбор действия случайным, чтобы посмотреть, как два безбашенных бота творят всякие глупости :)

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

1. Offensive move Передвижение на клетку более выгодную с точки зрения нападения (точка, в которой максимальное число противников находится на оптимальном расстоянии для применения атакующих способностей)
2. Defensive move Передвижение на клетку более выгодную с точки зрения защиты (точка, в которой максимальное число союзников находится на оптимальном расстоянии для применения защитных способностей)
3. Offensive Использование способности, наносящей урон противнику.
4. Defensive Использование способности, которая поможет персонажу или союзнику выжить: исцелит его или снимет негативные эффекты.
5. Control Использование способности, ограничивающей действия противника: оглушение, замедление, невозможность использовать способности и т.д.
6. Gain Использование способности, увеличивающей характеристики персонажа или союзника.
7. Weakening Использование способности, снижающей характеристики противника.

Для модели нейронной сети я выбрал достаточно простой для понимания перцептрон, подходящий для моей задачи.


Многослойный перцептрон

На входе – массив данных о ситуации. Рассмотрим небольшой кусочек последовательности значений:

    let input = [..., 1, 1, 0.8, 1, 0.5, 0.86, ...];

Шесть цифр в примере показывают отношение текущего запаса здоровья к максимальному для 6 персонажей (активный персонаж, 2 союзника и 3 противника). На выходе нейронной сети можно будет увидеть следующее:

    let output = [0.2, 0.1, 0.7, 0.45, 0, 0.01, 0.03]; 

Это массив тех самых 7 моделей поведения, которые я описывал выше. Т.е. нейронная сеть в данном случае оценила ситуацию и пришла к выводу, что оптимальнее всего атаковать противника (0.7), защитить себя или союзника (0.45) или просто перейти на клетку поближе к противнику (0.2).

Каждая способность в игре имеет отдельное свойство useClass, которое классифицирует её.


Способность «Prowler» наносит урон и оглушает врага на 7 ходов

Для способности «Prowler» это свойство выглядит следующим образом:

    useClass : {
        "offensiveMove" : 0,
        "defensiveMove" : 0,
        "offensive" : 1,
        "defensive" : 0,
        "control" : 1,
        "gain" : 0,
        "weakening" : 0,
    }

А в виде массива:

    let abilityUseClassArray = [0, 0, 1, 0, 1, 0, 0];

Чтобы определить насколько способность «Prowler» подходит под эту модель, я использую полученное нейронной сетью решение (output) и сравниваю 2 линейных массива.

    let difference = 0;
    for( let i = 0; i < output.length; i++ ) {
        difference += Math.abs(output[i] - abilityUseClassArray[i]);
    }

Чем ниже значение difference, тем вероятнее применение этой способности. При полной идентичности массивов (100% совпадение поведения и свойства useClass способности) difference будет равен 0. Дальше остаётся только выбрать то действие, для которого difference будет минимальным.

Вроде всё выглядит красиво и понятно, но есть ряд проблем.

Проблема 1: Нормализация

Для формирования массива входных данных необходимо было их нормализовать в пределах от 0 до 1. С упомянутыми выше значениями остатка здоровья всё оказалось достаточно легко. Сложнее с непостоянными величинами, такими как наложенные на персонажа временные эффекты (баффы и дебаффы). Каждый из них – это объект с несколькими важными полями, вроде оставшегося времени и множителя эффекта (стаков). Чтобы дать понять нейронной сети, чем один эффект отличается от другого, мне пришлось ввести такое же поле useClass, как и для способностей. Таким образом, я смог описать эффект, но осталась проблема их количества. Для этого я взял количество наложенных на персонажа баффов и дебаффов и нормализовал это в виде:

    buffs.length / 42

Такое решение практически не говорит нейронной сети о свойствах объектов внутри массива buffs. В среднем на персонажах может висеть 2-3 эффекта. Планку в 42 перейти невозможно, поскольку в бою только 6 персонажей и 7 способностей у каждого. В результате, нормализованное описание игровой ситуации представляет собой массив из порядка 500 значений.
Можно было бы сделать 42 последовательности значений для описания эффектов (когда его нет, заполнять нулями). Но даже если на каждый будет приходиться, скажем, 10 свойств, то выйдет уже 420 значений (и это только для баффов). Поэтому я на время отложил этот вопрос :)

Проблема 2: Обучающая выборка

Для формирования обучающей выборки мне необходимо было вручную заполнить выходные значения для ряда ситуаций. Я реализовал UI, который показывал все доступные в этом ходу действия. Выбранное действие записывалось в отдельный JSON файл как решение (output) для заданного набора входных значений (input). За одну партию мне удавалось сформировать порядка 500 соответствий input-output, что и являлось обучающей выборкой. Но главный вопрос продолжал висеть в воздухе: насколько большой должна быть выборка?

Более того, если я по каким-то причинам решил бы изменить описание ситуации (а так и случилось), то всё пришлось бы начинать сначала. Например, если массив входных данных будет состоять не из 520, а из 800 значений, то всю старую выборку можно выбросить на помойку вместе с конфигурацией сети.

Проблема 3: Архитектура и конфигурация сети

Итак, мы имеем около 520 значений в массиве входных параметров и 7 значений на выходе. Для реализации нейронной сети я выбрал библиотеку Synaptic.js, и реализовал сеть следующим образом:

    var network = new Architect.Perceptron(520, 300, 7); // input: 520, hidden: 300, output: 7
    var trainer = new Trainer(myNetwork);

    var trainingSet = [
        {
            input: [0, ... , 1], // input.length: 520
            output: [0, 0.2, 0.4, 0.5, 0.1, 0, 0] //output.length: 7 
        },
        ...
    ];

    trainer.train(trainingSet, {
	rate: .1,
	iterations: 10000,
	error: .005,
	shuffle: true,
	log: 1000,
	cost: Trainer.cost.CROSS_ENTROPY
    });

Так выглядела первая конфигурация сети. Я запустил её и… за 10000 итераций нейронка так и не смогла даже близко приблизиться к заданному значению ошибки в 0.005, потратив при этом 2 часа. Я думал над тем, что можно изменить, чтобы достигнуть заданного значения. И понял, что всё плохо :(

Рассмотрим имеющиеся параметры конфигурации:

1. Размер выборки
2. Количество скрытых слоёв и размер каждого из них
3. Коэффициент скорости обучения
4. Число итераций
5. Значение ошибки
6. Функция оценки (3 варианта или можно написать свою)

Понять, как каждый из них влияет на результат работы довольно трудно, особенно если нейронными сетями ты пока занимаешься 2 недели. Если сделать 1 скрытый слой из всего 10 нейронов, то ошибка в 0.01 достигается достаточно быстро (примерно 100 итераций), но закрадываются подозрения касательно гибкости такой сети. Скорее всего, если «скормить» ей нестандартную игровую ситуацию, она примет совершенно неприемлемое решение.

Проблема 4: Скорость тренировки

При вышеуказанной конфигурации обучение сети длилось около двух часов (примерно 1,38 итераций в секунду). Это довольно долго, учитывая, что нужно поэкспериментировать с цифрами для получения результата. Проблема была в том, что вычисления производились на CPU (Intel Core i5-4570), а не на видеокарте. В этот момент я задался вопросом переноса вычислений на GPU с использованием CUDA. Я перелопатил много материала и пришёл к выводу, что шансы настроить CUDA для Node.js на Windows практически равны 0. Да, можно развернуть отдельный сервер на Linux, который бы занимался только расчётами сети. Попробовать написать этот сервер не на Node.js, а на Python и много каких других вариантов. Но что, если вариант AI построенный на нейронной сети просто неприемлем для решения моей задачи?

Проблема 5: Особенности игровой механики

На этапе разработки сети я встретился ещё с двумя проблемами выбранного подхода к реализации AI.


Описание способности «Lets me take it»

1. Не все способности можно отнести к одной модели поведения. Самый яркий пример – способность «Lets me take it» оракула. Она «крадёт» случайный положительный эффект у противника и применяет к тому, кто её использовал. Проблема очевидна – разновидностей положительных эффектов довольно много: одни лечат, другие защищают союзников, третьи усиливают боевые характеристики, а какие-то ограничивают передвижение персонажа. Если мы украдём усиливающий эффект, какое это будет поведение? Усиление себя (gain) или ослабление противника (weakening)? По сути и то, и другое. Но эффект может ещё и лечить, следовательно – это уже поведение защиты (defensive); а если отняли лечение у противника, то ещё и нападение (offensive). Таким образом, способность «Lets me take it» попадает под все модели поведения. Что, конечно, очень странно. Эта способность далеко не единственная, у которой присутствует фактор случайности.
2. Поведение определяется только для конкретной ситуации. Решение о том, что лучше сделать в данный момент не учитывает следующие действия как активного игрока, так и игроков противника. Нет моделирования ситуаций и просчёта вариантов исхода событий.

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

А пока спасибо за внимание!