Colloquium Details
Games, Puzzles, and Computation
| Author: | Robert Hearn Neukom Institute for Computational Science, Dartmouth College |
|---|---|
| Date: | May 01, 2008 |
| Time: | 15:30 |
| Location: | 220 Deschutes |
| Host: | Andrzej Proskurowski |
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 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.
Biography
Bob Hearn is a research assistant professor in the Neukom Institute for Computational Science at Dartmouth College. He completed his Ph.D. in 2006 at MIT, on game-based models of computation; look for his book "Games, Puzzles, and Computation" this fall from A K Peters. Earlier work at MIT included implementing parts of Marvin Minsky's "Society of Mind" model of intelligence. Prior to entering grad school he spent several years in the software industry, where he co-wrote the popular program ClarisWorks.