Source-linked AI summary
Level Generation Through Large Language Models
Graham Todd, Sam Earle, Muhammad Umair Nasir, Michael Cerny Green, Julian Togelius
TL;DR
The paper asks whether LLMs can generate functional Sokoban levels despite spatial constraints and limited level data. It tests LLM level generation and preliminary controllability, finding that models can produce diverse, novel, playable levels with sufficient data, while GPT-2 performance depends strongly on data availability.
Problem
Game levels impose spatial and functional constraints unlike typical LLM training data, and level datasets are scarce; whether LLMs can generate them remains an open question.
Source: §1 · pp. 1–2Method
The paper trains LLMs on Sokoban levels and investigates pretraining, dataset size, and preliminary prompt-based controllability.
Source: §1 · pp. 1–2Results
With sufficient data and training, LLMs produce diverse, novel, playable Sokoban levels, while GPT-2 performance strongly depends on data availability.
Source: §9 · p. 7Takeaways & Limitations
The authors conclude that generating video-game levels can be added to the range of tasks LLMs perform.
Source: §9 · p. 7Feasibility remains uncertain because LLMs may require too much level data, and pretraining may already include Sokoban levels, complicating novelty.
Source: §8 · p. 7
Abstract
from arXiv · showhide
Large Language Models (LLMs) are powerful tools, capable of leveraging their training on natural language to write stories, generate code, and answer questions. But can they generate functional video game levels? Game levels, with their complex functional constraints and spatial relationships in more than one dimension, are very different from the kinds of data an LLM typically sees during training. Datasets of game levels are also hard to come by, potentially taxing the abilities of these data-hungry models. We investigate the use of LLMs to generate levels for the game Sokoban, finding that LLMs are indeed capable of doing so, and that their performance scales dramatically with dataset size. We also perform preliminary experiments on controlling LLM level generators and discuss promising areas for future work.
1 Introduction
The introduction examines whether LLMs can generate game levels despite challenges in representing spatial structure and limited level data. It investigates Sokoban generation, including pretraining, dataset size, and controllability.
1 Introduction
- The paper investigates LLM game-level generation and whether findings about these models from natural-language processing apply to this domain.It also conducts preliminary experiments using data augmentation and prompting to control generated levels.Source: §1 · p. 1
- LLMs must serialize spatial levels into tokens, making it difficult to preserve regularity and spatial relationships under variable-length tokenization.Earlier sequential models showed this could be done, but the paper tests whether the result holds for modern attention-based models.Source: §1 · pp. 1–2
- Game-level datasets are small and hard to obtain, leaving open whether LLMs need extensive training data and whether language pretraining transfers to level constraints.Level quality and playability can depend on topology and tile proportions, unlike ordinary text syntax.Source: §1 · p. 2
- The study uses Sokoban to examine pretraining and dataset-size effects, with a preliminary investigation of level-generator controllability.The introduction also identifies controllability and generalizability as potential advantages of LLMs for level generation.Source: §1 · p. 2
2 Related Work
Related work situates the paper within procedural content generation and earlier sequential models for game levels. It highlights prior Sokoban research on novel, playable, and controllable generation as a point of comparison for modern language models.
2 Related Work
- Procedural content generation via machine learning learns content-generating functions from existing datasets; game-level methods include VAEs, GANs, evolution, and reinforcement learning.Earlier autoregressive work used n-grams and LSTMs to generate levels from sequential representations.Source: §2 · p. 2
- Prior Sokoban work compared PCG methods, including LSTMs, and found they could generate varied novel, playable levels and follow specified characteristics above chance.The present study instead examines modern LLMs and assumptions about their training and behavior.Source: §2 · p. 3
- Contemporaneous transformer-based work controllably generated Super Mario Bros levels, complementing this study in a different target domain.Source: §2 · p. 3
3 Data
The study trains on two Sokoban datasets with different origins and scales. Levels are serialized as character strings and tokenized for model input.
3 Data
- Sokoban levels are grids whose characters encode walls, empty spaces, players, boxes, goals, and combinations of boxes or players on goals.The game can be challenging because its state space branches rapidly and some states cannot be escaped.Source: §3 · p. 3
- Microban1 contributes 282 human-created levels for which an A* search agent found a solution, while Boxoban contains 438,000 procedurally generated levels.Microban levels vary in size; Boxoban levels are 10 by 10 with four boxes and goals.Source: §3 · p. 3
- Each level is split into lines, padded with walls when nonrectangular, concatenated into a character string, and passed through the model tokenizer.Source: §3 · p. 3
4 Models
The paper uses Generative Pre-Trained Transformers, attention-based language models that predict the next token from preceding context. Most experiments focus on GPT-2 and its variants because they are more available.
4 Models
- The experimental models are Generative Pre-Trained Transformers, an attention-based language-model class.Source: §4 · p. 3
- GPT-2 and GPT-3 predict the next token from the preceding-token context.Source: §4 · p. 3
- Most experiments use GPT-2 and variants because GPT-2 is more available.Source: §4 · p. 3
5 Metrics
The paper evaluates generated Sokoban levels on playability, novelty, and diversity, adding accuracy for prompt-conditioned experiments.
5 Metrics
- Playability is the proportion of generated levels that are valid and solvable under an A* search capped at 150,000 steps.The cap makes the measured playability a lower bound on the true rate.Source: §5 · p. 3
- Novelty measures the proportion of generated levels distinct from training levels by a string edit-distance threshold of k=5.This measure does not capture functional differences between levels.Source: §5 · p. 3
- Diversity measures the largest subset of generated levels mutually at least k=5 edit-distance apart, divided by the number generated.The clique search stops after one million iterations, so the reported diversity is a lower bound.Source: §5 · p. 3
- Accuracy is the proportion of generated levels within an experiment-specific tolerance of the prompted characteristic.For example, a solution length of 21 is accurate for a prompt requesting 25 when tolerance is 5.Source: §5 · p. 4
6 Experiments
The experiments test how pretraining, training-set size, and prompt conditioning affect level generation, with a preliminary GPT-3 evaluation on Microban data.
6.1 Effects of Pretraining
- Three GPT-2 variants—standard, Java-adapted, and untrained—test pretraining effects on Boxoban level generation.Models train for 100,000 steps; evaluation reports novelty, playability, diversity, and the score, averaged across five seeds using selected generation settings.Source: §6.1 · p. 4, Table 1 · p. 5
6.2 Effects of Dataset Size
- GPT-2 is retrained on four Boxoban dataset fractions and on Microban with flip and flip-plus-rotation augmentations to test data size and augmentation.The Boxoban fractions are 0.1%, 1%, 10%, and 100%; each model's highest average score is reported.Source: §6.2 · p. 4
6.3 Controllability
- For controllability, GPT-2 is trained on Boxoban levels prefixed with annotations for empty-space proportion or solution length, then prompted with an annotation alone.These characteristics differ in observability: empty-space proportion can be counted directly, while solution length generally requires solving the level.Source: §6.3 · pp. 4–5
6.4 Preliminary Investigation on GPT-3
- A preliminary GPT-3 experiment trains Davinci for 10 epochs on Microban datasets and evaluates novelty, playability, and overall score after a limited temperature and top-p sweep.The experiments use a single training seed; direct comparison with GPT-2 on all measures is infeasible because GPT-3 access is limited.Source: §6.4 · p. 5
7 Results
Generation performance improves with more training data, while pretraining has little apparent effect and prompt control is stronger for empty-space proportion than solution length; GPT-3 findings remain preliminary.
7.1 Effects of Pretraining
- All three GPT-2 variants generated novel, playable, and diverse levels; untrained GPT-2 was only marginally better, suggesting pretraining neither particularly helps nor hinders generation.An average score around 0.55 indicates levels were reliably valid and solvable without directly copying Boxoban training levels.Source: §7.1 · pp. 5–6
7.2 Effects of Dataset Size
- Small-data Boxoban and Microban conditions yield levels that are novel or playable, but not both; GPT-2's score correlates with dataset size, while Microban results show overfitting.The authors note that LSTMs have generated novel levels from a bootstrapped dataset originally containing only 12 samples, so small-data difficulty is not universal.Source: §7.2 · p. 6, Table 3 · p. 6
7.3 Controllability
- 17% accuracy on solution length and at most 3% on the combined condition were consistent with chance, while prompted outputs generally remained novel and playable.GPT-2 achieved perfect accuracy for the specified empty-space proportion within one tile.Source: §7.3 · p. 6
7.4 Preliminary Investigation on GPT-3
- GPT-3 produced novel, playable levels on both augmented Microban sets, and adding rotations increased overall performance, though the evidence comes from one run and limited tuning.The final condition's overall score approached that of GPT-2 trained on the full Boxoban dataset.Source: §7.4 · p. 6
8 Future Work
GPT-3’s results on small Microban datasets offer some optimism, but effective level generation may still depend on data availability. Future work includes adapting across games, improving controllability, and addressing data and novelty concerns.
8 Future Work
- Generating levels across games annotated with tile meanings and objectives could let LLMs use natural-language familiarity and rapid adaptation.The authors present this as a possibility, not a demonstrated result.Source: §8 · p. 6
- Few games have Boxoban-scale level collections; bootstrapping and richer augmentation are possible ways to expand training data, though data costs may exceed hand-authoring costs.The authors note that GPT-3’s Microban results offer some optimism that more sophisticated models may ease this tension.Source: §8 · pp. 6–7
- Simple prompts control empty-space proportions, but the model does not adhere to solution-length controls.The table also evaluates prompts combining both characteristics.Source: Table 4 · p. 7
- GPT-3 produces novel, playable, and diverse levels from a relatively small Microban training set.The authors treat this as encouraging, not decisive evidence about performance with limited data.Source: Table 5 · p. 7
- Pretraining may expose models to existing Sokoban levels, so novelty relative to fine-tuning data may not rule out copying; separating prompt understanding from level generation is one proposed mitigation.The proposed split would retain pretraining for natural-language prompts while using a model without pretraining for generation.Source: §8 · p. 7
- Controllable decoding, reinforcement learning, and prompt engineering could be combined to improve adherence to game-level functional constraints.The paper identifies these as opportunities for more sophisticated output control.Source: §8 · p. 7
9 Conclusion
The paper finds that LLMs can generate novel, playable Sokoban levels, with GPT-2 performance strongly dependent on data availability. Simple prompting controls empty-tile proportions but not solution length, while GPT-3’s small-data results remain preliminary.
9 Conclusion
- With sufficient data and training, LLMs generate diverse, novel, and playable Sokoban levels.The paper presents level generation as an additional capability of language models despite the domain’s distinct constraints and syntax.Source: §9 · p. 7
- GPT-2 performance strongly depends on data availability, while GPT-3 may generalize better from small datasets, though decisive conclusions require more work.The paper reports that pretraining generally does not hinder level generation, but its actual effect is unclear.Source: §9 · p. 7
- Simple prompting controls observable characteristics such as empty-tile proportion, but breaks down on more complex measures such as solution length.Source: §9 · p. 7
- LLM level generation shows promise, including as a possible way to address the general lack of game-level data.The paper frames this as potential, not an established solution to data scarcity.Source: §9 · p. 7
Ethical Statement
The ethical statement identifies risks that remain relevant even when models are trained to produce game levels.
Ethical Statement
- LLMs can have biases and limitations and may occasionally produce harmful or toxic text.Source: Ethical Statement · p. 7
- Training models to produce game levels does not entirely eliminate the possibility of harmful or toxic output.Source: Ethical Statement · p. 7
- Models may copy published levels encountered during pretraining, a risk to consider before widespread or commercial adoption.Source: Ethical Statement · p. 7