Генерируем уровни для игры с помощью нейросетей

Предисловие

За последние несколько лет прогресс в области искусственного интеллекта привёл к созданию методов машинного обучения на основе обучения представлениям (representation-learning) с несколькими слоями абстракции — так называемому «глубокому обучению». Общественное и медийное внимание было привлечено к этой области исследований благодаря древнекитайской настольной игре го. Несмотря на то, что сложность го часто сравнивают со сложностью самой жизни, программе AlphaGo, использующей глубокое обучение с подкреплением (deep reinforcement learning), удалось превзойти мирового чемпиона по го Ли Седоля. Удивительно, что исследования ИИ были использованы в играх и получили такое широкое общественное внимание. Стоит также заметить, что один из разработчиков AlphaGo, Демис Хассабис, был ведущим программистом Theme Park (1994 год) и ведущим программистом ИИ Black & White (2001 год). Игры и современный прогресс ИИ, возможно, имеют некую корреляцию.

Эта статья является постмортемом, отчётом о попытке нашей команды реализации генерирования уровней для Fantasy Raiders с помощью различных методов искусственных нейронных сетей. Раньше генерирование уровней было процессом кодирования знаний разработчика игры с помощью неких вероятностных техник. Однако для Fantasy Raiders мы написали программу, которая могла учиться и генерировать уровни на основании наших данных. Как нам кажется, в результате мы получили всего лишь ключ к решению задачи генерирования уровней, а не общее решение. Чтобы поделиться нашими открытиями с другими разработчиками игр мы хотим подробно рассказать о процессе наших исследований, от начала до конца.

[Рис. 1. Генерирование уровней с помощью нейронной сети]

Оценка сложности

На первом этапе наших исследований нам нужно было твёрдо убедиться, что искусственная нейросеть сможет учиться на уровнях Fantasy Raiders. Поэтому нам нужно было начать с самого простого: оценки сложности уже готовых уровней.

Fantasy Raiders — это RPG, которая стремится создавать для каждого игрока свои уровни, соответствующие его навыкам и вкусам, чтобы обеспечить ему увлекательный игровой процесс. Единицей уровня является самодостаточная комната. Нечто подобное можно увидеть в игре The Binding of Isaac (2011 год). Для удобства мы будем называть каждую комнату Fantasy Raiders «уровнем».

Игра рекомендует игроку новый уровень (комнату) с подходящей сложностью, зависящей от состояния персонажа игрока и сложности текущего уровня (комнаты). Сложность каждой комнаты вычисляется алгоритмом, оценивающим NPC и предметы на текущем уровне.

[Рис. 2. Сложности уровней, рекомендуемые в последовательности уровней]

Самым простым шагом в процессе оценки было назначение численных значений NPC или их количеству HP (Health Points). Однако гораздо сложнее было оценивать находящиеся в комнате интерактивные предметы. Именно поэтому мы решили проверить, сможет ли искусственная нейросеть заменить такой эвристический алгоритм.

Сбор данных

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

Поначалу мы рассматривали возможность создания геймплейного бота, который будет играть в каждый уровень и оценивать его сложность по получившимся результатам. Однако было практически невозможно увеличить скорость игрового процесса до значений, подходящих для машинного обучения. Поэтому мы отказались от этого плана и попросили трёх разработчиков из нашей команды оценить по пятибалльной шкале все имевшиеся у нас уровни. За день они успевали оценить по 20 уровней, и в целом оценка 1000 уровней заняла два месяца.

[Рис. 3. Пример оценки сложности уровней.]

Прогнозирование сложности

После того, как разметка данных была завершена, мы сделали снимки экрана уровней в редакторе, которые стали абстрактной версией каждого из уровней. Мы дали программе обучиться на наборе данных в виде пар «скриншот уровня в редакторе — сложность». Мы использовали снимки из редактора уровней, потому что в низком разрешении они более различимы, чем внутриигровые скриншоты, то есть эффективнее с точки зрения скорости обучения и качества входящих данных. Для этого процесса мы решили использовать CNN (Convolutional Neural Network (свёрточные нейронные сети)), потому что по сравнению с другими нейросетями они лучше подходят для классификации изображений. Для оценки качества её работы мы выбрали опорной точкой формулу, выведенную одним из наших гейм-дизайнеров.

