Как чувак научил ИИ проходить Марио без знания правил игры

Есть один исследователь — Tom Murphy VII, он же tom7. Чувак из академической среды, но с абсолютно безумным чувством юмора. Он пишет научные статьи на конференцию SIGBOVIK (это такая полушуточная конференция по информатике, где работы при этом абсолютно настоящие), и одна из его работ — это шедевр.

Называется она «The First Level of Super Mario Bros. is Easy with Lexicographic Orderings and Time Travel» — «Первый уровень Супер Марио легко пройти с помощью лексикографических порядков и путешествий во времени».

«...after that it gets a little tricky» — «...а дальше начинаются сложности»

Оригинал статьи (PDF) | Видео и исходный код

Звучит как бред, но это 100% рабочая штука. Автор это подчёркивает прямо в тексте:

«Disclaimer for SIGBOVIK audience: This work is 100% real.»

«Дисклеймер для аудитории SIGBOVIK: эта работа на 100% реальная.»

Давайте разбираться, что он сделал.

Задача: пусть компьютер сам проходит игры на Dendy

Том задался вопросом: можно ли написать программу, которая будет сама играть в игры на NES (Nintendo Entertainment System, она же Денди)?

Причём не просто в одну конкретную игру — а в любую. Без знания правил, без понимания, что такое Марио, гриб, гумба или яма. Программа не видит экран. Не слышит звук. Она вообще не знает, что происходит в игре.

Всё, что у неё есть — это 2048 байт оперативной памяти приставки. И возможность крутить время туда-сюда через эмулятор.

Для понимания масштаба: 2048 байт — это ВСЯ память Денди. Автор даже нарисовал её целиком как картинку 64×32 пикселя. Вот она:

Это вся рабочая память, с которой работает любая игра на Денди. Там хранится всё: количество жизней Марио, его координаты, номер мира и уровня, счёт, состояние врагов. У автора на компьютере памяти в миллионы раз больше. Он решил, что пора это использовать.

Главная идея: мы не знаем правил, но знаем, что «побеждать» — это когда числа растут

Итак, программа не видит экран и не понимает, что такое «прогресс в игре». Но у неё есть доступ к памяти эмулятора — тем самым 2048 байтам, где хранятся все данные игры.

Идея гениально простая: посмотреть, какие байты в памяти растут, когда человек нормально играет. Номер мира? Растёт. Номер уровня? Растёт. Счёт? Растёт. Координата X (позиция на уровне)? В основном растёт.

«The central idea of this paper is to use (only) the value of memory locations to deduce when the player is "winning". The things that a human player perceives, like the video screen and sound effects, are completely ignored.»

«Центральная идея этой статьи — использовать только значения ячеек памяти, чтобы понять, когда игрок "побеждает". Всё, что воспринимает человек, — экран и звуковые эффекты — полностью игнорируется.»

То есть программа не понимает, что Марио идёт вправо. Она просто видит, что байт по адресу, допустим, 0x6D (координата X) — увеличивается. А байт 0x75F (номер мира) иногда скачком меняется с 1 на 2. Значит, мы «выигрываем».

Лексикографические порядки — это проще, чем звучит

Но тут есть проблема. В Марио вы начинаете в мире 1-1 и идёте к 1-2, потом 1-3, 1-4, а потом 2-1. Номер мира вырос с 1 до 2, а номер уровня упал с 4 до 1. Если смотреть только на один байт — кажется, что мы откатились назад.

Решение — лексикографический порядок. Это просто сортировка, как в словаре: сначала сравниваем первую букву, если одинаковая — вторую, и так далее.

Пара ⟨мир, уровень⟩ = ⟨1, 4⟩ меньше, чем ⟨2, 1⟩, потому что 1 < 2 по первому элементу. Неважно, что второй элемент упал. Точно так же слово «баня» идёт раньше «борщ», хотя вторые буквы идут не по порядку.

И это работает не только для пары мир-уровень. Можно собрать длинную цепочку: ⟨мир, уровень, экран внутри уровня, позиция X на экране⟩ — и получить функцию, которая описывает «общий прогресс» Марио.

Причём программа сама находит такие цепочки. Ей не надо говорить «вот этот байт — номер мира, а вот этот — счёт». Она просто смотрит запись того, как играет человек, и вычисляет, какие комбинации байтов стабильно растут.

Как это работает: обучение

Процесс разбит на два этапа. Первый этап — обучение (программа learnfun). Вы записываете, как играете в игру. Буквально несколько минут — прошли первый-второй уровень.

Программа берёт вашу запись и делает из неё две вещи:

