Games, Puzzles, and Computation (AK Peters/CRC Recreational Mathematics Series)

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. Read more... 1. Introduction ---- I. Games in General. 2. The Constraint-Logic Formalism --- 3. Constraint-Logic Games --- 4. Zero-Player Games (Simulations) --- 5. One-Player Games (Puzzles) --- 6. Two-Player Games --- 7. Team Games --- 8. Perspectives on Part I ---- II. Games in Particular. 9. One-Player Games (Puzzles) --- 10. Two-Player Games --- 11. Perspectives on Part II --- 12. Conclusions ---- Appendices. 1. Survey of Games and Their Complexities --- 2. Computational-Complexity Reference --- 3. Deterministic Constraint Logic Activation Sequences --- 4. Constraint-Logic Quick Reference Contents 6 1. Introduction 9 1.1 What is a Game? 11 1.2 Computational Complexity Classes 14 1.3 Constraint Logic 17 1.4 What's Next? 19 I. Games in General 21 2. The Constraint-Logic Formalism 22 2.1 ConstraintGraphs 23 2.2 Planar ConstraintGraphs 26 2.3 Constraint-Graph Conversion Techniques 27 3. Constraint-Logic Games 31 3.1 Zero-Player Games (Simulations) 32 3.2 One-Player Games (Puzzles) 35 3.3 Two-Player Games 37 3.4 Team Games 40 4. Zero-Player Games (Simulations) 44 4.1 Bounded Games 45 4.2 Unbounded Games 48 5. One-Player Games (Puzzles) 60 5.1 Bounded Games 61 5.2 Unbounded Games 66 6. Two-Player Games 76 6.1 Bounded Games 77 6.2 Unbounded Games 81 6.3 No-Repeat Games 86 7. Team Games 89 7.1 Bounded Games 90 7.2 Unbounded Games 93 8. Perspectives on Part I 105 8.1 Hierarchies of Complete Problems 105 8.2 Games, Physics, and Computation 106 II: Games in Particular 109 9. One-Player Games (Puzzles) 110 9.1 TipOver 110 9.2 Hitori 115 9.3 Sliding-Block Puzzles 118 9.4 The Warehouseman's Problem 123 9.5 Sliding-Coin Puzzles 123 9.6 Plank Puzzles 125 9.7 Sokoban 129 9.8 Push-2-F 132 9.9 Rush Hour 136 9.10 Triangular Rush Hour 139 9.11 Hinged Polygon Dissections 140 10. Two-Player Games 143 10.1 Amazons 143 10.2 Konane 148 10.3 Cross Purposes 151 11. Perspectives on Part II 157 12. Conclusions 158 12.1 Contributions 158 12.2 Future Work 159 Appendices 161 A. Survey of Games and Their Complexities 162 A.1 Cellular Automata 163 A.2 Games of Block Manipulation 164 A.3 Games of Tokens on Graphs 169 A.4 Peg-Jumping Games 173 A.5 Connection Games 173 A.6 Other Board Games 174 A.7 Pencil Puzzles 174 A.8 Formula Games 179 A.9 Other Games 181 A.10 Constraint Logic 185 A.11 Open Problems 185 B. Computational-Complexity Reference 191 B.1 Basic Definitions 191 B.2 Generalizations of Turing Machines 194 B.3 Relationship of Complexity Classes 197 B.4 List of Complexity Classes Used in this Book 197 B.5 Formula Games 198 C. Deterministic Constraint Logic Activation Sequences 201 D. Constraint-Logic Quick Reference 212 Bibliography 214 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. 1. Games In General -- 2. Games In Particular -- Appendices. Robert A. Hearn, Erik D. Demaine. Includes Bibliographical References (p. 217-229) And Index. 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.