• Прогнозирование на основании выведенной гейм-дизайнером формулы: точность 42
• Прогнозирование на основании снимка экрана редактора уровней (CNN): точность 62%

Даже при стандартной модели CNN точность повысилась на 20%. Мы несколько раз пытались использовать другие сложные модели CNN, но без каких-либо значимых результатов. На результаты негативно влиял ограниченный объём данных (примерно 1000 пар).

[Рис. 4. Прогнозирование сложности с помощью CNN]

Двигаясь по пути, вдохновлённому работами Дэвида Силвера et al. Mastering the game of Go with deep neural networks and tree search (2016 год) и Хуанхи Кима Do Neural Networks dream of procedural content generation? (2016 год) с конференции Nexon Developers Conference 2016, мы понимали, что для получения более качественных результатов нам нужно разнообразить входящие данные. Согласно работе Силвера, в 2016 году в наборы данных для AlphaGo, кроме расположения белых и чёрных камней, включалось количество ходов после начала игры, количество «убитых» камней после начала игры, а также контекстная и обработанная информация о ситё («лестницах»). Аналогично, в статье Кима для оценки сложности уровня игры обрабатывалась информация об NPC и рельефе.

Снимки редактора уровней были составлены из графических элементов, потому что должны были иметь человекочитаемую форму. Но в графических элементах представлена не вся информация о каждом NPC, объекте или предмете. Поэтому снова с помощью коллег-дизайнеров мы заново классифицировали части информации, которые могут влиять на уровень сложности. Все информационные величины, имеющие одинаковое качество, классифицированы в группу, имеющую по уникальному значению в одном каналов: R, G, B или A. Чем больше информационных величин у нас было, тем более высокой точности следовало ожидать, но при этом увеличивалась и сложность генерирования уровней. Поэтому методом проб и ошибок мы в результате пришли к четырём основным информационным величинам, которые использовались в процессе оценки сложности.

[Рис. 5. Снимок редактора уровней (вверху, RGBA) и закодированное изображение (внизу, R,G,B,A). Каждое изображение откалибровано по цвету в 128 градациях серого, чтобы повысить видимость изображения на экране.]

• Прогнозирование с помощью закодированных изображений (опорные значения — логистическая регрессия): точность 61%
• Прогнозирование с помощью закодированных сообщений (CNN): точность 71%

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

[Рис. 6. Закодированное изображение внутриигровых уровней Fantasy Raiders]

Автоматизированное генерирование уровней

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

В области генерирования изображений, голоса и текста проводятся активные исследования. Поскольку в качестве входящих данных нашей модели использовались снимки изображения, мы начали с GAN (Generative Adversarial Networks, генеративно-состязательная сетей), которые широко используются во многих случаях и демонстрируют хорошие результаты.

[Рис. 7. Классификация генеративных моделей — Иэн Гудфеллоу (Ian Goodfellow) (2016 год), Рис 9. «NIPS 2016 Tutorial: Generative Adversarial Networks»]

GAN (генеративно-состязательные сети)

С момента первой реализации GAN в 2014 году и соединения GAN с CNN в модели DCGAN в конце 2015 года были созданы различные версии GAN. Более десяти из них можно использовать для генерирования изображений. (Если вам интересно посмотреть, насколько сложные результаты может генерировать GAN, изучите the-gan-zoo.)

[Рис. 8. Персонажи аниме, сгенерированные GAN — Yanghua JIN, «Various GANs with Chainer»]

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

[Рис. 9. Процесс обучения GAN для генерирования уровней. Generator и Discriminator — это нейросети. Generator пытается обмануть Discriminator, выдавая сгенерированные программой уровни за созданные гейм-дизайнером, а Discriminator отделить созданные гейм-дизайнером уровни от сгенерированных программой. При повторении этого процесса Generator способен генерировать уровни, всё более и более похожие на созданные гейм-дизайнером.]

