Нейросети и Марио: анализ и генерация правдоподобных уровней

Несколько способов выявления структуры и автоматического создания локаций.

Прошло десять лет с момента создания исследовательского сообщества Mario AI, которое занималось поиском самых разных способов генерации уровней. Несмотря на то, что сообщество прекратило активную деятельность в 2012 году, работа над этой темой всё ещё столь же увлекательна, как и прежде. Существует множество типов уровней, которые можно сгенерировать, а также разные алгоритмы, отвечающие за это, поэтому тема достаточно обширна для детального обзора.

Автор блога AI and Games Томми Томпсон в своём тексте разобрал несколько подходов к автоматическому анализу и генерации уровней серии игр Mario. Он описал исследования, которые ранее проводились в рамках конкурса Mario AI, а теперь существуют благодаря энтузиазму отдельных людей. Мы выбрали из текста главное.

Сообщество Mario AI представило несколько направлений исследований, которые строились вокруг известной фигуры водопроводчика. Конкурс поставил перед исследователями задачу не только придумать систему, которая создавала уровни, вдохновлённые Super Mario Bros., но и попытаться настроить их на основе некоторые простые телеметрические данные о пользователе, который проходил уровень.

Получившиеся системы в течение следующих нескольких лет были довольно разнообразны как с точки зрения их работы, так и с точки зрения уровней, которые они создавали. Более поздние исследования стремятся подражать оригинальным тайтлам Марио. А все более ранние исследовательские проекты встраивали свои собственные знания о дизайне уровней Super Mario.

Это интересная область изучения сама по себе — что особенного в уровнях Super Mario? Дело в том, что, хотя, безусловно, есть аспекты общей эстетики, которые влияют на прохождение, более важной частью выступает логика и структура размещения объектов даже для самых простых уровней Mario.

Если дать кому-нибудь лист бумаги и карандаш, и попросить его нарисовать уровень Super Mario, он, вероятно, будет во многом отличаться от реальности, но, несомненно, будут некоторые общие элементы. Там будут кирпичные блоки; возможно, даже блоки с вопросом; трубы; гумбы и Купа Трупа. Там может быть яма, в которую можно упасть и умереть, или лестница, которая приведёт к флагу в конце уровня.

Сейчас исследования генерации уровней Super Mario продолжают процветать. Тем не менее самый большой сдвиг за последние годы — это попытки понять дизайн уровней Super Mario. Чтобы решить эту проблему, в более поздних исследователи избегают того, чтобы напрямую вводить свои собственные интерпретации дизайна уровней Марио, учитывая, что не существует абсолютного и полного набора правил, определяющих, как создаются уровни.

Самое последнее исследование с использованием машинного обучения обошло эту проблему, позволив алгоритму изучать уровни самостоятельно.

Прежде всего, стоит взглянуть на работу доктора Стива Дальскога — лектора в Университете Мальмё в Швеции. Работа Стива была направлена на оценку игр Super Mario с использованием шаблонов проектирования: выявления общих элементов в структуре уровней или механики. Его идея заключается в том, что, устанавливая правила построения игровых элементов, системы ИИ могут использовать эти знания в качестве средства для принятия разумных решений о том, как создавать новые уровни или даже игры.

Это исследование привело его к изучению процедурной генерации уровней-подземелий, а также систем оценки опыта игрока. Но большая часть его исследований, особенно в первые годы его докторской диссертации, вращалась вокруг Super Mario Bros.

Исследования Дальскога начинаются с определения 23 уникальных шаблонов дизайна на 20 наземных уровнях оригинальной Super Mario Bros., исключая подводные уровни и уровни замка. Эти шаблоны варьируются от поведения на микроуровне (цепочки гумб или пропасти) до макроуровня, где построение локации абстрактно (например, несколько вариантов пути или лестничные конструкции из труб, разделённых пропастями).

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

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

В 2014 году за этим последовали два проекта. Один изменил оценку уровня для записи моделей микро- и мезоуровней. Это привело к увеличению разнообразия. Второй — многоуровневый генератор, который построил уровни на разных уровнях абстракции: начиная с уровня макрошаблона, а затем переходя к мезо и микро.

Его заключительная часть исследований в этой области была опубликована в 2014 году при содействии Марка Нельсона. Модели Маркова представляют собой разумный подход к этому, поскольку они предназначены для прогнозирования последующих действий, предпринимаемых в процессе принятия решений, исходя из вероятности последующих результатов.

