Алгоритм машинного обучения Flappy Bird

Я познакомлю вас с полным туториалом на HTML5 с демо по алгоритму машинного обучения видеоигре Flappy Bird. Цель этого эксперимента — написать игровой контроллер искусственного интеллекта на основе нейросетей и генетического алгоритма.

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

Прочитав теорию, лежащую в основе этого проекта, можно скачать исходный код в конце этого туториала. Весь код написан на HTML5 с использованием фреймворка Phaser. Кроме того, мы использовали библиотеку Synaptic Neural Network для реализации нейросети, чтобы не создавать её с нуля.

Демо

Для начала посмотрите демо, чтобы оценить алгоритм в действии:
Запустить в полноэкранном режиме

Видеопрезентация

В дополнение к демо вы можете посмотреть короткое видео с простым объяснением алгоритма. Понравится тем, кто любит получать информацию быстро!

Что такое «алгоритм машинного обучения»

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

Конкретно в этом проекте, основной подход к машинному обучению (machine learning algorithm, ML) основан на нейроэволюции. В этой форме машинного обучения используются эволюционные алгоритмы, такие как генетический алгоритм (genetic algorithm, GA), для обучения искусственных нейронных сетей (artificial neural networks, ANN).

То есть в нашем случае можно сказать, что ML = GA + ANN.

Искусственная нейронная сеть

Искусственная нейронная сеть — это подмножество алгоритма машинного обучения. За основу в ней взяты структура и функции биологических нейронных сетей. Эти сети созданы из множества нейронов, передающих сигналы друг другу.
То есть для создания искусственного мозга нам нужно симулировать нейроны и соединить их, чтобы они сформировали нейронную сеть.

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

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

1. слой входных данных с двумя нейронами представляет то, что видит птица:
   
   • горизонтальное расстояние до ближайшего промежутка
   • разница высот с ближайшим промежутком
2. скрытый слой с шестью нейронами
3. слой выходных данных с одним нейроном, создающий действие:
   • если выходные данные > 0,5, то сделать рывок, в противном случае не делать ничего

На рисунке ниже показана архитектура нейронной сети для этого примера:

Генетический алгоритм

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

Вот основные этапы реализации нашего генетического алгоритма:

1. создаём исходную популяцию из 10 объектов (птиц) со случайными нейронными сетями
2. даём всем объектам играть одновременно с использованием их собственных нейронных сетей
3. у каждого объекта вычисляем его функцию приспособленности для оценки его качества (подробнее см. в разделе Функция приспособленности)
4. после смерти всех объектов оцениваем текущее поколение для создания нового с помощью генетических операторов (подробнее см. в разделе Стратегия замены)
5. возвращаемся к этапу 2

Функция приспособленности

В дополнение к генетическому алгоритму (этап 3), мы рассмотрим здесь подробнее функцию приспособленности — что это такое и как её определить.
Поскольку мы хотим, чтобы популяция эволюционировала из наилучших объектов, нам необходимо определить функцию приспособленности.

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

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

Подведём итог: наша функция приспособленности — это разность между общим расстоянием, проделанным птицей, и текущим расстоянием до ближайшего промежутка.

Стратегия замены

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

1. сортируем объекты текущего поколения по их уровню приспособленности
2. выбираем четыре лучших объекта (победителей) и передаём их непосредственно в следующее поколение
3. создаём одного потомка как результат кроссинговера между двумя наилучшими победителями
4. создаём трёх потомков как результаты кроссинговера двух случайных победителей
5. создаём двух потомков как прямые копии двух случайных победителей
6. применяем к каждому потомку случайные мутации, чтобы добавить вариативности

Исходный код

И вот, наконец, ссылка для скачивания исходного кода:
https://github.com/ssusnic/Machine-Learning-Flappy-Bird

Алгоритм машинного обучения для Flappy Bird — заключение

В этом туториале мы успешно реализовали ИИ-робота для обучения игре во Flappy Bird. В результате нескольких итераций мы можем получить почти неуязвимого игрока. Для достижения этой цели мы использовали два подхода к алгоритмам машинного обучения: искусственные нейронные сети и генетический алгоритм.
Для эксперимента можете попробовать изменить некоторые из параметров в коде и посмотреть, что произойдёт. Например, вы можете изменить количество нейронов в скрытом слое или количество объектов в популяции. Кроме того, можете попробовать изменить функции приспособленности. Более того, попробуйте менять некоторые физические параметры — расстояния между препятствиями, гравитацию и так далее.

Попробуйте также применить тот же подход к эволюции в других играх.