PaperlayerView exact revision on arXiv

Source-linked AI summary

Procedural Content Generation via Machine Learning (PCGML)

Adam Summerville, Sam Snodgrass, Matthew Guzdial, Christoffer Holmgård, Amy K. Hoover, Aaron Isaksen, Andy Nealen, Julian Togelius

arXiv:1702.00539v3cs.AI

TL;DR

PCGML addresses how machine learning can generate functional game content from existing content, while the field lacks common game data structures and often operates with small datasets. This survey synthesizes representations, methods, applications, and open challenges, including playability, designer control, and evaluation.

  • Problem

    PCGML lacks common data structures for representing games and is constrained by limited training data, complicating learning from existing game content.

  • Method

    The paper surveys and contrasts PCGML approaches, data representations, applications, and challenges across functional game-content domains.

  • Results

    The survey identifies platformer levels as the most common generation target and describes diverse representations and methods, while noting that performance comparisons lack an agreed goodness test.

  • Takeaways & Limitations

    PCGML supports generation, co-creativity, repair, critique, and content analysis, but future work must address playable-only generation and designer control.

  • Takeaways & Limitations

    Comparing approaches is difficult because there is no agreed test for generator goodness and training or generation times are generally unreported.

Abstract

from arXiv · show

This survey explores Procedural Content Generation via Machine Learning (PCGML), defined as the generation of game content using machine learning models trained on existing content. As the importance of PCG for game development increases, researchers explore new avenues for generating high-quality content with or without human involvement; this paper addresses the relatively new paradigm of using machine learning (in contrast with search-based, solver-based, and constructive methods). We focus on what is most often considered functional game content such as platformer levels, game maps, interactive fiction stories, and cards in collectible card games, as opposed to cosmetic content such as sprites and sound effects. In addition to using PCG for autonomous generation, co-creativity, mixed-initiative design, and compression, PCGML is suited for repair, critique, and content analysis because of its focus on modeling existing content. We discuss various data sources and representations that affect the resulting generated content. Multiple PCGML methods are covered, including neural networks, long short-term memory (LSTM) networks, autoencoders, and deep convolutional networks; Markov models, $n$-grams, and multi-dimensional Markov chains; clustering; and matrix factorization. Finally, we discuss open problems in the application of PCGML, including learning from small datasets, lack of training data, multi-layered learning, style-transfer, parameter tuning, and PCG as a game mechanic.

I. INTRODUCTION

PCGML generates functional game content directly from models trained on existing content, extending procedural generation beyond hand-crafted constructive, search-based, and solver-based methods. The survey distinguishes PCGML from approaches that use machine learning only for evaluation and focuses on content that affects game mechanics.

  • Unlike constructive, search-based, and solver-based PCG, PCGML learns from existing content rather than relying primarily on hand-crafted algorithms, parameters, constraints, and objectives.
  • PCGML generates game content directly from models trained on existing game content.Inputs may be random samples, partial content, or previous content; the model output itself is interpreted as game content.
  • PCGML models can support partial or complete, autonomous, interactive, or guided generation across levels, maps, items, weapons, quests, characters, and rules.
  • The survey focuses on functional content whose alteration could change the in-game effects of player actions, excluding textures and sound as primarily cosmetic content.
  • Game content generation must satisfy strict structural constraints because playability is evaluated through interaction rather than static inspection.

II. USE CASES FOR PCGML

PCGML supports autonomous generation and designer–algorithm collaboration by learning from examples in the target content domain. Because it models existing content, it also supports completion, repair, critique, and analysis.

  • PCGML extends beyond generation to recognition, analysis, and critique because its models are trained on existing game content.
  • PCGML supports autonomous generation of complete game artifacts without human input during generation, including online content generation for roguelike games.
  • Designers can provide representative target-domain examples instead of separately specifying generation algorithms and evaluation functions.
  • AI-assisted design lets human designers and algorithms work together to create content, with examples serving as the designer’s interaction language.
  • PCGML can autocomplete partially specified game content by training models to complete missing portions.
  • Learned models can identify unplayable content and suggest repairs using patterns learned from representative examples.

