Недавно я наткнулся на популярный пост в блоге о создании уровней для Super Mario Bros, и это было действительно круто.
Он дает отличный общий обзор того, как создавать уровни для игры, от выбора функций до обучения, с впечатляющими результатами. Для кого-то вроде меня, никогда раньше не работавшего с машинным обучением, оно помогло демистифицировать этот процесс. В то же время он упустил много деталей низкого уровня, которые я надеюсь заполнить.
В этом посте я опишу все шаги, которые я предпринял для создания уровней и прохождения их в исходной игре, от извлечения необработанных данных уровня до получения разумного результата. Демонстрация уровня, созданного сетью, доступна здесь, а также на Super Mario Maker. Полный исходный код доступен здесь.
Формат уровня
Формат уровней в игре довольно прост, хотя в нем есть несколько причуд, предназначенных для экономии места на картридже. Мне не удалось найти никакой документации по оригинальной игре, хотя ее порт для Super Mario All Stars имеет довольно похожий формат уровней, который хорошо документирован.
Самый простой способ найти места в ROM, которые нужно изменить, если вы хотите редактировать уровни, - это открыть шестнадцатеричный редактор и выполнить поиск. Если посмотреть на разборку игры, все данные уровня (и соответствующий им номер мира / уровня) задокументированы. Затем вы можете найти первые несколько байтов уровня в ПЗУ. Например, объекты уровня для W1–1 хранятся по смещению 0x269E, а вражеские объекты хранятся по адресу 0x1f11 в версии файла rom для США.
Я взял из разборки данные об уровне и противнике и поместил их в один большой массив для вывода (см. Исходник). Сам формат уровня на самом деле довольно легко проанализировать. Вот W1–1:
0x50, 0x21, 0x07, 0x81, 0x47, 0x24, 0x57, 0x00, 0x63, 0x01, 0x77, 0x01, 0xc9, 0x71, 0x68, 0xf2, 0xe7, 0x73, 0x97, 0xfb, 0x06, 0x83, 0x5c, 0x01, 0xd7, 0x22, 0xe7, 0x00, 0x03, 0xa7, 0x6c, 0x02, 0xb3, 0x22, 0xe3, 0x01, 0xe7, 0x07, 0x47, 0xa0, 0x57, 0x06, 0xa7, 0x01, 0xd3, 0x00, 0xd7, 0x01, 0x07, 0x81, 0x67, 0x20, 0x93, 0x22, 0x03, 0xa3, 0x1c, 0x61, 0x17, 0x21, 0x6f, 0x33, 0xc7, 0x63, 0xd8, 0x62, 0xe9, 0x61, 0xfa, 0x60, 0x4f, 0xb3, 0x87, 0x63, 0x9c, 0x01, 0xb7, 0x63, 0xc8, 0x62, 0xd9, 0x61, 0xea, 0x60, 0x39, 0xf1, 0x87, 0x21, 0xa7, 0x01, 0xb7, 0x20, 0x39, 0xf1, 0x5f, 0x38, 0x6d, 0xc1, 0xaf, 0x26, 0xfd,
А вот данные врага:
0x1e, 0xc2, 0x00, 0x6b, 0x06, 0x8b, 0x86, 0x63, 0xb7, 0x0f, 0x05, 0x03, 0x06, 0x23, 0x06, 0x4b, 0xb7, 0xbb, 0x00, 0x5b, 0xb7, 0xfb, 0x37, 0x3b, 0xb7, 0x0f, 0x0b, 0x1b, 0x37, 0xff,
Данные уровня начинаются с двухбайтового заголовка с информацией о времени, типе фона и о том, как Марио начинает уровень. Затем каждые два байта представляют объект уровня, например блок вопросов или ряд кирпичей.
Формат объекта уровня - XXXXYYYY POOOOOOO. Первый полубайт представляет позицию x на странице из 16 блоков, затем позицию y. В следующем байте старший бит показывает, является ли объект началом новой страницы. Остаток указывает, какой это тип объекта.
Например, 0x07 0x81 имеет x = 0, y = 7, p = 1 и o = 1. То есть это блок вопросов, 7 блоков от верхней части экрана и 16 блоков на уровне.
Формат вражеского объекта аналогичен, за исключением заголовка. Для получения более подробной информации о формате уровня ознакомьтесь с документацией Super Mario All Stars.
Однако самая сложная часть чтения на этих уровнях - это ограничение в 2–3 объекта на координату y. Я не могу найти однозначного правила, но размещение более двух объектов иногда приводит к повреждению уровня, в результате чего следующая страница не загружается. В оригинальной игре это обходится за счет «группируемых» объектов. Например, если o = 0x21, это будут два горизонтальных кирпича. Если o = 0x22, то будет три.
Чтобы загрузить уровни из текстового файла, эмулятор сначала ищет объекты, которые можно сгруппировать по вертикали, а затем по горизонтали. Хотя это, возможно, и не оптимально, похоже, позволяет обойти ограничения.
Использование Torch-RNN
Я выполнил шаги на https://github.com/jcjohnson/torch-rnn, используя образы докеров CUDA. Я передал -v /home/justin/ml:/data докеру, чтобы сопоставить папку ~ / ml в моей домашней папке с / data в виртуальной машине, таким образом я мог получить данные для обучения и выровнять данные.
Первые попытки обучения
Сначала я попытался вывести уровни с их типом блока в качестве первого символа строки, за которым следуют остальные объекты для этого вертикального среза уровня:
1 1 1 1 1 ? 1 1 1 1 b 1 ! 1 g b ? 1 ? 1 b 1 1 1 1 pp 1 1 1 1 1 1 1 1 1 1 ppp 1 1 g 1 1 1 1 1 1 pppp 1 1 1 1 1 1 1 1 g 1 g 1 1 pppp
Хотя этот формат было легко читать, нейронной сети было гораздо труднее улавливать закономерности. Сгенерированные уровни были далеко не идеальными:
Ясно, что этот формат не сработал, и поэтому я постарался максимально приблизиться к исходной статье. Моя следующая попытка формата уровня выглядела так:
==............ ==............ ==............ ==............ ==............ ==...?........ ==............ ==............ ==............ ==...b........ ==...!........ ==g..b...?.... ==...?........ ==...b........ ==............ ==............ ==............ ==pp.......... ==pp.......... ==............ ==............ ==............ ==............ ==............ ==............ ==............ ==............ ==ppp......... ==ppp......... ==g........... ==............ ==............ ==............ ==............ ==............ ==pppp........ ==pppp........
Вместо того, чтобы напрямую считывать тип блока, код ищет тип блока, который охватывает наибольшее количество блоков, без перехода. Затем он заполняет оставшиеся = блоки кирпичами. Хотя это дало лучшие результаты, я по-прежнему не мог получить ничего игрового.
Я обратился к Адаму Гейтгей, автору оригинальной записи в блоге, и он посоветовал мне попытаться упростить формат и поэкспериментировать с различными параметрами на torch-rnn. В частности, он посоветовал мне попробовать использовать меньшую сеть, так как у меня не так много данных. Я пробовал множество различных комбинаций размера сети, количества эпох обучения и температуры выборки, но ничего не помогло. У меня просто не хватило данных.
Еще одно предложение Адама заключалось в использовании графического процессора для обучения. Это сэкономило мне столько дней тренировок.
Успех
Я наконец добился успеха, повторяя уровни несколько раз в случайном порядке в обучающих данных. Хотя обычно это приводит к переобучению, в данном случае, похоже, все прошло нормально. Возможно, у кого-то, более осведомленного в этом вопросе, может быть лучший подход - вполне вероятно, что некоторая комбинация сетевых параметров могла бы дать тот же эффект с меньшим повторением.
Ключевыми факторами, которые, по-видимому, улучшили результаты, были:
- Меньше тренировочных эпох. Я продолжал увеличивать количество тренировок, надеясь, что это улучшит сетку. Я дошел до 20000 эпох, но в итоге кажется, что где-то между 20 и 80 - это магическое число. Больше тренировок! = Лучшие результаты.
- Больше повторений. Я читал в Интернете, что повторение данных в вашем обучающем наборе обычно плохо, так как обычно приводит к переобучению. В данном случае вроде бы получилось, но в идеальном мире было бы предпочтительнее больше данных. Есть множество игр Mario и пользовательский контент, на котором можно учиться.
- Больше данных. Я добавил несколько уровней из второй игры Super Mario Bros: The Lost Levels. Это придавало результату более сложный вид, хотя, казалось, помогало избежать переобучения.
Окончательные настройки, которые я использовал для генерации уровня выше, были ~ 20 эпох (я использовал 10000-ую контрольную точку), каждый уровень повторялся 20 раз и случайным образом перемешивался со всеми параметрами torch-rnn по умолчанию. Необработанный вывод выглядел так:
I....... .Ik........... ..I........... ..I........... ..I.........K. ..I........... ..I.....0..... .....I..0..... .....I........ .....I........ .....I........ .....I........ .....I........ .....I........ .....I........ .....I...I.... .....I........ .....I........ .....I........ .....I........ .....I........ .....I........ .....I........ .....I........ .....I........ .............. .............. .............. .............. .........<.... .........<.... .........I.... .........I.... .........I.... .........I.... .........I.... .........I.g.. .............. .............. .............. ==-........... ==............ ==............ ==............ ==............ ==............ ==............ ==............ ==............ .............. .............. ......0....... ......00...... .........0... ==...?........ ==...?........ ==............ ==............ ==............ ==k.......0... ==............ ==............ ==............ ==----........ ==............ ==............ ==...?........ ==...?........ ==...?........ ==..........b. ==............ ==pp.....b.... ==pp.....b.... ==.......b.... ==.......b.... ==.......b.... ==............ ==g........... ==g........... ==............ ==............ ==............ ==----........ ==------...... ==------...... ==............ ==............ ==k........... ==............ ==............ ==............ ==............ ==............ ==..8......... ==............ ==............ ==............ ==............ ==F........... ==............ ==............ ==A........... ==A........... ==............ ==............ ==............ ==............ ==............ ==............ ==............ ==............ ==............ ==............ ==............ ==............ ==............ ==............ ==............ ==............ ==............ ==............ ==............ ==............ ==............ ==............ ==............ ==............ ==............ ==............ ==............ ==............ .............. ==............ ==............ ==............ ==.8.......... ==............ ==............ ==............ ==............ ==............ ==............ ==............ ==............ ==............ ==8.8.........
Так продолжалось до конца уровня. Я вручную удалил первый незавершенный уровень, добавил небольшой заголовок уровня, чтобы указать тип уровня, и добавил флагшток в конце. Все остальное совершенно не модифицируется.
Следующие шаги
Есть множество возможностей для создания уровней. Есть еще много игр, в которых нужно собрать гораздо больше данных. В частности, серия игр New Super Mario Bros имеет много уровней в едином стиле, что идеально подходит для применения машинного обучения. Кроме того, другие алгоритмы, такие как генетические алгоритмы, процедурная генерация и цепи Маркова, могут обеспечить часы интересного нового контента.
Если вы хотите поиграть с torch-rnn самостоятельно, у меня есть полный исходный код для генерации обучающих данных и воспроизведения сгенерированных уровней, доступных на Github. Он также включает файлы контрольных точек, которые я использовал для создания уровня выше, если вы хотите пропустить обучение (самая интересная часть).
Я никогда раньше не занимался машинным обучением, поэтому, если вы обнаружите какие-либо грубые ошибки, сообщите мне. Удачи!
