Pólya urn

11 Sep 2016

If you are generating a random dungeon, like in a Roguelike, there's a sort of paradox. One possibility is that you generate the entire dungeon ahead of time, and then progressively reveal it to the player. This is how we normally understand real-world buildings to work - they have definite architecture, before you visit them. Another possibility is that you generate the dungeon just-in-time. When the player opens a door to an unobserved room, then at that moment, the game figures out what size and shape and contents are.

The paradox is that the player can't (without cheating and looking at the game's memory) really tell which is the case. I associate it with idea of solipsism.

It's not a binary, either; there's a whole "how solipsistic is this game's implementation"? Perhaps one game generates a level at a time, but shows one room at a time. This is more solipsistic than another game that generates all levels ahead of time and then shows one room at a time, but less solipsistic than a third game that generates each room, exactly when the player first opens the door.

Usuaully, the developer of the game chooses when to generate any particular feature based primarily on performance concerns. For example, if the game has a large and detailed overworld, the developer may choose to generate the landscape on-demand, in order to avoid keeping the entire map in memory. On the other hand, if each level of a dungeon is both small and self-contained, then generating the entire level when the player first arrives on that level may be more convenient than generating it piecemeal as the player walks through it.

There's a whole "observer independent world" sidetrack that we could go into. Some games, such as Skyrim, generate "level-appropriate" enemies and loot when the player observes a space for the first time. This tends to undercut the substance and reality of the world. For example, the player will be "punished" for spending time studying Speech in a city when they next go into a cave, because the player's total-skill-point increases will cause more dangerous monsters to be generated, and Speech is unlikely to help with Draugr. However, let's not go down that side-track, tempting though it is, and confine our attention to techniques that sustain the illusion of a world.

The Pólya Urn is the idea of selecting a ball from an urn filled with white and black balls, and, if the ball is white, putting two white balls back into the urn, and, if the ball is black, putting two black balls back into the urn.

This has a peculiar feature of baking the player's past interactions with the urn into the player's future interactions. If you have drawn 75% white balls and 25% black balls from the urn, then your probability of drawing a white ball in the future is moved toward 75% - the more you interact with the urn, the more definite the urn's behavior becomes. After a while, the urn becomes more like a weighted coin. Because of the solipsism phenomenon, a player with no access to the internals, just the sequence of white and black balls, will have difficulty distinguishing the urn from a weighted coin, with its weight generated once, at the beginning.

Bootstrapping the game from the player's previous behavior is a really excellent idea. It finesses several problems. First, the player is hungry for "content", and content is expensive to produce. (Of course, you could go to multiplayer, but that introduces its own puzzles, like liquidity - can you find someone to play with?).

Second, the player wants to make meaningful long-term decisions - by building the player's future out of the player's past, you're building a mechanism for that to occur. Sean Barrett's Succor, and Extreme Exorcism and Chronotron each use this explicitly, but games with a significant amount of digging or building, such as Minecraft, Dungeon Keeper, or SimCity, derive a significant portion of their interest from this interaction between the player's past and the player's future.

Role-playing games without building or digging have some of this, but often less, precisely because the player's statistics, skill allocations, equipment and inventory are a low-bandwidth way for the player's past to communicate with the player's future.

Anyway, I think Pólya urn generation is neat and I'd like to see more use of it in procedural generation stuff. I wrote two number sequence completion puzzle generators, one with and one without using Pólya urn generation. a, b. If you play twenty or thirty rounds, I think you can tell which is which.