D. Recognition, Critique, and Analysis

The survey organizes PCGML across data representations and training methods, emphasizing that learned content models can also support recognition, critique, analysis, and compression. Its taxonomy exposes commonalities and gaps across game-content applications.

  • PCGML models trained on existing content can analyze content created by algorithms, players, or designers.
  • Unsupervised encoding approaches can compress content into representations used to classify level types or compare content across games.
  • Learned representations may support automatic evaluation and identify uniqueness or similarity through pattern frequency and relatedness to existing content.
  • The survey’s taxonomy crosses three data representations—sequences, grids, and graphs—with five training categories: back propagation, evolution, frequency counting, expectation maximization, and matrix factorization.
  • The same representation can use different training techniques, while one training category can apply to different model classes.

A. Sequences

Sequence-based PCGML represents content as ordered data and applies frequency-based or learned sequential models to generate new material. In platformer levels, this representation relies on a natural traversal order or a conversion into one-dimensional slices.

  • Sequences represent content experienced over time, including textual content and game levels with a natural left-to-right traversal.
  • Frequency Counting: Frequency-counting methods estimate probabilities for atomic generative pieces, often conditionally on the current state.
  • Frequency Counting: An n-gram model determines each state’s probability from the n preceding states.
  • Frequency Counting: Mario levels were converted into strings by dividing them into vertical slices, exploiting recurring configurations in the level design.
  • Frequency Counting: Mario n-gram models generated new levels, while later work used Monte Carlo Tree Search to score roll-outs with designer-specified objectives.
  • Evolution: Evolutionary sequence approaches can train generators by evolving neural-network-based tile predictions from human-authored levels.
  • Evolution: Search-based evolutionary methods are not PCGML when generation occurs through an author-defined search space, even if machine learning supplies fitness functions.

3) Back Propagation

Back-propagation and recurrent neural methods learn level or card representations from existing content, supporting generation, player-conditioned levels, and partial card completion.

  • Level generation: LSTM RNNs generated Super Mario Bros. levels from tile sequences while incorporating simulated player paths and level-depth information.The representation encouraged exemplar paths and modeled both progression and level termination.
  • Level generation: Actual player paths from four YouTube playthroughs biased generated levels toward the collecting and movement preferences of specific players.For example, paths collecting coins and question-mark blocks produced levels with more of those elements.
  • Card generation: Neural networks trained on card sequences generated Magic: The Gathering cards, but sequential representations could not condition earlier fields on later fields.A field such as Cost near the sequence’s end could not condition generation unless preceding fields were specified.
  • Card generation: Mystical Tutor used sequence-to-sequence LSTMs with MISSING tokens to reconstruct corrupted Magic: The Gathering cards from any specified card field.This architecture addressed the conditioning limitation of sequence-only generation and supported co-creative design assistance.

B. Grids

Grid-based PCGML represents levels and maps as spatial tile structures, using neighborhood models, autoencoders, and convolutional networks for generation, repair, and resource placement.

  • Grid representations: Two-dimensional grids are natural representations for many game levels, although aligning non-tile entities to grids can lose information.This representation is used for platformers, dungeons, and real-time strategy maps.
  • Markov models: Multi-dimensional Markov Chains sample tiles using learned probabilities conditioned on neighboring states in multiple directions.The model builds a frequency-based probability table and selects each new tile probabilistically from preceding tile configurations.
  • Markov models: Hierarchical and constrained MdMC extensions capture higher-level structure and ensure usability, while an MRF performed better than standard MdMC in Kid Icarus.The comparison is especially relevant where platform placement is pivotal to playability.
  • Markov models: Gumin’s wave-function-collapse approach uses representative N × N windows to choose tiles and propagate the constraints imposed by each choice.The method extends an MRF-like process from bitmap generation to 3-D tile sets and level generation.
  • Map decoration: Convolutional neural networks predicted StarCraft II resource locations from downsampled heightmaps, with postprocessing allowing designers to vary resource density.The approach performed well in some cases but struggled in others, likely because of overfitting to a small training dataset.
  • Repair: Autoencoders repair illegal Super Mario Bros. level windows by replacing unplayable segments with playable alternatives, including solutions different from the original.The models were trained on vertical windows and compressed typical Mario-level features.