Во-первых, целевые функции — те самые лексикографические порядки на байтах памяти. Она генерирует их десятки, на разных кусках записи, чтобы не зависеть от одного единственного «мнения».

Во-вторых, мотивы — типичные последовательности кнопок, которые вы нажимали. Например, «бежать вправо 10 кадров» или «прыгнуть и держать кнопку 15 кадров». Это модель того, как реальный игрок пользуется контроллером. Без мотивов программа пыталась бы перебирать все 256 комбинаций кнопок на каждом кадре, и Марио тупо дёргался бы на месте.

«On a scale from gravitational constant to pulled it out of my ass, this is an 8.»

«По шкале от "гравитационная постоянная" до "взял из задницы", это 8.»

Это автор про магическое число 10 — длину мотива. Он честно признаёт, что параметры он не особо тюнил.

Как это работает: игра

Второй этап — playfun, собственно программа-игрок. Она берёт обученные целевые функции и мотивы и начинает играть.

И вот тут начинается самое интересное — путешествия во времени.

Эмулятор — детерминированная штука. В отличие от реальной приставки, тут нет никакой случайности — одни и те же нажатия кнопок всегда дают один и тот же результат. Это как сохранения в играх, только можно сохраняться на каждом кадре. Сохранил → попробовал нажать что-то → посмотрел, что случилось → откатился → попробовал другое. И так 60 раз в секунду, если хватает мощности.

Программа поддерживает 40 «будущих» — возможных сценариев того, что может произойти дальше. Каждое будущее — это последовательность кнопок на несколько сотен кадров вперёд (от 50 до 800 кадров, то есть от секунды до 13 секунд игрового времени).

На каждом шаге программа:

1. Берёт первые 10 кадров из каждого будущего
2. Пробует каждый вариант — сохраняет состояние, проигрывает 10 кадров, потом проигрывает оставшееся будущее
3. Оценивает, какой вариант приводит к лучшему результату по целевым функциям
4. Выбирает лучший вариант и «коммитит» его — всё, эти 10 кадров мы прожили
5. Плохие будущие выкидывает, хорошие мутирует и продолжает

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

Марио учится избегать опасности — через будущее

Одна из крутых вещей — как программа обходит врагов. Наивный подход (просто выбирать то, что увеличивает счёт прямо сейчас) не работает. Потому что к моменту, когда гумба стоит прямо перед вами — уже поздно. Вы бежали навстречу, и через пару кадров вы мертвы, что бы вы ни нажали.

Поэтому программа оценивает каждый ход не по тому, что будет прямо сейчас, а по тому, что будет через несколько сотен кадров. Если во всех будущих, которые начинаются с «бежать вправо», Марио через 3 секунды мёртв — значит, «бежать вправо» сейчас плохая идея. А если будущие, начинающиеся с прыжка, выглядят хорошо — значит, прыгаем.

Марио чисто перепрыгивает гумб. Он лихо уворачивается от врагов. И самое смешное — он эксплуатирует баги игры. Например, он прыгает на гумбу снизу — и вместо смерти «убивает» его, потому что в момент контакта Марио двигался вниз, и игра засчитывает это как «прыжок сверху».

«playfun is happy to exploit bugs in the game; in this case, that whenever Mario is moving downward this counts as "stomping" on an enemy, even if that enemy is above him.»

«playfun с удовольствием использует баги игры: если Марио двигается вниз — это считается "прыжком на врага", даже если враг находится над ним.»

Проблема с монетами: когда жадность убивает

Самая драматичная часть истории — мир 1-2. Подземный уровень.

Сначала тут узкий проход с врагами, которые выходят навстречу. Это уже сложно — программа должна точно рассчитать момент прыжка. Марио находил разные решения: ждал, пинал черепах, идеально запрыгивал.

Но сразу после — ловушка пострашнее. Полка с четырьмя монетами сверху. Счёт — один из компонентов целевой функции, монеты дают очки. Программа прыгала на полку, собирала монеты... и оказывалась в тупике. Внизу враги, выхода нет. Марио стоял и тупо прыгал на месте, пока не заканчивалось время.

Автор потратил на эту проблему шесть выходных и тысячи часов процессорного времени. Добавил механизм бэктрекинга — откат назад и попытка заново. Не помогло.

А потом, пока писал статью в самолёте, обнаружил баг в коде расчёта весов целевых функций. Исправил — и всё заработало: Марио запрыгнул за монетами, сразу спрыгнул обратно и побежал дальше.

«Bugs matter, and thinking about your code and explaining it is a good way to find bugs.»

