Games, Puzzles, and Computation

Back

The authors show that there are underlying mathematical reasons for why games and puzzles are challenging (and perhaps why they are so much fun). They also show that games and puzzles can serve as powerful models of computation—quite different from the usual models of automata and circuits—offering a new way of thinking about computation. The appendices provide a substantial survey of all known results in the field of game complexity, serving as a reference guide for readers interested in the computational complexity of particular games, or interested in open problems about such complexities.

About the Authors

Robert A. Hearn is currently a Visiting Research Scholar in the Neukom Institute for Computational Science at Dartmouth College. He completed his Ph.D. in the Computer Science and Artificial Intelligence Laboratory at MIT. Prior to that he spent several years in the software industry, where he co-wrote the popular program ClarisWorks.

Erik D. Demaine is an Associate Professor of Electrical Engineering and Computer Science in the Computer Science and Artificial Intelligence Lab at MIT. He is a MacArthur Fellow, an Alfred P. Sloan Research Fellow, and the current International Francqui Chair at the Université Libre de Bruxelles, Belgium.