Заключительная часть.

В предыдущих главах(часть1, часть 2 , часть про GPU) мы коснулись условий конкурса, нейронной сети, генетического алгоритма, так что продолжим.

Но прежде чем продолжить, ссылка на GitHub c исходниками программы на c++ и чтобы поддержать заголовок статьи — исполняемым файлом под ОС Windows в папке bin, который вполне похож на screeen saver. В подвале статьи организовал "зал славы" прошлых чемпионатов.

Итак, мы остановились на архитектуре программы, которая состоит из двух отдельных частей(программ), часть содержащая только нейронную сеть и протокол связи с игровым сервером организаторов конкурса(собственно игровой бот) и основной части, состоящей из следующих блоков:

Коротко о каждой из частей.

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

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

Генетический алгоритм. В освещении его реализации остались пробелы. Сейчас скорее всего повторюсь, но проще повторить лишний раз.

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

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

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

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

Вот и рассказал основные принципы построение программы. Кто хочет увидеть вживую добро пожаловать по ссылке на ГитХаб.

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

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

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

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

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

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

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

Две основных реализации это метод Brute Force (Полный перебор) или Метод МонтеКарло. Каждый из них это тема отдельной статьи, но по ощущению именно эти методы приведут вас к финалу. Если тезисно, то бот может смотреть не только текущее время или прошлое, а при желании может заглянуть в будущее, здесь возникает воронка(конус) возможных исходов и чем дальше бот хочет посмотреть тем больше вариантов появится. Например в момент времени Тик Ноль, бот решает пойти по одному из восьми направлений, в шаг Тик+1 в каждой из восьми новых координат у него появляется возможность пойти опять в восьми направлениях и т.д. надо учитывать возможные перемещения противника за это время. Каждому возможному исходу расчетов начисляется возможная польза или вред. Исходя из которых бот делает ход в одном из направлений. И далее такой расчет в глубину будущего времени идет каждый тик. Глубина просмотров ходов определяется возможными ресурсами компьютера. Поэтому при малых ресурсов компьютера возникает задача оптимизации этих расчетов.

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

Тем кто вспомнит тезис о начальном распределении весов в нейронной сети, интересная тема Инициализации Xavire.

Спасибо за внимание. Встретимся на AI соревнованиях.

Статьи по теме от участников, но сначала лирическое отступление:

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

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

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

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