Games, Puzzles, And Computation

Bob Hearn, H3 Labs, Palo Alto, CA

Stevenson Hall 1300
11:00 AM - 11:50 AM

One can frame a game or a puzzle as a decision problem: from this configuration, does the puzzle have a solution? Can Black win the game? The computational complexity of the decision problem can then be investigated. Reviewing the properties of the complexity classes (NP-complete, PSPACE-complete, etc.), it’s possible to briefly survey several hardness results, including sliding-block puzzles, sliding-coin puzzles, TipOver, Rush Hour, Sokoban, hinged polygon dissections, plank puzzles, the Dyson telescope game, Amazons, and Konane. These results are all applications of a larger framework of computation in terms of generalized games (as opposed to Turing machines), called Constraint Logic. In this framework, cellular automata are zero-player games, puzzles are one-player games, and ordinary games are two-player games. Surprisingly, some team games turn out to be undecidable, even though they are played with finite physical resources.