248 Pages
    by A K Peters/CRC Press

    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.

    Introduction
    What is a Game?
    Computational Complexity Classes
    Constraint Logic
    What’s Next?
    I Games in General
    The Constraint-Logic Formalism
    Constraint Graphs
    Planar Constraint Graphs
    Constraint-Graph Conversion Techniques
    Constraint-Logic Games
    Zero-Player Games (Simulations)
    One-Player Games (Puzzles)
    Two-Player Games
    Team Games
    Zero-Player Games (Simulations)
    Bounded Games
    Unbounded Games
    One-Player Games (Puzzles)
    Bounded Games
    Unbounded Games
    Two-Player Games
    Bounded Games
    Unbounded Games
    No-Repeat Games
    Team Games
    Bounded Games
    Unbounded Games
    Perspectives on Part I
    Hierarchies of Complete Problems
    Games, Physics, and Computation
    II Games in Particular
    One-Player Games (Puzzles)
    Tip Over
    Hitori
    Sliding-Block Puzzles
    The Warehouseman’s Problem
    Sliding-Coin Puzzles
    Plank Puzzles
    Sokoban
    Push-2-F
    Rush Hour
    Triangular Rush Hour
    Hinged Polygon Dissections
    Two-Player Games
    Amazons
    Konane
    Cross Purposes
    Perspectives on Part II
    Conclusions
    Contributions
    Future Work
    Appendices
    Survey of Games and Their Complexities
    Cellular Automata
    Games of Block Manipulation
    Games of Tokens on Graphs
    Peg-Jumping Games
    Connection Games
    Other Board Games
    Pencil Puzzles
    Formula Games
    Other Games
    Constraint Logic
    Open Problems
    Computational-Complexity Reference
    Basic Definitions
    Generalizations of Turing Machines
    Relationship of Complexity Classes
    List of Complexity Classes Used in this Book
    Formula Games
    Deterministic Constraint Logic Activation Sequences
    Constraint-Logic Quick Reference

    Biography

    Robert A. Hearn, Dartmouth College, Hanover, New Hampshire, USA

    Erik Demaine, Massachusetts Institute of Technology, Cambridge, USA

    "… the games also provide an extremely well-suited platform for the introduction of a unified method for determining complexity using constraint logic … considers not only mathematically oriented games, but also games that may well be suitable for non-mathematicians … The book also contains a comprehensive overview of known results on the complexity of games and therefore with its 177 references is also an excellent reference book on the topic … warmly recommended for anyone who likes games and wants to know more about their (mathematical) complexity."
    Internaionale Mathematische Nachrichten, December 2012

    "Games, Puzzles, and Computation will serve well in roles similar to that of Garey and Johnson’s book. In particular, the text would work exceedingly well as a reference for what’s known in the subfield of game/puzzle complexity or for self-study by someone familiar with basic computational complexity principles who is interested in learning more about the complexity of games and puzzles. It would also serve well as supplementary material to an upper-level undergraduate or entry-level graduate special topics course in game/puzzle complexity. It could also be used as the primary text for such a course (in principle) given extra preparation by the instructor … ."
    —Daniel Apon, SIGACT News, September 2011

    "The authors show that there are underlying mathematical reasons that games and puzzles are challenging (which perhaps explains why they are so much fun). Complementarily, 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."
    L'Enseignement Mathematique, December 2009

    "… intriguing book … Hearn and Demaine present an elegant family of benchmarks they have developed, allowing them to settle open questions on the complexity of various games. … and the authors certainly provide plenty to mull over. The publisher A K Peters has done a quite nice job of production, as well. All in all, this is a book well worth looking into."
    —Leon Harkleroad, MAA Reviews, December 2009

    "This book will be of interest to advanced readers working in this area."
    —Brian Borchers, CHOICE, February 2010