Заключительная часть.
В предыдущих главах(часть1, часть 2 , часть про GPU) мы коснулись условий конкурса, нейронной сети, генетического алгоритма, так что продолжим.,
Но прежде чем продолжить, ссылка на GitHub c исходниками на c++ и чтобы поддержать заголовок статьи — исполняемый файлом под oc Windowsd в папке bin, который вполне похож на screeen saver.
В прошлой статье мы остановились на архитектуре программы, которая состоит из двух отдельных частей, часть содержащая только нейронную сеть и протокол связи с игровым сервером организаторов конкурса и основной части, состоящей из следующих блоков:
Коротко о каждой из частей.
Физический движок. За основу взят модуль расчетов физики в официальных исходниках, добавлены расчет сенсоров бота, фитнесс функция.
Нейронная сеть. Про нее мы довольно подробно поговорили в прошлом, поэтому буду считать, что здесь тоже всё ясно, тем более вопросов от читателей особо не поступало.
Генетический алгоритм. В освещении его реализации остались пробелы. Сейчас скорее всего повторюсь, но думаю по тексту так будет проще.
Из слайда презентации много вспомнилось. Поэтому остался главный вопрос как двигать эволюцию. Для этого придумана Fitness function (Фитнесс функция). Главной задачой фитнесс функции является отбор генотипов для передачи из текущей популяции ботов в последующую.
Как происходит выбор фитнесс функции стало скорее всего понятно. Вопрос скрещивания остался.
Существует несколько основных методов скрещивания, подробнее по ссылке. Но принцип основной принцип случайный обмен генами между генотипами родителей. Родителей обычно выбирается двое, методов выбора родителей из популяции тоже несколько, по ссылке можно освежить память. Выбор родителей производится случайно, но вероятность выбора конкретного родителя растет пропорционально его фитнесс функции.
Получили новую популяцию и далее эволюция продолжается до нужного нам результата. Есть несколько моментов, первый чем больше ботов тем быстрее генетический алгоритм найдем оптимальное решение (оптимальное соотношение весов в нейронной сети). К примеру если у бота 1000 генов то пространство поиска существенно расширяется при размере популяции 3000 ботов чем при популяции в 300 ботов. Но возникает другая проблема, если выпустить все 3000 ботов на арену рассчитанную на 4-8 ботов, то скорее всего из там будет физически тесно и если они и научатся чему-то, то точно не игре в Агарио. Поэтому существуют два основных способа, первый выбирать из популяции поочередно несколько ботов и проводить их состязание на арене, и так много раз, пока не накопит статистку по всем ботам. Второй, которым пошел автор, это запуск параллельно несколько арен допустим 100 или 300, все зависит от мощности конкретного компьютера и параллельно все боты участвуют в состязаниях. Популяция можно разбить на подпопуляции со своими фитнесс функция, а далее обменивать генотипы между подпопуляциями или представить все как одну большую популяцию ботов. Автор пробовал и так и так, но в исходниках вариант с общей популяцией ботов.
Скорее всего уже рассказал основные принципы построение программы. Кто хочет увидеть живую добро пожаловать по ссылке на ГитХаб.
если не получится запустить, то короткое видео скрасит это момент:
В августе mail.ru организует очередной AI mini cup, официального анонса еще не видел правда. Но по информации из телеграмм группы в основе конкурса снова физический движок, что-то на тему машинок. Поэтому коротко о принципах создания бота, тем кому будет интересно конечно:
Здесь как у нашей сборной по футболу, желательно выйти из группы, финал это отдельная песня. Пусть финалисты и пишут о победах, а у нас главное участие.
Самый понятный и простой :
Пишите в теле кода бота побольше разных условий, например if(ямка)-> прыгай и т.д. Простые условия эффективны в начале чемпионата, потом сложность ботов подрастет и преимущество условных решений уйдет.
И так самый перспективный во многих стратегических играх метод:
Метод ПП (или потенциальных полей). Идея красивая, поиск максимума или минимума в динамическом окружении. В основном 2D реализации, хотя 3D будет круто смотреться, но ресурсов много ест.
Самый сложный:
Две основных реализации это метод Brute Force (Полный перебор) или Метод МонтеКарло. Каждый из них это тема отдельной статьи, но по ощущению именно эти методы приведут вас к финалу.
В исходниках на вход нейронки подаются сигналы текущего Тика и предыдущего Тика, стало интереснее, спасибо читателю: tongohiti за идею.
Тем кто вспомнит тезис о начальном распределении весов в нейронной сети, интересная тема Распределение Xavire.
Спасибо за внимание. Встретимся на AI соревнованиях.
Источник
