Illuminating Mario Scenes in the Latent Space of a Generative Adversarial Network

Matthew C. Fontaine, Ruilin Liu, Ahmed Khalifa, Jignesh Modi, Julian Togelius, Amy K. Hoover, Stefanos Nikolaidis

TL;DR

This paper tackles the challenge of controlling Generative Adversarial Networks (GANs) for game level design. Instead of opaque latent vectors, they use Quality Diversity (QD) algorithms to explore the GAN's latent space, allowing designers to specify desired gameplay features like enemy count or platform height. This enables the generation of diverse, high-quality Mario levels that are both playable and stylistically similar to human-created ones.

What Problem Does This Paper Address?

Procedural content generation (PCG) in games often aims to create content that is not only aesthetically pleasing but also adheres to specific gameplay mechanics and constraints. Generative Adversarial Networks (GANs) have shown great promise in generating realistic-looking game levels that mimic human-authored styles. However, directly controlling the output of a GAN to achieve specific gameplay attributes is difficult. The "latent space" of a GAN, which represents the underlying parameters that generate content, is often opaque and not intuitive for designers to manipulate. Designers might have a general idea of what they want (e.g., a harder level with more obstacles) but struggle to translate this into specific latent vector adjustments. This paper addresses the problem of "latent space illumination" (LSI): how to efficiently explore this latent space to extract a diverse collection of high-quality game levels that satisfy a range of user-specified gameplay measures.

Methods

The core of this paper lies in applying Quality Diversity (QD) algorithms to navigate the latent space of a GAN. QD algorithms are designed to discover a wide range of high-quality solutions that vary across specified attributes, rather than just optimizing for a single objective.

The authors specifically leverage:

  • MAP-Elites: A foundational QD algorithm that partitions the "behavior space" (defined by desired attributes) into a grid and maintains the best solution (elite) for each grid cell.
  • MAP-Elites (line): An extension that uses a "directional variation operator" to exploit correlations between elites, potentially improving exploration efficiency.
  • CMA-ME (Covariance Matrix Adaptation MAP-Elites): A hybrid algorithm that integrates CMA-ES (a powerful derivative-free optimization strategy) into MAP-Elites. CMA-ME uses "improvement emitters" that dynamically adapt their search goals based on the archive's progress, making it particularly effective for exploring continuous spaces.

These QD algorithms are used to search the latent space of a pre-trained Deep Convolutional GAN (DCGAN) that generates Super Mario Bros. levels. The goal is to find latent vectors that produce levels exhibiting specific combinations of gameplay measures.

Datasets

  • Training Data: 15 original Super Mario Bros. levels from the Mario AI Framework were used to train the DCGAN.
  • Evaluation: The generated levels were evaluated using the Mario AI Framework, specifically by an A* agent that won the 2009 Mario competition. The "fitness" of a scene was defined as the percentage of completion by this agent.

Key Insights and Ideas

  • QD Algorithms as Latent Space Navigators: The paper demonstrates that QD algorithms are a powerful tool for "illuminating" the latent space of GANs, making it explorable for designers. This moves beyond simply generating "realistic" levels to generating levels with controllable, diverse gameplay characteristics.
  • Beyond Single Objectives: Traditional optimization methods (like CMA-ES) focus on a single objective (e.g., playability). QD algorithms, by design, explore multiple dimensions simultaneously, which is crucial for generating diverse content.
  • CMA-ME's Superiority: The CMA-ME algorithm consistently outperformed other tested QD algorithms and random search, highlighting its effectiveness in efficiently covering the behavior space and finding high-quality solutions.
  • Representation vs. Agent-Based Metrics: The study explores both "representation-based" behavioral characteristics (e.g., number of sky tiles) and "agent-based" characteristics (e.g., performing a jump). While representation-based metrics are easier to control, agent-based metrics are more directly tied to actual gameplay.
  • User Perception Aligns with Metrics: A user study confirmed that the generated levels' perceived difficulty and similarity to ground truth were influenced by the chosen behavioral characteristics, validating the effectiveness of the QD approach in generating perceptually diverse content.

Key Results

  • QD Algorithms Outperform: MAP-Elites, ME (line), and CMA-ME significantly outperformed CMA-ES and random search in terms of coverage and QD-score for representation-based and KL-divergence behavioral characteristics.
  • CMA-ME Leads: CMA-ME achieved the highest QD-scores and coverage in representation-based and KL-divergence metrics, indicating it found a more diverse and high-quality set of levels.
  • Agent-Based BCs Challenging: All algorithms performed similarly and poorly on agent-based binary behavioral characteristics, likely due to the A* agent's tendency to rush through levels without engaging with many mechanics.
  • User Study Validation:
    • Perceived difficulty of generated levels significantly increased with the number of sky tiles and enemies (supporting H1).
  • Perceived similarity to ground truth scenes decreased with higher KL-divergence values (supporting H2).

Limitations and Future Work

  • Agent-Based BCs Limitation: The authors acknowledge the difficulty in generating levels that trigger specific agent-based behaviors due to the A* agent's playstyle. Future work could involve training agents that are more exploratory or using different evaluation metrics.
  • ME (line) Performance: The ME (line) algorithm did not show significant improvement over MAP-Elites, possibly because the assumption of similar search space parameters between elites was not strongly met in this domain.
  • Future Directions:
    • Extending the approach to other generative models like Variational Autoencoders (VAEs) and other GAN architectures.
  • Combining QD with "intelligent trial and error" algorithms for personalized level generation.
  • Exploring more complex combinations of behavioral characteristics.

Summary updated

Abstract

Generative adversarial networks (GANs) are quickly becoming a ubiquitous approach to procedurally generating video game levels. While GAN generated levels are stylistically similar to human-authored examples, human designers often want to explore the generative design space of GANs to extract interesting levels. However, human designers find latent vectors opaque and would rather explore along dimensions the designer specifies, such as number of enemies or obstacles. We propose using state-of-the-art quality diversity algorithms designed to optimize continuous spaces, i.e. MAP-Elites with a directional variation operator and Covariance Matrix Adaptation MAP-Elites, to efficiently explore the latent space of a GAN to extract levels that vary across a set of specified gameplay measures. In the benchmark domain of Super Mario Bros, we demonstrate how designers may specify gameplay measures to our system and extract high-quality (playable) levels with a diverse range of level mechanics, while still maintaining stylistic similarity to human authored examples. An online user study shows how the different mechanics of the automatically generated levels affect subjective ratings of their perceived difficulty and appearance.
BibTeX
@inproceedings{fontaine2021illuminating,
  author = {Matthew C. Fontaine and Ruilin Liu and Ahmed Khalifa and Jignesh Modi and Julian Togelius and Amy K. Hoover and Stefanos Nikolaidis},
  title = {{Illuminating Mario Scenes in the Latent Space of a Generative Adversarial Network}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i7.16740},
}
Figure