[Рис. 10. Генерирование уровней после завершения обучения.]

Больше всего нас беспокоил ограниченный объём собранных данных — всего около тысячи, потому что в самой простой базе данных MNIST в целом больше 60 000 записей. Первая попытка с использованием DCGAN окончилась провалом. Большинство других попыток с помощью других недавно изобретённых моделей GAN, демонстрировавших потрясающие результаты в генерировании изображений, тоже потерпели неудачу в генерировании уровней. Даже если им что-то и удавалось, то они генерировали очень ограниченные типы уровней.

[Рис. 11. Пример изображения, полученного после неудачного обучения. Выборка для обучения — 8 x 8 уровней. После 5000 повторений с размером серии 16 (слева). После 50000 повторений с размером серии 16 (справа).]

В этот момент мы уже почти сдались и считали, что причиной неудач является маленький объём данных. Однако обучение закончилось успехом при использовании DRAGAN, стабильной версии для обучения GAN.

[Рис. 12. Изображения уровней, сгенерированные с помощью DRAGAN, обученного на объёме данных в 1000 записей. На этом этапе генерировались только самые простые уровни.]

Однако из-за малого объёма данных DRAGAN всё равно не мог генерировать более сложные уровни.

Расширение объёма данных

Даже несмотря на то, что для машинного обучения 1000 уровней является довольно маленьким объёмом, на их создание нескольким гейм-дизайнерам потребовалось два года. Мы не могли сразу же увеличить объём входящих данных. Поэтому мы попытались увеличить количество данных с помощью метода, обычно используемого в других областях машинного обучения: мы увеличили объём данных, с 1000 до 6000, повернув каждый уровень на 90, 180, 270 градусов относительно исходного и заменив типы NPC, объектов и предметов.

[Рис. 13. Пример расширения объёма данных — исходная версия (слева), повёрнутая по часовой стрелке на 90 градусов (в середине), с заменой NPC (справа)]

После тысяч итераций с 6000 наборов данных модель, наконец, начала генерировать более сложные уровни.

[Рис. 14. Чем больше раз повторялось обучение, тем более сложные уровни генерировала программа. Они становились похожими на созданные гейм-дизайнерами.]

[Рис. 15. Уровень, созданный гейм-дизайнером (слева). Уровень, сгенерированный GAN (справа).]

(Полуконтролируемая) CGAN

С самого начала разработки Fantasy Raiders, мы изучали генеративную грамматику, надеясь на то, что со временем автоматизированное генерирование заменит создание уровней вручную. Поэтому когда мы убедились, что GAN генерирует более сложные уровни, мы применили для генерирования уровней по сложностям CGAN, которая генерирует данные в соответствии с условиями.

Как сказано выше, у нас была всего тысяча уровней, сложность которых вручную оценили наши коллеги-дизайнеры. Из-за малого объёма данных мы не могли создавать более сложные уровни. Чтобы решить эту проблему, мы увеличили объём данных с помощью расширения объёма данных (Data Augmentation). Однако 5000 уровней — это слишком много, чтобы дизайнеры могли оценивать их все вручную.

Поэтому мы решили использовать метод полуконтролируемого обучения: в этом случае, когда размечается только часть данных, Discriminator определяет, какие из уровней созданы гейм-дизайнерами, а какие — программой для выборки из всех уровней. Однако он не определяет сложность уровней, полученных расширением объёма данных. Подробнее об этом методе можно прочитать в Improved Techniques for Training GANs.

[Рис. 16. Уровни, сгенерированные сетью CGAN с одинаковым начальным значением seed, но различными сложностями.]

RNN (рекуррентные нейронные сети)

Генерирование уровней с помощью GAN работало вполне хорошо. Модель достаточно неплохо работала с обучением любым характеристикам формы уровней, однако не обучалась контекстной информации уровней.

[Рис. 17. Генеративная модель, использующая GAN, может обучаться любым характеристикам формы уровней, но не может обучаться контекстуальной информации уровней. Забор, построенный гейм-дизайнером (слева) и забор, сгенерированный генеративной моделью с использованием GAN (справа).]

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