«Баги имеют значение, а обдумывание и объяснение своего кода — хороший способ их находить.»

А потом Марио прошёл 1-2... и тут же прыгнул в первую яму на уровне 1-3. Просто прям с разбегу.

«On a scale of OMFG to WTFLOL I was like whaaaaaaat?»

«По шкале от OMFG до WTFLOL я был типа чтоооооо?»

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

Это работает не только на Марио

Автор запустил программу на нескольких других играх с теми же настройками, без тюнинга. Результаты — от забавных до поразительных.

Hudson's Adventure Island. Толстячок Мастер Хиггинс на скейтборде. Программа не парится по поводу здоровья, роняя его почти до нуля, но потом аккуратничает. Когда получает оружие — метко стреляет по врагам, которые ещё даже не появились на экране. Погиб, прыгнув в череп с огненными шарами.

Pac-Man. Пакмэн получил сверхчеловеческое преимущество — «путешествия во времени» позволяют ему знать, куда повернут призраки. Он безумно храбр: гоняет призраков по коридорам, протискивается в щель между двумя призраками и возвращается невредимым. Но в итоге оставшиеся точки оказались слишком далеко от него, ни одно будущее до них не доставало — и Пакмэн побежал на призраков.

Karate Kid. Даниэль-Сан тратит все суперудары «Журавлиный пинок» на самых слабых противников, дерётся стоя спиной к врагу, кидает удары в пустоту. Дошёл до финала, свёл здоровье к нулю одновременно с боссом — но при ничьей побеждает компьютер. Автор оценил этот финал на 6 по шкале «Премия Дарвина → достойная смерть».

Bubble Bobble. Дракончик Баб поначалу тратит жизни (респаун = бесплатная телепортация в угол, логично). Но потом начинает играть как человек: стреляет пузырями, лопает их, убивает монстров. И самое смешное — он научился ставить игру на паузу, когда ситуация выглядит безнадёжной. Ждёт, пока среди будущих не появится хорошее, и снимает с паузы. Прошёл дальше, чем запись человека.

Тетрис. Катастрофа. Программа несколько секунд входит и выходит из меню, потом укладывает фигуры хуже рандома. Ноль линий, ноль тетрисов. Единственная умная вещь — она ставит игру на паузу перед тем, как экран заполнится, и не снимает с паузы. Как пишет автор: «Единственный выигрышный ход — не играть».

Color a Dinosaur. Детская «игра», где вы раскрашиваете динозавров. Цели нет, правил нет. Программа хаотично раскрашивает двух динозавров. Автор философски замечает: «В этой игре невозможно ошибиться — любая раскраска прекрасна».

Сколько это стоило вычислительно

Программа работает примерно час реального времени на 1000 кадров вывода — это 16 секунд игрового процесса. То есть одна секунда Марио стоит примерно 4 минуты процессорного времени.

Чтобы ускорить работу, автор написал MARIONET (каламбур: «Mario network» + «Marionette») — систему распараллеливания через TCP/IP, которая запускает десятки эмуляторов одновременно. Загрузка процессора — 100% на всех 12 ядрах. Автор комментирует: «Keeps the bedroom warm» — «Согревает спальню».

Почему это круто

Эта работа вышла в апреле 2013 года. Знаменитая статья DeepMind, где нейросеть училась играть в Atari, — в декабре того же года. Подходы совершенно разные: у DeepMind — глубокое обучение с подкреплением, у Тома — комбинаторный поиск + простейшая статистика + грубая сила эмуляции. Никаких нейросетей.

Программа:

• Не знает правил игры
• Не видит экран
• Не знает, что такое Марио, враги или ямы
• Использует только 2048 байт памяти
• Работает на любой игре NES без переобучения

И при этом проходит уровни, эксплуатирует баги, уворачивается от врагов с нечеловеческой точностью и находит творческие решения.

Вся статья написана с убийственным чувством юмора. Автор придумал шкалу оценки буквально для всего: «По шкале от X до Y это Z». Он честно описывает свои провалы, баги, костыли и параметры, за которые ему стыдно. И при этом работа абсолютно легитимная — с математическими определениями, псевдокодом, графиками и воспроизводимыми результатами.

Исходный код и видео доступны на tom7.org/mario. Видео — это вообще must watch, особенно моменты, когда Марио решительно прыгает в яму после героического прохождения сложного участка.

Такие дела. Иногда не нужны нейросети, миллионы параметров и тысячи GPU. Достаточно 2048 байт, путешествий во времени и шести потерянных выходных.