Используя коллекцию наиболее часто встречающихся вертикальных срезов, используемых в уровнях Марио, система может затем проанализировать набор из одного или нескольких уровней, построить модель Маркова и затем попытаться создать уровни, которые будут иметь схожие n-граммы в нём. Как можно увидеть здесь, итоговые уровни не только отражают конкретные конструкции из существующих уровней Mario, но и объединяют их способами, которые ранее не рассматривались.

Другое исследование принадлежит Адаму Саммервиллю, который защитил докторскую диссертацию в Калифорнийском университете в Санта-Крус в 2018 году и в настоящее время работает на должности доцента в Калифорнийском государственном политехническом университете. Будучи аспирантом, Адам работал над различными забавными исследованиями, и он попробовал два подхода для генерации уровня Mario с помощью машинного обучения.

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

Следовательно, в статье Саммервилля используется аналогичный подход цепи Маркова (MC), но решения, принятые таким способом, проверяются с помощью поиска по методу Монте-Карло (MCTS), который следит за тем, что принимаемые решения будут не только воспроизводимыми, но и адаптирует их к конкретным параметрам проекта.

Для начала, цепь Маркова создаётся аналогично работе Дальскога, исследуя вертикальные слои каждого уровня и идентифицируя твёрдые и разрушаемые блоки, врагов, трубы, монеты, блоки вопросов и скрытые бонусы. Как только цепь Маркова установлена, каждый шаг процесса генерации уровня основывается на алгоритме MCTS для проверки качества каждого возможного действия, которое он может выполнить.

Если цепь Маркова говорит, что есть три часто используемых продолжения текущего вертикального среза, MCTS оценивает их несколькими способами, и система выбирает тот, который считается наиболее подходящим. Оценки MCTS многогранны, учитывая, что они предназначены не только для того, чтобы гарантировать, что итоговые уровни могут быть воспроизведены, но также основаны на дополнительных метриках, которые пользователь может параметризировать на основе своих личных интересов.

Сначала каждый уровень оценивается на полноту, используя бота A* Баумгартена, и применяя его для проверки уровня. В дополнение к тестированию бота, есть независимые желательные параметры: количество пропастей, врагов, монет и бонусов. Эта ручная подстройка позволяет дизайнеру лучше контролировать типы уровней, при этом полагаясь на MCTS, чтобы гарантировать пригодность локаций.

Второй подход Саммервилля состоял в том, чтобы использовать вариант рекуррентных искусственных нейронных сетей, известный как долгосрочная или LSTM-сеть.

Сети LSTM датируются концом 1990-х годов и отлично подходят для обработки последовательностей данных, поскольку они имеют компонент памяти для входных данных, что позволяет им не только читать свежую информацию, но и определять, когда следует запомнить или забыть данные из предыдущих циклов ввода. В результате сети LSTM часто используются в процессах распознавания речи и видео, учитывая непрерывные последовательности данных.

Второй подход состоял в том, чтобы обучить LSTM на 15 уровнях из оригинального Super Mario Bros., а также 24 уровнях из оригинальной японской версии Super Mario Bros. 2 (на западе Super Mario Bros: The Lost Levels).

Были проведены эксперименты с различными конфигурациями сетей, чтобы позволить системе считывать и генерировать соответствующий вывод с наилучшей конфигурацией. Суть подхода заключается в том, что генератор встраивает в уровень персонажей, которые отражают потенциальный путь, по которому может пройти игрок.

После обучения сеть может генерировать уровни, которые оцениваются по различным показателям. Эти показатели, как утверждает сам Саммервилль, не предназначены для оценки правдоподобия уровня, относительно оригинальной игры Mario, но вместо этого позволяют создавать новые уровни, которые имеют сходные свойства, но тем не менее являются новыми.

Оценка учитывает не только то, является ли уровень выполнимым — снова с помощью бота, управляемого A* — но и процент пустого пространства; а также отрицательного пространства — пустое пространство, которое игрок может фактически достичь; количество интересных тайлов; количество прыжков для оптимального прохождения уровня; и измерение линейности и простоты уровня.

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

Каждый исследователь вводит информацию уровня Марио по-разному. Дальског описывал уровни шаблонами проектирования, в то время как Саммервилль передавал данные тайлов с уровней. Но первоначальная работа Гуздиала была нацелена не только на сбор информации об уровне, но и на понимание того, как игроки перемещаются по этим уровням в режиме реального времени. Так что он получает информацию об уровнях, наблюдая, как люди проходят их на YouTube.

В проекте используется OpenCV — набор инструментов для компьютерного зрения с открытым исходным кодом, который обрабатывает каждый кадр прохождения. Проект фокусируется на двух целях: сначала определить, что можно узнать о разметке уровней по информации с отснятого материала; а также найти способ представить знания о дизайне, скрытые в отснятом материале игрового процесса, чтобы их можно было воспроизвести для целей генерации уровня.

