Марио прошёл первый уровень, ловко перепрыгнул гумбу, воспользовался багом столкновений и уверенно двинулся дальше. За него играла программа, которая не видела экран, не знала правил и понятия не имела, что такое Марио, гриб или яма.
Всё, что у неё было, — 2048 байт оперативной памяти приставки и возможность отматывать время назад.
Работу сделал Tom Murphy VII, он же tom7, — исследователь с академическим бэкграундом и совершенно отвязным чувством юмора. Статья называется «The First Level of Super Mario Bros. is Easy with Lexicographic Orderings and Time Travel» и вышла в 2013 году на SIGBOVIK — полушуточной конференции, где работы при этом настоящие: с определениями, псевдокодом, графиками и воспроизводимым результатом.
Мне эта история нравится тем, что в ней нет ни одной нейросети. Разберу, как она устроена и почему двух килобайт памяти хватило, чтобы Марио дошёл до конца уровня.
А ещё она отлично показывает, как из простого критерия «числа растут» вылезает поведение, которое выглядит осмысленным, — и как тот же критерий приводит к решениям, от которых хочется схватиться за голову. С этим я сталкиваюсь каждый раз, когда ставлю задачу агенту и получаю формально верное выполнение не того, что имелось в виду.
Задача: пусть программа сама играет в любую игру на Денди
Вопрос ставился так: можно ли написать программу, которая играет в игры на NES — той самой Денди, — причём не в одну конкретную, а в любую?
Без знания правил. Без картинки на экране. Без звука. Программа вообще не в курсе, что происходит в игре.
У неё есть ровно два ресурса. Первый — 2048 байт оперативной памяти приставки. Второй — эмулятор, в котором можно сохраняться и откатываться на каждом кадре.
Стоит остановиться на объёме. 2048 байт — это вся память Денди целиком. Автор для наглядности нарисовал её как картинку размером 64 на 32 точки: там уместилось всё, что игра знает о себе. Сколько у Марио жизней, где он стоит, какой сейчас мир и уровень, какой счёт, что делают враги.
Для сравнения: одна фотография с телефона весит в тысячи раз больше, чем вся оперативная память приставки, на которой выросло несколько поколений.
Побеждать — это когда числа растут
Программа не видит экран и не понимает, что такое прогресс. Но у неё есть доступ к этим двум килобайтам, а в них лежит всё состояние игры.
Идея простая до наглости: посмотреть, какие байты растут, когда играет человек.
Номер мира растёт. Номер уровня растёт. Счёт растёт. Координата по горизонтали в основном растёт. Программа не понимает, что Марио идёт вправо, — она видит, что байт по некоторому адресу увеличивается, и делает вывод: вот это и есть «хорошо».
Технически это выглядит так. Есть адрес, по которому лежит горизонтальная координата, и адрес с номером мира. Программа не знает, что они значат. Она видит: пока человек играл, первый рос почти непрерывно, а второй иногда скачком менялся на единицу больше. Оба попадают в список «показателей успеха», и дальше Марио двигается туда, где эти числа больше.
Заметьте, что здесь нет никакого понимания игры. Есть статистика по числам, которые меняются согласованно. Примерно так же устроены и цепи Маркова: правил никто не задаёт, закономерность вытаскивается из наблюдений.
Лексикографический порядок проще, чем звучит
У наивной идеи есть дыра. В Марио вы идёте с уровня 1-1 на 1-2, потом 1-3, 1-4, а дальше попадаете на 2-1. Номер мира вырос с единицы до двойки, а номер уровня упал с четвёрки до единицы. По одному байту получается, что мы откатились назад.
Лечится это лексикографическим порядком. Название пугает, а суть — обычная сортировка как в словаре: сначала сравниваем первый элемент, при равенстве переходим ко второму, и так далее.
Пара «мир, уровень» со значением (1, 4) меньше пары (2, 1), потому что единица меньше двойки по первому элементу. Что второй элемент упал — неважно. Ровно так слово «баня» стоит в словаре раньше «борща», хотя вторые буквы идут не по порядку.
Работает это не только с парой. Можно собрать цепочку подлиннее — «мир, уровень, экран внутри уровня, позиция по горизонтали» — и получить функцию, которая описывает общее продвижение Марио.
Самое красивое: цепочки программа находит сама. Ей не говорят, какой байт что означает. Она смотрит запись человеческой игры и вычисляет, какие сочетания байтов растут устойчиво.
У этого есть неожиданное следствие. Чтобы программа заиграла в новую игру, её не нужно перепрограммировать — достаточно записать несколько минут своей игры. Всё, что она знает про Марио, она вытащила из вашей записи, и точно так же вытащит про любую другую игру.
Первый этап: обучение
Всё делится на две программы. Первая называется learnfun и занимается обучением.
Вы записываете, как играете сами. Не часами — несколько минут, пары уровней достаточно. Из этой записи программа достаёт две вещи.
Целевые функции — те самые лексикографические порядки на байтах памяти. Их генерируется не одна, а десятки, на разных кусках записи, чтобы результат не зависел от одного случайного «мнения».
Мотивы — типичные последовательности кнопок, которые нажимал человек. «Бежать вправо десять кадров», «прыгнуть и держать кнопку пятнадцать кадров». Это модель того, как живой игрок обращается с геймпадом.
Без мотивов ничего бы не вышло. Программа перебирала бы все 256 комбинаций кнопок на каждом кадре, и Марио дёргался бы на месте, не сдвигаясь ни на пиксель. Мотивы сужают перебор до осмысленных движений.
Второй этап: игра и путешествия во времени
Вторая программа — playfun. Она берёт целевые функции с мотивами и начинает играть. Здесь и начинается самое интересное.
Эмулятор детерминирован: в отличие от живой приставки, случайности в нём нет. Одни и те же нажатия всегда дают один и тот же результат. Это как сохранения в играх, только сохраняться можно на каждом кадре.
Сохранился, попробовал нажать, посмотрел на результат, откатился, попробовал другое. И так шестьдесят раз в секунду, если хватает мощности.
Программа держит сорок «будущих» — вариантов того, что может произойти дальше. Каждое будущее — последовательность кнопок на несколько сотен кадров вперёд, от секунды до тринадцати секунд игрового времени.
На каждом шаге она берёт первые десять кадров из каждого будущего, проигрывает вариант целиком, оценивает результат по целевым функциям, выбирает лучший и фиксирует его — эти десять кадров прожиты и назад не отматываются. Плохие будущие выбрасываются, хорошие мутируют и идут дальше.
Набор будущих не постоянный, он всё время обновляется. Варианты, которые привели к плохим числам, выбрасываются, а удачные копируются с небольшими изменениями — где-то кнопка нажата на пару кадров дольше, где-то вставлен другой мотив. Получается что-то вроде отбора: выживают последовательности, после которых Марио продвинулся дальше.
Важно, что фиксируются только первые десять кадров. Остальное будущее — черновик, нужный лишь для оценки. Программа как бы всё время смотрит на несколько секунд вперёд, но делает при этом маленький шаг.
Представьте, что вы можете в любой момент поставить игру на паузу, проиграть сорок вариантов на несколько секунд вперёд, выбрать лучший и продолжить с него. И делать так шесть раз в секунду.
Ещё одна тонкость: целевых функций несколько десятков, и они не всегда согласны между собой. Одна считает, что Марио продвинулся, другая — что откатился. Итоговая оценка складывается из всех, поэтому единичная кривая функция не портит игру целиком. Именно в расчёте этих весов и пряталась та самая ошибка, которая стоила автору шести выходных.
Как Марио уворачивается от врагов
Отсюда вытекает поведение, которое выглядит осмысленным, хотя никакого понимания за ним нет.
Наивный подход — выбирать то, что увеличивает счёт прямо сейчас — не работает. Когда гумба уже стоит перед вами, поздно: вы бежали ей навстречу, и через пару кадров вы мертвы, что бы ни нажали.
Поэтому каждый ход оценивается по тому, что будет через несколько сотен кадров. Если во всех будущих, начинающихся с «бежать вправо», Марио через три секунды мёртв, значит, бежать вправо сейчас плохо. Если будущие с прыжком выглядят прилично, значит, прыгаем.
В итоге Марио аккуратно перепрыгивает врагов и уворачивается с точностью, которой у человека не бывает. А ещё он пользуется багами. Например, прыгает на гумбу снизу — и вместо смерти убивает её, потому что в момент касания двигался вниз, и игра засчитала это как прыжок сверху.
Никто программу этому не учил. Баг просто оказался ходом, после которого числа росли, — а откуда взялся рост, ей безразлично.
Кстати, о нечеловеческой точности. Она берётся не из мастерства, а из того, что программа успевает попробовать. Живой игрок жмёт кнопку один раз и живёт с результатом. Марио здесь проигрывает десятки вариантов одного и того же прыжка и оставляет тот, где приземление вышло удачным. Со стороны это выглядит как филигранная реакция, а на деле — обычный перебор.
Монеты, тупик и шесть потерянных выходных
Самая драматичная часть истории — подземный уровень 1-2.
Сначала там узкий проход с врагами навстречу: нужно точно рассчитать момент прыжка. С этим программа справлялась по-разному — ждала, пинала черепах, запрыгивала идеально.
А сразу за проходом ловушка похуже. Полка с четырьмя монетами наверху. Счёт входит в целевую функцию, монеты дают очки — программа запрыгивала, собирала их и оказывалась в тупике. Внизу враги, выхода нет. Марио стоял и прыгал на месте, пока не кончалось время.
Автор потратил на эту проблему шесть выходных и тысячи часов процессорного времени. Добавил откат назад с повторной попыткой — не помогло. А потом, дописывая статью в самолёте, нашёл ошибку в расчёте весов целевых функций. Исправил — и Марио запрыгнул за монетами, тут же спрыгнул обратно и побежал дальше.
Обратите внимание, чем именно всё чинилось. Не новым алгоритмом, не увеличением числа будущих и не добавленной памятью. Обычной ошибкой в арифметике, из-за которой веса считались неправильно. Шесть выходных ушло на попытки усилить метод, а проблема была в опечатке уровнем ниже.
История на этом не кончается. Пройдя 1-2, Марио с разбегу прыгнул в первую же яму на 1-3.
Объяснение автора отрезвляющее: смерть выглядела для программы приемлемым вариантом. Откат на один экран — потеря небольшая, жизни в целевую функцию не входили, а остальные будущие всё равно не доставали дальше. Формально она выбрала лучшее из доступного. Просто «лучшее» было посчитано не по тому критерию.
Причём разбирался автор не в теории, а тем же способом, которым отлаживают любой код: смотрел записи неудачных попыток кадр за кадром и искал, где расчёт расходится с ожиданием.
Что было на других играх
Ту же программу с теми же настройками запустили на других играх, без подгонки под каждую.
Тут важна деталь: настройки не менялись под каждую игру. Одна и та же программа, один и тот же способ обучения, только запись человеческой игры своя. Всё остальное поведение — уже её собственные выводы из чисел.
Adventure Island. Мастер Хиггинс на скейтборде роняет здоровье почти до нуля, а потом начинает осторожничать. Получив оружие, метко стреляет по врагам, которые ещё не появились на экране. Погиб, прыгнув в череп с огненными шарами.
Pac-Man. Отматывание времени даёт нечеловеческое преимущество: он заранее знает, куда повернут призраки. Гоняет их по коридорам, протискивается в щель между двумя и уходит невредимым. Проиграл на том, что оставшиеся точки оказались дальше, чем достаёт любое из будущих, — и побежал прямо на призраков.
Karate Kid. Тратит все суперудары на самых слабых противников, дерётся спиной к врагу, бьёт в пустоту. Дошёл до финала и свёл здоровье к нулю одновременно с боссом — а при ничьей побеждает компьютер.
Bubble Bobble. Сначала бездумно тратит жизни: возрождение работает как бесплатная телепортация в угол, и по числам это выгодно. Потом начинает играть почти по-человечески — стреляет пузырями, лопает их, убивает монстров. И научился ставить игру на паузу, когда всё плохо: ждёт, пока среди будущих не появится приличное, и снимает с паузы. Прошёл дальше, чем человек в обучающей записи.
Тетрис. Провал. Несколько секунд программа входит и выходит из меню, потом укладывает фигуры хуже случайного выбора. Ноль линий. Единственное разумное действие — перед самым заполнением экрана она ставит паузу и больше её не снимает.
Color a Dinosaur. Детская раскраска без целей и правил. Программа хаотично раскрасила двух динозавров. Ошибиться здесь физически невозможно.
Отдельно стоит сказать про подачу. Статья написана с убийственным юмором: автор придумал шкалу оценки буквально для всего, честно перечисляет свои провалы, костыли и параметры, за которые ему стыдно. Финал Karate Kid он оценил по шкале «от премии Дарвина до достойной смерти». При этом работа абсолютно серьёзная — с математическими определениями, псевдокодом и графиками.
Где такой подход ломается
Провал на тетрисе интереснее любого успеха, потому что показывает границу метода.
В Марио прогресс виден в числах напрямую: координата растёт, номер уровня растёт, счёт растёт. Оптимизируй их — и движешься к победе. В тетрисе это не так. Счёт растёт только в момент, когда линия уже собрана, а вся работа до этого — аккуратная укладка фигур — в числах никак не отражается. Между действием и наградой пропасть, которую перебор на несколько секунд вперёд не перепрыгивает.
Второе ограничение — горизонт. Программа видит на несколько сотен кадров вперёд, и всё, что дальше, для неё не существует. Пакмэн проиграл ровно поэтому: точки оказались дальше горизонта, а внутри горизонта все варианты выглядели одинаково бесперспективно. Раз разницы нет, выбор становится случайным — и он побежал на призраков.
Третье — то, что в критерий не попало. Жизни Марио не входили в целевую функцию, и прыжок в яму оказался дешевле, чем топтание на месте. Программа не сломалась. Она честно выбрала лучшее по тем числам, которые ей выдали за меру успеха.
И четвёртое, самое неприятное: программа не отличает выигрыш от эксплуатации бага. Марио, убивающий гумбу снизу, и Марио, честно перепрыгивающий её, для целевой функции неразличимы. Пока баг даёт рост чисел, он такой же законный ход.
Все три ограничения — не про старую программу 2013 года. Это ровно те грабли, на которые наступают сегодня: близорукий критерий, слишком короткий горизонт планирования и забытое ограничение, о котором никто не подумал заранее.
Пауза в Bubble Bobble и в тетрисе — вообще отдельный сюжет. Никто не закладывал в программу идею «переждать». Просто среди кнопок есть Start, а состояние с паузой по целевым функциям не хуже текущего — и в безнадёжной ситуации оно оказывается лучшим доступным ходом. В тетрисе это довели до логического конца: перед самым проигрышем программа ставит паузу и не снимает её никогда.
Сколько это стоило
Дорого. Примерно час реального времени уходит на тысячу кадров вывода — это шестнадцать секунд игры. Одна секунда Марио обходится в четыре минуты процессорного времени.
Чтобы ускориться, автор написал систему распараллеливания, которая гоняет десятки эмуляторов одновременно по сети. Загрузка процессора — сто процентов на всех двенадцати ядрах. Собственный комментарий автора: греет спальню.
Почему это до сих пор интересно
Работа вышла в апреле 2013 года. Знаменитая статья DeepMind, где нейросеть училась играть в игры Atari, — в декабре того же года.
Подходы противоположные. У DeepMind обучение с подкреплением и нейросеть. У tom7 — перебор, простейшая статистика и грубая сила эмуляции. Ни одного нейрона.
При этом программа:
- не знает правил игры;
- не видит экран;
- не понимает, что такое Марио, враги и ямы;
- работает с 2048 байтами памяти;
- запускается на любой игре NES без переобучения.
И проходит уровни, обходит врагов и эксплуатирует баги. Меня тут цепляет не столько результат, сколько вывод: «понимание» задачи оказалось необязательным. Хватило измеримого признака успеха и возможности много раз попробовать.
Та же мысль вылезает в современных задачах: результат вытаскивает не понимание, а хорошо выбранный измеримый критерий. Похожая логика была и в истории с капчей, где полезная работа получалась побочным продуктом совсем другого действия.
Практический вывод я для себя вынес такой: если задачу можно свести к измеримому признаку, половина работы сделана, и метод может оказаться до смешного простым. А если признак подобран криво, то никакая мощность не спасёт — она просто быстрее приведёт вас не туда.
И обратная сторона тут же: критерий, в который забыли включить жизни, отправляет Марио в яму. Программа не ошиблась — она честно оптимизировала то, что ей дали.
Исходный код и видео автор выложил открыто, и видео стоит посмотреть — особенно момент, где Марио после героического прохождения сложного участка решительно прыгает в первую попавшуюся яму.
