Why Oatmeal is Cheap: Kolmogorov Complexity and Procedural Generation

Autor:	Rabii, Younès, Cook, Michael
Rok vydání:	2023
Předmět:	Computer Science - Artificial Intelligence Computer Science - Human-Computer Interaction Computer Science - Information Theory
Zdroj:	Rabii Younes and Michael Cook. "Why Oatmeal is Cheap: Kolmogorov Complexity and Procedural Generation." Proceedings of the 18th International Conference on the Foundations of Digital Games. 2023
Druh dokumentu:	Working Paper
DOI:	10.1145/3582437.3582484
Popis:	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. Comment: Foundation of Digital Games 2023, Best Paper Award, 11 pages, 4 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2305.02131 Zobrazit plný text záznamu View this record from Arxiv