В результате мы пришли к использованию RNN, которые чаще, чем другие генеративные модели, применяются для гененирования предложений. Мы выбрали LSTM, одну из нескольких версий RNN (недавно мы узнали, что существует ещё одно исследование, использующее для создания дискретных значений в генерировании предложений GAN, но с ним мы пока не экспериментировали.)

[Рис. 18. Генерирование уровней с помощью RNN]

LSTM (Long Short-Term Memory Units)

Для использования LSTM все уровни должны быть транслированы в строки. Поскольку мы уже закодировали все уровни, процесс трансляции проблем не вызвал. Нам пришлось разделить закодированное изображение и склеить его в одномерную строку.

[Рис. 19. Трансляция уровня в строку для RNN-обучения]

Для генерирования уровня в соответствии с его сложностью мы добавили транслированную в строку информацию о сложности уровня. После всех повторов LSTM начала генерировать уровни, обучаясь не только характеристикам формы, но и контекстной информации.

[Рис. 20. Уровни, сгенерированные с помощью RNN — Сгенерированные строки (вверху). Уровни, декодированные из строк (снизу)]

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

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

PixelRNN (PixelCNN)

В процессе поисков метода, способного объединить преимущества RNN с улучшенным пониманием контекстной информации о пространстве, мы обнаружили PixelRNN, решение для генерирования изображений на основе RNN. (Позже мы перешли к PixelCNN, которая имеет бОльшую скорость обучения).

В качестве входящих данные PixelRNN требуются изображения, а не предложения, однако мы уже выполнили все процессы, генерирующие закодированные изображения для обучения GAN.

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

[Рис. 21. Сгенерированные PixelRNN уровни с различным расположением и формой заборов.]

Работаем вместе: человек плюс машина

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

Сделав такое наблюдение, мы подумали, что будет неплохо создавать уровни совместно: человек плюс машина. Вдохновлённые исследованием Sketch-RNN, мы добавили режим редактора уровней, позволявший дизайнеру генерировать новый уровень с моделью машинного обучения.

[Рис. 22. Если гейм-дизайнер делает выбор, то машина рекомендует ему NPC, объект или предмет.]

[Рис. 23. Если гейм-дизайнер выбирает несколько вариантов, то машина делает остальные выборы вместо гейм-дизайнера.]

Fantasy Raiders разрабатывается на основе Unity, и редактор уровней тоже основан на Unity. Поэтому экземпляр уровня создаётся в JSON и передаётся на сервер, а сервер вносит в него изменения и отправляет обратно в Unity в формате JSON.

(Unity предоставляет разработчикам SDK Unity Machine Learning Agents, позволяющий использовать в Unity обучение с подкреплением. Однако возможности Python API ограничены. Мы надеемся, что команда Unity расширит свой Python API в SDK, чтобы мы могли использовать его не только в обучении с подкреплением, но и в других методах машинного обучения.)

Подведём итог

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

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

Пожелайте нам удачи, чтобы мы могли рассказать вам о новых находках!

[Рис. 24. Первый уровень Fantasy Raiders, сгенерированный машинным обучением.]

Дополнительное чтение

Generative Models: краткое введение в генеративные модели.

Generative Adversarial Nets in TensorFlow: краткое и простое введение в работу GAN.

The Unreasonable Effectiveness of Recurrent Neural Networks: конспективное введение в работу RNN.

RNN models for image generation: введение в генерирование изображений с помощью RNN.

Teaching Machines to Draw: классический пример применения нейронной сети в области творчества. Этот пример показывает, что мы должны рассматривать нейросеть не только как инструмент автоматизации, но и как источник вдохновения.

AlphaGo: источник вдохновения для использования нейронных сетей в играх.

Artificial Intelligence and Games: взгляд на игровой ИИ под другим углом. В частности, в Procedural Content Generation via Machine Learning (PCGML) рассматривается множество исследований генерирования контента для игр с помощью машинного обучения.

---

Статья написана программистами Maverick Games Seungback Shin и Sungkuk Park.