Source-linked AI summary
Super Mario as a String: Platformer Level Generation Via LSTMs
Adam Summerville, Michael Mateas
TL;DR
Machine-learning level generation needed approaches that could learn platformer structure without relying on manually specified generation rules. This paper trains LSTMs on Super Mario Brothers levels using alternative tile and path representations, then evaluates generated levels against human-authored levels. The authors report that path information substantially improves playability and makes generated-level metrics closer to human-authored levels, while noting limits of the left-to-right sequencing approach.
Problem
Prior platformer level generators often relied on specified rules or Markov-chain sequences, while machine-learning methods needed better representations for generating playable levels.
Method
The paper trains LSTMs on Super Mario Brothers levels using eight induced tile orderings, alternative data representations, and player path information.
Results
Path information produced the strongest reported outcome: generated levels reached 97% playability, exceeding the best reported machine-learning result of 66% and human-authored system result of 94%.
Takeaways & Limitations
Including player paths improves generated-level playability and brings level metrics closer to those of human-authored levels.
Takeaways & Limitations
The left-to-right sequencing approach is less suited to games with highly non-linear progression, backtracking, and dead ends.
Abstract
from arXiv · showhide
The procedural generation of video game levels has existed for at least 30 years, but only recently have machine learning approaches been used to generate levels without specifying the rules for generation. A number of these have looked at platformer levels as a sequence of characters and performed generation using Markov chains. In this paper we examine the use of Long Short-Term Memory recurrent neural networks (LSTMs) for the purpose of generating levels trained from a corpus of Super Mario Brothers levels. We analyze a number of different data representations and how the generated levels fit into the space of human authored Super Mario Brothers levels.
INTRODUCTION
The paper applies LSTMs to generate Super Mario Brothers levels from learned level representations, extending machine-learning approaches beyond hand-specified generation rules. It evaluates eight data representations and compares generated levels using multiple statistics.
- LSTMs are used to learn and generate Super Mario Brothers platformer levels.
- The approach examines eight different data representations for levels.
- Generated levels are compared using multiple evaluation statistics.
RELATED WORK
Prior machine-learning approaches generated platformer levels with Markov chains, clustering, graph grammars, or limited neural prediction, but faced trade-offs in structure, generalization, and playability. These approaches varied in modeling range and authorial control, while often requiring mechanisms to address unplayable outputs.
- Markov-chain methods represented levels as tile-to-tile transitions or vertical slices, with each choice imposing different structural trade-offs.Vertical slices can fail on unseen columns, while tile-level transitions can violate implicit semantic constraints.
- Earlier generators provided no general playability guarantee, and one reported system produced levels that simulated agents could not complete.Monte Carlo Tree Search improved playability guidance but required a designer-specified reward function.
- Clustering and graph-based methods modeled longer-range structure than Markov chains by learning relative tile placements or graph grammars.One clustering approach considered tile distances up to 18 tiles, compared with three tiles of history in earlier work.
- The other known neural-network approach predicted block heights from short temporal contexts or other block types to fill portions of levels.
- Neural procedural generation had also been explored for images, text, and calligraphic or address-sign sequences using neural and attentional systems.
LSTM SEQUENCE GENERATION
The paper treats individual Super Mario tiles as sequence characters and uses LSTMs to predict subsequent tiles, addressing the difficulty of imposing a useful order on two-dimensional levels. It evaluates alternative orderings, tile encodings, and path information within a multilayer architecture.
- LSTM Sequence Generation: LSTMs address the vanishing-gradient problem by adding memory mechanisms that control when information is remembered or forgotten.Standard RNNs can maintain local coherence while losing global coherence across long sequences.
- LSTM Sequence Generation: The network uses three internal layers of 512 LSTM blocks, one-hot tile inputs, and a final SoftMax categorical distribution.The architecture is fully connected between successive layers.
- Data Specification: Each individual level tile is represented as a character in a linear sequence rather than using only vertical slices.This representation avoids restricting generation to complete slices observed during training.
- Data Specification: The representation distinguishes tile types such as solids, enemies, destructible blocks, coins, power-ups, empty space, and pipe parts.Question-mark blocks are separated by contents, and pipe halves preserve their sequence order.
- Data Specification: Eight induced tile orderings address how to linearize two-dimensional levels across bottom-to-top, snaking, path, and column-depth choices.Naive row ordering would require remembering tile placements across levels 200–500 tiles wide.
- Data Specification: Player path information is included as part of the level specification to target the playability problem in generated levels.The representation models both level geometry and a possible player path.
RESULTS
The LSTM generators learned coherent level sequences and produced new levels whose measured properties generally matched human-authored Super Mario levels. Path information was especially important for both prediction performance and playability, while metric-based evaluation still required informal inspection.
- The Snaking-Path-Depth representation achieved the lowest error among the evaluated data formats.
- Eight LSTM networks were trained on 39 Super Mario levels using a 70%-30% training-evaluation split and negative log-likelihood.Networks were selected by held-out evaluation performance and training stopped after the evaluation score plateaued for more than two epochs.
- Path information roughly doubled evaluation performance and, combined with other representation choices, produced performance over twice that of the next-best network and 20× the naïve specification.The most complex specification also had a vocabulary 36% larger than the naïve specification.
- The generators generally matched existing levels across evaluated metrics, although generated optimal paths were consistently longer than those in the original levels.Metrics included empty space, leniency, linearity, decoration, jumps, induced jumps, and path-related properties.
- Path-informed generators produced 97% completable levels, exceeding the reported 66% machine-learning result and 94% human-authored Mario AI result.The Snaking-Path-Depth generator also generally matched the expressive range of the original levels.
- Metric-based evaluation had to be supplemented with informal inspection because no trained system yet judged how good or fun a generated level was.The authors used randomly selected examples to inspect learned patterns and apparent quality.
- The LSTMs generated coherent column-to-column placements and learned to produce exactly 16 tiles per column without an explicit reset rule.They also avoided incorrectly generating column-delimiting characters.
CONCLUSION AND FUTURE WORK
The paper finds that adding player-path information improves generated Super Mario levels, especially playability and similarity to human-authored metrics. It also identifies future extensions for automated level analysis and for games with nonlinear progression, while noting that current sequencing conflates time with space.
- CONCLUSION AND FUTURE WORK: Player-path information dramatically improves generated-level playability and brings level metrics closer to human-authored levels.The authors treat player paths as part of the level specification and report improvements in both playability and metric similarity.
- CONCLUSION AND FUTURE WORK: The path-based system could support automated level analysis by assigning likelihoods to player destinations from observed behavior.Future versions may analyze levels without explicitly simulating a player and may use human gameplay videos rather than simple A* agents.
- CONCLUSION AND FUTURE WORK: Attention-based sequencing is proposed for games with nonlinear progression, including backtracking and dead ends, where left-to-right ordering is unsuitable.The authors suggest that an attentional system could learn to navigate such nonlinear maps.
- CONCLUSION AND FUTURE WORK: Treating time as a linear mapping to x-coordinate remains a concern because standard platformer generators conflate temporal and spatial structure.A tensor autoregression over width, height, and tile type is suggested to deconvolve time and space.