Создание бота для участия в AI mini cup 2018 на основе рекуррентной нейронной сети

Изначально у меня не было планов о статье, тем более о выступлении на конференции. Но случилась конференция. И после выступления на ней, у смотревших появились ко мне вопросы касательно реализации некоторых технических моментов. Так и получилось слово за слово — статья.

Запись прямого эфира ниже по ссылке.

Дисклеймер: Это статья попытка ответить на часть этих вопросов. Буду рад если возникнут новые вопросы, отвечая на которые появится возможность и самому узнать что-то новое. И да, эта статья не является ни в коей мере попыткой ощутить звон медных труб.

И так начнем с самого начала этой истории. Весна 2018 года, mail.ru объявил конкурс по программированию по мотивам игры Агаиро. Суть соревнований создание игрового бота.

Правила проведения соревнований по этой ссылке. Но если быть кратким и обрисовать правила своими словами, то нужно создать бота для игры в Агаиро. В свое время популярная интернет игра (в смысле что запускается из browser), суть которой поедание меньших братьев своих и убегание от более крупных. Вы управляете цветным кругом в ограниченном двухмерном пространстве. Для создания игрового процесса в этом пространстве кроме вашего круга есть и другие круги, управляемые соответственно другими игроками. Для роста существует еда (цветные точки), введены дополнительные препятствия в виде "вирусов" столкновение с которыми порождает деление вашего круга на более мелкие, что частично усложняет игровой процесс, так как мелких едят более крупные и крупным быть безопаснее.

приведу картинку из варианта игры для соревнований

Далее под игроком будем понимать не разработчика бота, а самого бота.

Устроители конкурса в целом сохранили первоначальную концепцию игры, но добавили от себя ряд нововведений. Основные из которых это ограничение обзора бота и введение простого физического закона под названием инерция. Физику давно проходил, поэтому инерция ассоциируется не только с нами, но и такими величинами как масса, скорость и ускорение. Больше ничего из мира физики нам не понадобится.

Надеюсь литературной части уделил достаточно внимания и пора переходить к технической составляющей конкурса и участия в нем.

Дисклеймер 2: Почти уверен что рассказанное ниже можно было сделать тоньше, изящнее и умнее, но как получилось так получилось.

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

Задача: Создать бота умеющего самостоятельно играть в Агаиро.
Основная идея: Использовать нейронные сети (далее по тексту нейронка, neural network(NN)) в качестве управляющего элемента бота.
Основные производственные средства: Microsoft Visual Studio и c# с плавным переходом в c++.

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

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

Поэтому по ходу написания статьи буду вспоминать простые формы типа нейрон и функция активации.

Для визуализации буду использовать собственноручно нарисованные картинки, что следует читать как: если увидите там какие-то ошибки, пишите, перерисую на правильные.

Итак так все готово для отправки в путь программного строительства бота. Начнем:

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

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

Здесь надо упомянуть волшебное слово Сериализация: это упаковка ваших данных в понятный сериализатору формат и возможность считывать эти данные обратно в программу c помощью сериализатора. Сериализаторов много, простейший последовательный формат записи в файл txt тоже сериализатор, но простой. Что нам нужно знать о сериализаторах, это то что они существуют и почти прозрачны в части API. Организаторы скорее всего это понимали и поэтому пример их бота содержит все необходимые инструкции по работе с сериализатором. В нашем случае это был JSON.

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

И так у нас есть Цикл, мера Цикла это Тик, сколько циклов прошло столько тиков набежало. Скорее всего мы больше не вспомним этот Тик, но он внесет ряд важный ограничений и упрощений: время на расчеты ограничены не только единичным Тиком, временем одной итерации цикла, но и суммарным временем расчетов, при превышении которых игровой сервер отключит вашего бота от управления. Тик это и время отдавать команды боту. Будем считать его квантом игрового Времени, Тик есть неделимая величина времени в игровом мире. Из этого вытекают и плюсы. Так как Тик по умолчанию равен 1, то скорости, ускорения и другие величины проще считать. Мы во всех формулах умножаем на 1, вместо использования в них какого-нибудь кривого времени t=0.0015 секунды. Погрешности этих операций так же минимальны.

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

Нейронная сеть тоже будет работать согласно Тикам.

Картинка начинает проясняться со стороны бота:

Сервер отправляет обработанные данные о мире боту->Начало Тика->бот принимает данные ->обрабатывает их->отдает серверу команды по управлению ботом-> Сервер читает данные->Конец Тика и далее по кругу или циклу почти бесконечному, 45000 тиков в финале на игру вполне существенная цифра.

Важное замечание: вы можете пропустить Тик и ничего вам за это не будет. Бывают случаи серверов, когда нужно каждый Тик что-то сообщать серверу, чтобы сервер не заподозрил бота в зависании управляющей программы.

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

• расчет коллизий ботов (обработка столкновений с границами игрового мира, кто кого съел, бот бота или бот еду, или столкновение с вирусом и тд)
• расчет физики ботов (движение ботов, изменение скоростей бота согласно командам бота или произошедшими коллизиям)
• расчеты связанные с делением ботов или их объединением если таковые возможны, добавлением еды и прочие функции для поддержания игрового мира.
• и конечно отправка и прием данных ботам по игровым Тикам.

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

картинка с сайта организаторов

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

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

Выбор нейронной сети и техника ее реализации.

На данный момент решим что нейронная сеть для нас черный ящик, который имеет вход и выход.

Входом и выходом для нас будут одномерные массивы с размерность N=16 на вход и размерностью M=4 на выход.

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

Экспериментально выбран следующий вариант (картинка упрощена до 8 сенсоров, и нейронной сети 4x3, но это исключительно чтобы запутать моего читателя):

Область обзора бота делится на равные(возможно сделать и неравные) сектора. Каждый сектор подает сигнал на один из входов нейронной сети. Соответственно, если мы разделили область вокруг бота на 16 секторов (360/12=22,5 градуса обзор сектора), то получаем 16 входов нейронной сети. Обычно на вход нейронной сети подают сигнал в пределах от -1 до 1. Поэтому потребуется нормировать входные сигналы.

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

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

рисунок

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

Сенсоры в виде секторов наиболее подходили к данному случаю, но могут быть просто щупы-усики, здесь фантазия на вашей стороне. Конечно автор опробовал различные варианты деления на сектора от 4 секторов до 72, но практика показала что нейронная сеть вполне успешно обучается на 16 секторах и готова управлять ботом даже при наличии четырех секторов. Здесь проявляется гибкость самой природы нейронной сети.

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

Размерность выходного сигнала мы установили равную 4. Это число есть проявление дуализма декартовых координат и полярных. Автор не забыл о природе знаний своего читателя и поэтому напоминает ему своим рисунком когда-то крепко усвоенные знания.

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

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

 float rotate1 = outputs[0];                 float rotate2 = outputs[1];                 float speed1 = outputs[2];                 float speed2 = outputs[3];                  if (rotate1 > 0.65 && rotate2 < 0.65)                     angle = angle + 35 * PI / 180;                 if (rotate1 < 0.65f && rotate2 > 0.65)                      angle = angle - 35 * PI / 180;                 if (speed1 > 0.65 && speed2 < 0.65)                     speed = speed + 2;                 if (speed1 < 0.65 && speed2 > 0.65)                     speed = speed - 2;                  dx = speed * Cos(angle);                 dy = speed * Sin(angle);

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

Вот и настало открыть черный ящик и заглянуть внутрь.

Продолжение следует.

Но перед новой серией тизер:

Фиолетовый бот на нейронной сети играет в Local Runner против стандартных ботов которые организаторы вшили в него по умолчанию.