Нейроэволюционный алгоритм учится играть в 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 учится проходить различные игры
    Поделиться публикацией
    Комментарии 13
      +11
      Судя по видео алгоритм не различает типы врагов, т.е. он не знает будет ли этот враг в него, например, стрелять. Следовательно алгоритм работает только за счет того, что уровни в марио не рандомные, по сути это не обучение, а брутфорс — перебор вариантов действий на каждом участке до нахождения правильного.
        +4
        На самом деле играя делаешь примерно тоже. И в марио и особенно в super meat boy заметно. Ты просто заучиваешь последовательность действий. А враги всегда на тех же позициях и всегда в том же состоянии инициализации. И можно прям заучить как бежишь, тут прыжок а потом вот все три молотка будут в подходящей позиции и их пробегаешь. Стоит затупить где-то и всё уровень провален.
          +1
          брутфорс — это полный перебор, чтобы его осуществить понадобилось бы в разы больше времени. Этот алгоритм ищет решение для конкретного уровня за конечное время.
            +10
            за конечное время.

            Нет. И это надо чётко понимать. Нет никаких гарантий что алгоритм найдёт за конечное время хоть что-то полезное.
              +5
              Так же было и со мной, когда я играл на приставке(
          +3
          Я не совсем понимаю, почему алгоритм сделан так, что видит все непроходимые блоки (стены, пол) одинаковыми? Ведь если бы он их различал и запоминал — все было бы быстрее, нет? Типа видит новый тип стены — пытается перепрыгнуть. Не получается? Пробует другие варианты. Какой-либо подошел? Запоминает визуальный вид стены и впредь все следующие преодолевает так же. И то же самое с противниками.
            +1
            Скорость обучения может упасть с увеличением числа категорий. Либо он использует примитивный алгоритм классификации состояний, способный принимать лишь 0 и 1.
            +1
            Его реализация не учитывает рекуррентные соединения, и вобще не ждет пока нейрон получит все сигналы и использует его значение, больше к нему не возвращаясь. Я сейчас пишу эту штуку как раз.
              +1
              Когда допишите — сделаете статью? Искренне очень интересно почитать.
                +2
                Может быть. Я ведь еще не закончил писать, вдруг я не допишу из-за трудностей, которые то и дело вылазят. После первого прочтения статьи с NEAT, казалось, что все легко и описано, а как взялся писать, оказалось, что куча нюансов, которые сразу либо не заметил в статье, либо до сих пор там не нашел *смех*.
                +1
                Я уже не могу редактировать свой комментарий, так что вот.
                Я наконец дошел до момента, когда мне нужно писать часть с построением нейронных сетей из генотипа. И я понял, что его код без комментариев был слишком гениален для меня. Вобщем нейронам не нужно ждать, чтобы все входящие в него нейроны получили все свои сигналы и выпустили сигнал, потому что если мы забираем сигнал с какого-либо нейрона, который еще не спайкнул на текущем инпуте сети, это значит, что это рекуррентное соединение!
                +5
                Если внимательно посмотреть на инпуты модели, то там ничего нет кроме слоев уровня, ни врагов, ни монеток, ни блоков с секретами, ни обработки этих секретов, ни поиска секретных труб, а в гонке уход с трассы не отменяет фитнесс модели. То есть по сути модель не «видит» нифига кроме трассы и блоков, которые ее окружают и ее прогресс обучения не зависит от правильности прохождения трассы. А собственно фитнесс модели не учитывает ничего, кроме дистанции и времени.

                Поэтому результаты обучения ничтожны. Как выше написал grokinn — это брутфорс. А раз брутфорс то модель не применима на других уровнях и не применима при рандоме врагов/секретов/машин и трасс.

                Поэтому ценность полученных данных имеется только в виде нахождения идеальной траектории для одной конкретной локации и для неизменных параметров.

                Ценность этих данных в других местах нулевая. На другом уровне модель опять упрется в стену и будет там торчать, как и на Марио Карте в трубу.

                Вообще странно, что этот разработчик упорно игнорит эти вещи в своих видео и говорит о том, как марио «очень любит эту трубу».

                  0
                  Интересно, а это сможет?
                  Mario Frustration

                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                  Самое читаемое