Хабрахабр

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Показать больше

Похожие публикации

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»