Нейроэволюционный алгоритм учится играть в Mario
SethBling известен своим каналом, на котором он размещает различные советы и изобретения для мира Minecraft. Часто там появляется иной контент. К примеру, в список интересов влогера входит Mario. Именно SethBling первым прошёл Super Mario World на консоли с помощью бага с редактированием памяти путём перемещения предметов в игре. В его последних видео и стримах всё та же игра. Но играет уже не человек, а нейроэволюционный алгоритм, который SethBling сам и написал.
Реализация получила название MarI/O. Графическое представление нейронной сети выполнено в верхней части экрана. Слева показано, как алгоритм видит уровень — он понимает окружение и положение игрока. Белые квадраты — это блоки, на которых игрок может стоять, чёрные — двигающиеся объекты. Справа расположены кнопки, на которые может нажимать нейронная сеть. Связи-нейроны расположены посередине, лишь часть из них используется в любой момент времени.
Структура сложна, но SethBling не создавал нейронную сеть. Этим занималась его реализация нейроэволюционного алгоритма. Программа пыталась выполнять действия, затем их эффективность оценивалась по пройденному расстоянию. Обучение заняло сутки. Нулевое поколение было очень глупым, некоторые особи просто стояли на месте. Если игрок стоял слишком долго, то симуляция обрывалась. Некоторые научились идти вперёд, игнорируя наличие препятствий и врагов. Это приводило к встрече с врагами и пулями, но был хоть какой-то прогресс.
Одна из особей нулевого поколения. Зелёная линия — это позитивное соединение. Если в неё попадёт блок, то на выход будет передан тот же цвет. Этот нейрон заставляет игрока двигаться вперёд, пока перед ним есть платформа. Красная линия — негативное, и на выходе получается противоположный от полученного цвет.
После встречи с несколькими врагами над головой игрок несколько раз прыгает и оказывается на платформе, которая заканчивается обрывом. Поскольку в нужном месте больше нет блока, эта особь здесь и останавливается. Более сложные и, возможно, более успешные особи имеют больше нейронов, но принцип работы остаётся тем же.
Чтобы заставить нейронную сеть учиться, применяется отбор. Производительность каждой особи оценивается по пройденному расстоянию и скорости. Лишь самые эффективные особи подвергаются скрещиванию в следующее поколение, затем происходят мутации. Процесс повторяется нужное количество раз. Для прохождения одного уровня потребовалось 35 поколений. Самая совершенная особь получила значение приспособленности порядка 4000.
SethBling не придумал принцип работы с нуля. При создании он использовал уже существующую научную работу по NEAT (NeuroEvolution of Augmenting Topologies), нейроэволюции нарастающих топологий. В ней также описывается, как поколения можно разделять на виды, что пытаются делать не все генетические алгоритмы. MarI/O был написан на Lua с помощью эмулятора BizHawk.
SethBling не остановился на проделанном. Он заставил алгоритм проходить другие платформеры, транслируя процесс обучения в своём аккаунте Twitch. В числе игр был и классический Super Mario Brothers. MarI/O смог пройти первый уровень, но застопорился уже на втором. Даже несмотря на неудачу алгоритм случайно обнаружил небольшой баг, который потенциально может пригодиться спидранерам.
Некоторые особи застревали на одной из стен на уровне Donut Plains 4 в Super Mario World. Потребовалось некоторое время, чтобы понять, что на стену нужно забегать, на неё не нужно прыгать. Следующее поколение уже умело забегать на стену, но на следующем препятствии особи застопоривались — они разучились прыгать перед препятствием. Ещё через несколько поколений алгоритм понял, где нужно зажимать кнопку влево, а где прыгать.
MarI/O так и не смог закончить тот уровень. Одна из труб слишком высока, чтобы на неё запрыгнуть. Вместо этого нужно использовать платформу одного из Братьев Молота. SethBling прервал процесс обучения, посчитав, что алгоритм этому никогда не научится.
В третьем видеоролике MarI/O играет в Super Mario Kart в режиме Time Trial без врагов. Winterbunny помог с модификацией скрипта для работы в этой игре. Хотя Super Mario Kart отлична от платформеров, процесс обучения проходит так же. Вначале алгоритм глуп и не может выполнять никакие действия. Особи лишь пытаются нажимать на те или иные кнопки. Но даже в нулевом поколении нашлись особи, которые неплохо научились ехать.
Уже в седьмом поколении нашлась особь, которая проехала 5 кругов за 2,5 минуты. Этот показатель плох, мировой рекорд составляет порядка минуты. Особь постоянно натыкалась на препятствия и иногда наматывала круги. Особь из девятого поколения показала неплохой результат в 1,5 минуты, она даже пыталась держаться на дороге, не выезжая на обочину.
Исходный код MarI/O на Pastebin
Другой Twitch-канал, где MarI/O учится проходить различные игры