3) Matrix Factorization

Matrix factorization compresses existing level data into latent patterns and weights, which can then be recombined to generate new levels. The survey also notes representation-specific trade-offs, including fixed dimensions and graph-structure costs.

  • 3) Matrix Factorization: Matrix factorization infers latent level features by compressing existing data into smaller matrices of patterns and coefficients.The part matrices represent level patterns, while coefficient matrices provide their weights.
  • 3) Matrix Factorization: Novel coefficient vectors can be multiplied by learned part matrices to generate levels beyond the original generators’ expressive range.
  • 3) Matrix Factorization: The Zelda approach hierarchically generates dungeon topology and represents rooms as tile grids using Principal Component Analysis.The supplied passage introduces PCA as a compressed representation of the original two-dimensional room arrays.
  • 3) Matrix Factorization: Graph representations are general but lack structural properties that grids encode implicitly, such as the relations above and below.

1) Expectation Maximization

Expectation Maximization is presented as an iterative parameter-learning procedure used with clustering and probabilistic models. The surveyed examples apply these ideas to gameplay-derived platformer chunks, interactive fiction, and dungeon structures.

  • 1) Expectation Maximization: Expectation Maximization alternates between computing model likelihoods in an Expectation step and updating parameters to maximize that likelihood in a Maximization step.
  • 1) Expectation Maximization: K-means clustering with automatic K estimation learned Super Mario Bros. level-generation models from gameplay videos.
  • 1) Expectation Maximization: Guzdial and Riedl used nine gameplay videos, totaling roughly four hours, as training data for their Super Mario Bros. approach.
  • 1) Expectation Maximization: Their hierarchical model clusters level chunks and embedded shapes into styles, then combines those styles probabilistically to generate novel chunk sequences.Generated levels use sequences derived from the gameplay videos.
  • 1) Expectation Maximization: Dungeon generation models room connectivity and high-level parameters such as dungeon size and optimal player-path length with a Bayes Net.
  • 1) Expectation Maximization: Scheherazade-IF derives interactive fiction games from crowdsourced exemplar stories by learning plot graphs whose vertices represent events and whose edges encode sequentiality.Players can assume character roles and choose among learned event sequences.

D. Discussion of Approaches

The surveyed PCGML approaches vary across representations, training methods, computational costs, and application domains. The discussion identifies incomplete coverage of method–representation combinations, limited data, and several promising unexplored directions.

  • D. Discussion of Approaches: Platformer level generation is the most common target and spans all surveyed training methods and data representations.Sequence and grid approaches encode level shape, while graph approaches preserve relative entity positions without explicit shape or size.
  • D. Discussion of Approaches: There is no agreed-upon test for generator goodness, making performance comparisons difficult across approaches.The survey also notes that training and generation times are often unreported.
  • D. Discussion of Approaches: LSTM methods generally require more training and generation computation than multi-dimensional Markov chains, while matrix factorization may have the highest memory usage.
  • E. Unexplored Approaches: Only slightly over half of the possible method–representation combinations had been explored, leaving extensions such as HMMs and CRFs as open directions.
  • E. Unexplored Approaches: Matrix factorization remains underused for sequences and graphs, despite possible applications to categorical embeddings and adjacency-matrix representations.
  • E. Unexplored Approaches: Graph convolutional networks had been used for classification but not yet for game-content generation in the surveyed work.
  • E. Unexplored Approaches: PCGML faces domain-specific challenges including typically small game datasets and underexplored applications such as style transfer, parameter tuning, and PCGML game mechanics.

A. Ensuring Solvability and Playability