Чтобы узнать, что генератор может делать с разметкой уровней, он запускает процесс определения и классифицирования того, что Гуздиал называет «областями с высоким уровнем взаимодействия» — сегментом уровня, на котором игрок тратит больше времени по сравнению с другими. Это может относиться к областям с jumping puzzle, летающими монетами или блоками с вопросами и скрытыми бонусами.

Эти области высокого взаимодействия идентифицируются в видеоролике, а затем анализируются, чтобы понять, в какой последовательности размещаются спрайты. Этого легче всего достичь в оригинальной Super Mario Bros., учитывая, что система должна учитывать только 102 спрайта. Видео разбито на отдельные разделы путём оценки различий в содержании каждого кадра.

Получающиеся области взаимодействия затем группируются так, чтобы их можно было эффективно классифицировать, в результате чего получается 21 кластер, в котором видеосегменты размером от 2 до 250 кадров несут особые интересные свойства, такие как нахождение под землей или на верхушках деревьев. Чтобы анализ не прерывался, используются только видеозаписи, где игроки не умирают.

Второй этап заключается в построении вероятностной модели, основанной на кластерах, извлечённых из видеоданных. Эта модель кодирует правила проектирования, посредством которых «узлы уровня» (обозначен буквой D на диаграмме выше) могут быть сгенерированы различными способами с помощью данных, полученных из кластеров на основе определённого стиля. Это требует правильной калибровки узлов G и D.

Узел G-модели представляет всю геометрическую информацию о заданной форме, которая состоит из одного или нескольких спрайтов. Есть D-узел модели, в котором хранится реляционная информация G-узла ко всем другим G-узлам в данном разделе уровня. По сути, это кодирование информации о том, как объекты размещаются относительно друг друга.

Таким образом, система эффективно взяла всю эту видеоинформацию, проанализировала интересные формы, которые используют определённые спрайты, а затем узнала, как эти формы связаны друг с другом. Интересной частью этого является то, что она не изучает, как сделать уровень Mario, и при этом система не понимает, что такое Mario. Вместо этого она изучает, как спрайты располагаются относительно друг друга в сегментах видеоряда.

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

Последнее, но не менее важное, это недавнее исследование доктора Ванессы Волц, аспиранта Технического университета Дортмунда и в настоящее время научного сотрудника в Университете королевы Марии в Лондоне.

Волц занималась исследованием создания уровней, используя процесс, известный как генеративные состязательные сети (generative adversarial networks — GAN). GAN — это процесс обучения без дополнительного контроля, который основывается на существующих исследованиях состязательного обучения между нейронными сетями, которое началось в начале 1990-х годов.

Генеративная состязательная сеть — это метод глубокого обучения, состоящий из двух отдельных сверточных нейронных сетей, известных как генератор и дискриминатор. Генератор создаёт решения для данной проблемы, а дискриминатор оценивает их качество.

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

Этот подход привёл к значительным улучшениям в изменении фотографий. Возможно, самое большое влияние, которое он оказал на игры — это недавняя работа в сообществах моддеров, использующих машинное обучение для увеличения разрешения текстур до 4K для таких игр, как Elder Scrolls: Morrowind, DOOM, Metroid Prime и Final Fantasy VII.

Для анализа Mario подход разбит на две отдельные фазы: первая часть — это обучение требуемой сети-генератора. Дискриминатор обучается на одном уровне Super Mario Bros., который также использовался в работе Саммервилля, в то время как генератор обучается тому, как начать учиться обманывать дискриминатор. Как только этот процесс завершён, генератор может создавать новые уровни, которые обманывают дискриминатор, и дают старт второй фазы обучения.

На втором этапе используется процесс, известный как Covariance Matrix Adaptation Evolution Strategy (или CMA-ES для краткости), чтобы дополнительно обучить генератор так, чтобы он мог строить уровни, которые отражают определённые свойства конструкции (например, количество наземных плиток и размещённых врагов). Но это также оценивается на основе того, может ли бот A* Баумгартена завершить сгенерированные уровни и добиться нужного количества прыжков для прохождения.

Это приводит к уровням, которые основаны на фрагментах, сгенерированных системой, но упорядоченных в постепенно усложняющихся сегментах. Хотя система не всегда идеальна и требует правильной калибровки, её преимущество состоит в том, что уровни могут генерироваться очень быстро, и теоретически она может генерировать новые уровни пока игрок проходит готовые!

Можно посмотреть генератор уровней в действии на видео ниже. Также этот генератор можно опробовать самостоятельно, код доступен на GitHub.

#mario #нейросети