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

Заключительная часть.
В предыдущих главах(часть1 ^[1], часть 2 ^[2], часть про GPU ^[3]) мы коснулись условий конкурса, нейронной сети, генетического алгоритма, так что продолжим.,
Но прежде чем продолжить, ссылка на GitHub ^[4] c исходниками программы на c++ и чтобы поддержать заголовок статьи — исполняемым файлом под ОС Windows в папке bin ^[5], который вполне похож на screeen saver. В подвале статьи организовал "зал славы" прошлых чемпионатов.
Итак, мы остановились на архитектуре программы, которая состоит из двух отдельных частей(программ), часть содержащая только нейронную сеть и протокол связи с игровым сервером организаторов конкурса(собственно игровой бот) и основной части, состоящей из следующих блоков:

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

Из слайда презентации многое вспомнилось. Поэтому остался главный вопрос: как двигать эволюцию? Для этого придумана Fitness function (Фитнесс функция ^[6]). Главной задачей фитнесс функции является отбор генотипов для передачи из текущей популяции ботов в последующую.

Как происходит выбор фитнесс функции стало скорее всего понятно. Вопрос скрещивания остался.
Существует несколько основных методов скрещивания, подробнее по ссылке ^[7]. Но основной принцип случайный обмен генами между генотипами родителей. Родителей обычно выбирается двое, методов выбора родителей из популяции тоже несколько, по ссылке ^[8] можно прочитать подробнее. Хоть выбор родителей производится случайно, но вероятность выбора конкретного родителя растет пропорционально его фитнесс функции.
Далее к готовому генотипу применяют функцию мутации ^[9].
В нашем случае время от времени алгоритм меняет произвольный выбранный ген на случайный ген, другими словами один из весов нейронной сети меняется на случайный.

Получили новую популяцию и далее эволюция продолжается до нужного нам результата. Есть несколько моментов, первый: чем больше ботов в популяции, тем быстрее генетический алгоритм найдем оптимальное решение или сойдется к решению (оптимальное соотношение весов в нейронной сети). К примеру, если у бота 1000 генов, то пространство поиска существенно расширяется при размере популяции 3000 ботов, в сравнении с популяцией в 300 ботов. Но возникает другая проблема, если выпустить все 3000 ботов на арену рассчитанную на 4-8 ботов, то скорее всего ботам на ней будет физически тесно и если они и научатся чему-то, то точно не игре в Агарио. Поэтому существуют два основных способа избежать перенаселения арены: первый выбирать из популяции поочередно несколько ботов и проводить их состязание на арене, и так много раз, пока не накопим статистку игр по каждому боту. Второй, которым пошел автор, это запуск параллельно несколько арен допустим 50-300, все зависит от мощности конкретного компьютера и параллельно вся популяция ботов участвуют в состязаниях. Популяцию можно разбить на подпопуляции со своими фитнесс функциями и индефикаторами (соответствует количеству арен), а далее обменивать генотипы между подпопуляциями. Или представить все как одну большую популяцию ботов играющую на разных аренах. Автор опробовал оба варианта, но в исходниках вариант с единой популяцией ботов. Параметр в программе Depth это и есть номер арены.
Вот и рассказал основные принципы построение программы. Кто хочет увидеть вживую добро пожаловать по ссылке на ГитХаб ^[4].

если не получиться запустить, то короткое видео скрасит это момент:

Анонс: В августе mail.ru организует очередной AI mini cup, официального анонса еще не видел правда. Но по информации из телеграмм группы в основе конкурса снова физический движок, что-то на тему машинок. Поэтому коротко о принципах создания бота, тем кому будет интересно конечно:

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

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

И так самый перспективный во многих стратегических играх метод:

Метод ПП (или потенциальных полей ^[10]). Идея красивая, поиск максимума или минимума в динамическом окружении. В основном 2D реализации, хотя 3D будет круто смотреться, но ресурсов много ест.

Самый сложный:

Две основных реализации это метод Brute Force ^[11] (Полный перебор) или Метод МонтеКарло ^[12]. Каждый из них это тема отдельной статьи, но по ощущению именно эти методы приведут вас к финалу.

Про исходники, если будет интерес отредактирую комментарии к коду, пока выложил как было.
В исходниках на вход нейронки подаются сигналы текущего Тика и предыдущего Тика, стало интереснее, спасибо читателю: tongohiti за идею.
Тем кто вспомнит тезис о начальном распределении весов в нейронной сети, интересная тема Распределение Xavire.
Спасибо за внимание. Встретимся на AI соревнованиях.
Статьи по теме от участников, но сначала лирическое отступление ^[13]:

Она сидела на полу
И груду писем разбирала,
И, как остывшую золу,
Брала их в руки и бросала.

Брала знакомые листы
И чудно так на них глядела,
Как души смотрят с высоты
На ими брошенное тело…

О, сколько жизни было тут,
Невозвратимо пережитой!
О, сколько горестных минут,
Любви и радости убитой!..

Моя стратегия на Russian AI Cup 2017 ^[14]
История участия (и почти победы) в ежегодном соревновании Russian AI Cup 2016 ^[15]
История победы на ежегодном соревновании Russian AI Cup 2015 ^[16]
Russian AI Cup 2014: стратегия победителя ^[17]
Золотая медаль на Russian AI Cup 2013 — как это все было ^[18]
Путь к серебряной медали на Russian AI Cup 2012 ^[19]

Автор: Geo Evclid

Источник ^[20]