Middlebury College
Department of Computer Science Seminar
Games, Puzzles, and Computation
Bob Hearn
Department of Psychological and Brain Sciences
Dartmouth College
Sliding-coin puzzles, sliding-block puzzles, TipOver, Rush Hour, Sokoban, Minesweeper, hinged polygon dissections, plank puzzles, the Dyson telescope game, Amazons, and Konane are among a large number of games and puzzles which can be studied computationally as “decision problems”. In particular, we are interested in the computational complexity of answering questions such as: “Does the puzzle have a solution?” and “Can Black win the game?” The talk will begin by reviewing the characteristics of various classes of computational complexity (polynomial time, NP-complete, PSPACE-complete, etc.. ) We will then explore hardness proofs involving the construction of “gadgets”, which often resemble computational elements. For a large class of games and puzzles, an assembly of such gadgets can be viewed as a kind of computer—not an ordinary, deterministic Turing machine, but instead more like a nondeterministic TM, or an alternating TM. However, it’s possible to interpret the hardness framework for the game or puzzle itself as the model of computation, rather than the corresponding Turing machine, and it is this idea we will explore. We will see how these results can be seen in view of a larger framework of computation in terms of generalized games, 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. This is joint work with Erik Demaine and others.
Wednesday, October 25, 2006
12:20 p.m. to 1:15 p.m.
McCardell Bicentennial Hall 104
Lunch will be provided at 12:05 p.m.
All are welcome to attend