Why Oatmeal Is Cheap: Kolmogorov Complexity and Procedural Generation [pdf]
knivesandpaintbrushes.org
knivesandpaintbrushes.org
One well-known example of this is The Ten Thousands Bowls of Oatmeal Problem, a term coined by Kate Compton and now one of the best-known idioms among procedural generation practitioners. In this analogy, Compton likens procedurally generated content to bowls of oatmeal, and uses this to highlight the meaninglessness of appeals to variety or unpredictability which often accompany sales pitches related to procedural generation. Every bowl of oatmeal is unique, Compton explains, but that does not make them interesting or valuable. Designers use this to understand that procedural generation alone does not guarantee variety or interest, and that systems must be carefully designed to use generative methods as an expressive tool, rather than a solution in and of itself.
As a VFX-person I have to add that the variation can be a value in itself.
E.g. imagine a level in a computer game that plays in an office building. Having procedural desks with different heights and stuff on it with various degrees of use and personalization seems boring, but in sum it makes a big room look more like the real thing, because most real things have these tiny imperfections. In games where e.g. you have items to find the variance of the environment is a major factor in the enjoyability of the game. Too much and nobody can tell items from assets, too little and items feel like on a board game.
That being said, procedural systems must either be incredibly intricate or use a lot of artistic input to produce good results.
E.g. a good level artist might tell a whole story of human relationships with the way a room is set up, with the pictures/notes those office workers hung at the walls, which objects decorated their work places, what is missing from their places etc.
A purely procedural approach will look very arbitrary unless it tries to model the same underlying rules (e.g. "simulating" the owner of said desk and their role within the system that produced that room). If done correctly this can look extremely good (better than mediocre level designers) — but this is rarely taken that far.
A trick of writing is to leave stuff off the page. If you put everything on, it’s tiresome. If there’s nothing left off, characters seem hollow. A character background or even scenes that exist but aren’t shared means there’s a sense to things that the reader can pick up on, even if they don’t know exactly what it is.
I can see the same thing happening with generative AI. Rather than procedurally generating desks and the objects on them, you generate a sales team. The composition of the team makes sense. Then you give each employee a paragraph of background, then from that generate a desk. This will give something much more cohesive than adding a family picture if rand < 0.2.
The problem with procedural generation is (over)use of it to generate gameplay. In your example it'd be "we have 50 million different offices to explore!", but they're all just different arrangements of the same desks.
If you're reading this Mike or Azalea: Hi!
[1] https://www.wolframscience.com/nks/p231--four-classes-of-beh...
Yes. Wolfram gets the point across, but the lack of formality makes the taxonomy appear somewhat arbitrary which leaves one hanging. Thanks for the tip about Ilachinski's book. I notice it was published around the same time as NKS which makes me curious about the overlap in content; it certainly seems to have a more formal approach.
The Artificial War book is pretty cool. I was into war games (board games back in the 80s), and his multi-agent approach was unique at the time and is fun to play with.
Game theory dynamics are fascinating. I have Nowak's Evolutionary Dynamics in my shelf, in which he covers for instance spatial prisoner's dilemma modelled as cellular automata.
Wolfram's new physic's book is visually appealing, and I am starting it soon.
I tried making up my own rules without reference to see just how difficult it is to achieve anything similar to Conway's GoL, and it is eyeopening. I do love the variations on it where the simulations look almost like microscope vids of actual organisms. Artificial Life sims. People are getting creative in these sims, and some produce some beautiful and engaging animations.
I thought it was empirical? E.g. sample Turing drawings: https://maximecb.github.io/Turing-Drawings/
They clearly seem to me to fall into four kinds: Boring, Oscillating, Chaotic, Life.
The first three kinds of simple system are, um, pretty obvious: Boring is static, Oscillators have movement but are static in time so to speak, chaotic systems overwhelm themselves with too much movement, "living" systems seem to balance stasis and chaos.
But what does it mean? ;)
> By the definition of 𝑃𝑎 , we know there are at least as many programs in 𝑃𝑎 as there are artefacts in 𝜋 (𝐺), i.e. |𝑝𝑎 | ≥ #𝜋 (𝐺).
I'm not sure how the definition of P_a leads to |p_a| >= #\pi(G)...
P_a definitely can’t be all the maximally compressed programs for specific a. There’s at most 2^|p_a| of them and if G were the identity function on m length binary strings where m>|p_a|..
Not necessarily - just feed in a stream of pseudorandom data?
Even a 32 bit seed space can generate more environments than a player could ever explore, each with arbitrary levels of detail.
The data stream may be lacking in true complexity, but (done right) it would be indistinguishable from the player's perspective.
(Or am I missing something?)
In some sense, if you feed your reader truly random letters (generate uniformly and independently), they should be maximally surprised.
But they aren't. They will be bored. And they will be able to predict roughly how many spaces there will be in next million characters. Or roughly how many repetitions of the sequence 'xyz'.
And they will notice that there's no overarching structure.
If you give people a carefully written text, the individual letters will be more predictable, but your readers / viewers will feel more surprised when they learn that Darth Vader is Luke's father.
[1] https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.70....
The most interesting planets tend to be more forested or have extreme terrain features, but the patterns are still obvious.
I remember spending countless hours with Fractint (https://en.wikipedia.org/wiki/Fractint) in the 1990s. Back then the programme fit on a floppy disk (or so). Today the latest version from https://fractint.org/ is about 9 MiB in size.
If you want to transmit n pictures of the Mandelbrot set, you can either send me n PNGs, or you can transmit Fractint once and n tuples of (top, left, bottom, right) coordinates. You can do the math what size n you need before the former becomes much, much bigger than the latter.
But, I like the spirit of your comment. So perhaps the thought-provoking thing might be the following observation:
Most of the bytes and complexity in the fractint binary are not at all necessary for displaying the fractals. You could generate them with much simpler software. No, most of the bytes are there to generate the fractals _quickly_.
Kolmogorov complexity doesn't care about runtimes as long as they are finite. Humans do.
For example, cherry-picking Quaker Foods North America, PepsiCo 23Q1 earnings reported[1] +10% revenue on -5% volume; this pattern is rearing its head across the consumer staples sector.
Putting this into pragmatic perspective, local prices where I'm at are $5.68/42oz ~= €4.30/kg for Quaker Oats name brand as a proxy baseline, while Walmart's Great Value house brand are $3.98/42oz ~= €3.00/kg on the cheaper end of the spectrum.
[1] https://www.sec.gov/Archives/edgar/data/77476/00000774762300...
https://www.ah.nl/producten/product/wi48405/ah-volkoren-have...