Why Oatmeal is Cheap: Kolmogorov Complexity and Procedural Generation
Open accessAbstract
Although procedural generation is popular among game developers, academic research on the topic has primarily focused on new applications, with some research into empirical analysis. In this paper we relate theoretical work in information theory to the generation of content for games. We prove that there is a relationship between the Kolomogorov complexity of the most complex artifact a generator can produce, and the size of that generator’s possibility space. In doing so, we identify the limiting relationship between the knowledge encoded in a generator, the density of its output space, and the intricacy of the artifacts it produces. We relate our result to the experience of expert procedural generator designers, and illustrate it with some examples.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
A long path of perceptually similar nodes, especially with distinct edges, signals an unresponsive region of the expressive possibility space.
“A lengthy path that contains long sequences of perceptually similar nodes, especially if their edges are distinct, is an indicator of an unresponsive area of the expressive possibility space, the expressive equivalent of the 1000 bowls of oatmeal problem (Compton 2016;Rabii and Cook 2023).”
From Expressive Response Curves: Testing Expressive Game Feel with A* (2023) · cites this paper as Rabii and Cook 2023
Section 5.3, “The Cost of Oatmeal” (page unavailable), describes large quantities of perceptually similar content as the oatmeal problem, and §4.1.2 says a large possibility space may contain very similar outputs. The paper does not describe paths of nodes, distinct edges, or those features as an indicator of an unresponsive region of expressive possibility space. (LLM, conf=0.86)
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
No references could be resolved yet.
Research works printed but not linked: 8
- Michael Cook, Jeremy Gow, Gillian Smith, and Simon Colton. 2022. Danesh: Interactive Tools for Understanding Procedural Content Generators. IEEE Transactions on Games 14, 3 (2022), 329-338.
- Andrei N. Kolmogorov. 1998. On Tables of Random Numbers (Reprinted from "Sankhya: The Indian Journal of Statistics", Series A, Vol. 25 Part 4, 1963). Theoretical Computer Science 207, 2 (1998), 387-395.
- Julian Mariño, Willian Reis, and Levi Lelis. 2021. An Empirical Evaluation of Evaluation Metrics of Procedurally Generated Mario Levels. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (2021).
- Emily Short. 2015. The Annals of the Parrigues.
- Gillian Smith and Jim Whitehead. 2010. Analyzing the expressive range of a level generator. In Proceedings of the 2010 Workshop on Procedural Content Generation in Games.
- Adam Summerville. 2018. Expanding Expressive Range: Evaluation Methodologies for Procedural Content Generation. In Proceedings of the Fourteenth AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment. 116-122.
- Adam Summerville, Julian R. H. Mariño, Sam Snodgrass, Santiago Ontañón, and Levi H. S. Lelis. 2017. Understanding Mario: An Evaluation of Design Metrics for Platformers. In Proceedings of the 12th International Conference on the Foundations of Digital Games. ACM.
- Adam Summerville, Sam Snodgrass, Matthew Guzdial, Christoffer Holmgård, Amy K. Hoover, Aaron Isaksen, Andy Nealen, and Julian Togelius. 2018. Procedural content generation via machine learning (PCGML). IEEE Transactions on Games 10, 3 (Sept. 2018), 257-270.
Cited by
Sorted by citations
Expressive Response Curves: Testing Expressive Game Feel with A*
Junius, N., & Carstensdottir, E. (2023) · Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment · doi:10.1609/aiide.v19i1.27524
- Authors
- Rabii, Y., & Cook, M.
- Affiliations
- Queen Mary University of London (GB)
- King's College London (GB)
- Venue
- Proceedings of the 18th International Conference on the Foundations of Digital Games
- Publisher
- ACM
- Published
- 2023-04-12
- Pages
- 1-7
- OpenAlex
- W4364360830
- Cited by
- 8
- References
- 0
- Citations by year
- 2025: 5 · 2024: 1 · 2023: 2
- FWCI
- 1.42
- Type
- conference paper
- Language
- en
- Open access
- green
- arxiv.org
- Licence
- Locations
- International Conference on the Foundations of Digital Games (FDG) (publishedVersion)
- arXiv (Cornell University) (submittedVersion, cc-by-nc-sa)
- Research Portal (King's College London) (submittedVersion, cc-by)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Artificial Intelligence in Games
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Computability, Logic, AI Algorithms
- Physical Sciences › Computer Science › Computer Graphics and Computer-Aided Design › Computer Graphics and Visualization Techniques
- Keywords
- procedural content generation, Kolmogorov complexity, game content generation, possibility space, information theory
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