PCGML faces persistent challenges in generating playable game artifacts because training data is scarce, heterogeneous, and difficult to represent consistently. Existing approaches bias or constrain generation toward playability, but do not yet guarantee it.

  • Ensuring Solvability and Playability: Current approaches constrain or bias generated content using post-generation checks, stepwise sampling constraints, or player-path information.Player paths encourage playable levels but do not ensure playability.
  • Data Sources and Representations: Game datasets are difficult to aggregate because different games rarely share data structures or semantic meanings.Even visually similar sprite encodings can represent different concepts across games.
  • Data Sources and Representations: The Video Game Level Corpus provides 428 levels from 12 games in three formats, but remains small and lossy for machine learning.It is an initial shared resource for PCGML research, though its scale and representations limit its coverage.
  • Learning from Small Datasets: Games are likely to remain data-constrained, with platformer and individual-series corpora much smaller than standard language and image datasets.The NES library is approximately 237 MB, while platformers and individual series occupy progressively smaller portions of it.
  • Learning from Small Datasets: One-shot learning is relevant to PCGML because it targets generalization from a single example or a very small dataset.Games are presented as a natural testbed because of their limited training data.

D. Learning on Different Levels of Abstraction

PCGML for games must model multi-modal dynamic systems in which content and rules interact, while the field still lacks shared datasets and standardized evaluation. Transfer methods have begun blending level styles, but broader transfer across mechanics and content types remains open.

  • Learning on Different Levels of Abstraction: Generated game content participates in interactions among rules, levels, and the consequences of player actions, unlike isolated modalities such as images or sound.The paper uses the Mechanics, Dynamics, Aesthetics framework as a high-level model for these systems.
  • Datasets and Benchmarks: PCGML lacks many publicly available datasets and widely used standardized evaluation benchmarks.This limits common resources for comparing methods across the field.
  • Datasets and Benchmarks: Large public datasets could reduce entry barriers and support faster community growth, but existing resources primarily provide level data.Other datasets for object models and gameplay mechanics exist but have not been widely used by the PCGML community.
  • Datasets and Benchmarks: Existing competitions and metric-based benchmarks provide comparison mechanisms, but their coverage is limited across techniques, training data, or game types.The Super Mario Bros. benchmark focuses on platforming level generators, while competitions may rely on hard-coded rules or omit training data.
  • Style Transfer: Style and concept transfer combines information from one domain with knowledge from another, and has only recently been applied to PCGML.Early game applications transfer or blend level styles without explicitly transferring or blending different mechanics.
  • Style Transfer: Future PCG transfer research should address game mechanics and content beyond levels, including character models, stories, and quests.The survey identifies these as broader targets than purely aesthetic level transfer.

G. Exposing and Exploring the Generative Space

PCGML systems are largely trained to replicate designed content, but the survey highlights opportunities to expose their learned generative spaces to designer control and player interaction. Latent-space manipulation and game-as-mechanic designs are proposed directions for exploring those spaces.

  • Exposing and Exploring the Generative Space: Designer control over difficulty, complexity, or theming remains underexplored because interaction is mainly limited to selecting training data.The survey identifies controllable generation as an important avenue for opening PCGML systems to designers.
  • Exposing and Exploring the Generative Space: Latent-space interpolation and extrapolation could let users tune semantic factors in generated game content.The paper relates this possibility to latent directions associated with meaningful visual properties in generative models.
  • Exposing and Exploring the Generative Space: Most PCGML work focuses on reproducing designed content to create infinite or novel gameplay variations.This framing emphasizes variation informed by prior examples rather than direct exploration of the model’s internal space.
  • Exposing and Exploring the Generative Space: PCGML could itself become a game mechanic, with players generating, comparing, identifying, or training content according to desired qualities.Suggested designs position the system as an adversary or toy rather than only as a behind-the-scenes generator.
  • Conclusion: The survey contrasts existing PCGML work and identifies challenges and opportunities for future research in an emerging field.It notes that most work has focused on two-dimensional Super Mario Bros. levels, leaving other domains underexplored.
Loading 1702.00539v3…