CSAIL Event Calendar: Previous Series

Games, Puzzles, and Computation

Speaker: Bob Hearn , Project MAC, CSAIL, MIT
Date: November 7 2005
Time: 4:10PM to 5:00PM
Location: Patil conference room (32-G449)
Contact: Louis-Philippe Morency, 617-253-4278, lmorency@csail.mit.edu
Relevant URL:

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. We would like to know whether the game is polynomial, NP-complete, PSPACE-complete, etc. Hardness proofs involve constructing "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. But usually the computer is not an ordinary, deterministic Turing machine, and is instead more like a nondeterministic TM, or an alternating TM, etc. 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 I would like to explore.

I will briefly present several recent hardness results, including sliding-block puzzles, sliding-coin puzzles, Rush Hour, Sokoban, hinged polygon dissections, plank puzzles, the Dyson telescope game, Amazons, and Konane. I will try to show how these results can be seen in view of a larger framework of computation in terms of generalized games. In this framework, cellular automata are zero-player games, puzzles are one-player games, and ordinary games are two-player games.

Joint work with Erik Demaine and many others.

See other events that are part of CSAIL Student Seminar Series Fall 2005

See other events happening in November 2005