|
Abstract:
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. I will begin by reviewing the properties of Turing
machines and of the complexity classes I'll be discussing (NP-
complete, PSPACE-complete, etc.), then briefly present several recent
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.
Joint work with Erik Demaine and others.
|