Awesome paper on games math

Giovanni Viglietta of the University of Pisa has posted up a paper called "Gaming is a hard job, but someone has to do it!". 

In it, he not only analyzes a variety games to determine their complexity class, but he also arrives at a few metatheorems that are generically applicable for all game design. In other words, "include these features and your game gains fun."

Remember, according to the Theory of Fun, pattern mastery and learning is why the brain plays games. And if you recall my presentation on Games Are Math, I made the case that entire classes of "tasty" problems can be described in mathematical terms (specifically, complexity class), because they are problems that always feel like they are on the margin of our ability.

So if you make use of these specific sorts of math problems — which are actually represented in the game as not looking like math at all, mind you — you are effectively inserting exactly the sort of problem that the brain finds most interesting.

These are not the only sort of problem the brain likes, of course — there ae psychological challenges, social challenges, physical challenges, emotional challenges, and so on. But an enormous amount of what we tend to call "gameplay" falls under the mathematical realm.

Among the metatheorems that Viglietti identifies:

Metatheorem 1. Any game exhibiting both location traversal and single-use paths is NP-hard.

Metatheorem 2. If a game features doors and pressure plates, and the avatar has to reach an exit location in order to win, then:
a) Even if no door can be closed by a pressure plate, and if the game is non-planar, then it is P-hard.
b) Even if no door is controlled by two pressure plates, the game is NP-hard.
c) If each door may be controlled by two pressure plates, then the game is PSPACE-hard.

Metatheorem 3. If a game features doors and k-switches, and the avatar has to reach an exit location in order to win, then:
a) If k > 1 and the game is non-planar, then it is P-hard.
b) If k > 2, then the game is NP-hard.
c) If k > 3, then the game is PSPACE-hard.

Despite the jargon, these are immediately applicable to your games right now, and phrased in game terms are fairly simple features.

The paper goes on to provide proofs and examples for games ranging from Boulder Dash to Doom.