More Games of No Chance (Mathematical Sciences Research Institute Publications, Series Number 42)

This book is a state-of-the-art look at combinatorial games, that is, games not involving chance or hidden information. It contains articles by some of the foremost researchers and pioneers of combinatorial game theory, such as Elwyn Berlekamp and John Conway, by other researchers in mathematics and computer science, and by top game players. The articles run the gamut from new theoretical approaches (infinite games, generalizations of game values, two-player cellular automata, alpha-beta pruning under partial orders) to the very latest in some of the hottest games (Amazons, Chomp, Dot-and-Boxes, Go, Chess, Hex). Many of these advances reflect the interplay of the computer science and the mathematics. The book ends with an updated bibliography by A. Fraenkel and an updated version of the famous annotated list of combinatorial game theory problems by R. K. Guy, now in collaboration with R. J. Nowakowski. Cover......Page 1 About......Page 2 Series: Mathematical Sciences Research Institute Publications, Vol 42......Page 4 More Games of No Chance......Page 6 Copyright......Page 7 Contents......Page 8 Preface......Page 12 The Big Picture......Page 14 1. Introduction and Background......Page 16 2. Definitions of Idempotents with Opening Ceremonies......Page 19 3. Definitions of Idempotents Without Opening Ceremonies......Page 21 4. The Addition Table......Page 24 5. Other Properties of These Idempotents......Page 25 6. Suggestions for Further Work......Page 33 References......Page 35 The Lattices......Page 38 Lattices up to Day 3......Page 40 References......Page 42 More Infinite Games......Page 44 1. Introduction......Page 50 2. Structure and Definitions......Page 51 3. Shallow Pruning......Page 54 4. Deep Pruning......Page 56 5. Bridge......Page 58 6. Related Work......Page 59 References......Page 60 The Abstract Structure of the Group of Games......Page 62 The Old Classics......Page 72 1. Introduction......Page 74 2. An Illustrative Pair of Endgames......Page 75 3. A Game of Pawns......Page 77 4. Embedding into Generalized Chess......Page 83 5. Stopped Files......Page 84 6. The Pawns game with Stopped Files......Page 86 References......Page 91 1. Introduction......Page 92 2. How D Can Win......Page 94 3. How G Can Win......Page 96 References......Page 99 Reading a Thermograph......Page 102 The Jiang–Rui Environmental Go Game......Page 107 Orthodox Play......Page 108 Actual Play......Page 113 Acknowledgments......Page 117 References......Page 118 1. Easy Examples without Kos......Page 120 2. A Simple 1-point Ko......Page 124 3. An Example Containing a Hidden Ko......Page 125 4. The Rogue Positions......Page 130 References......Page 136 1. Introduction......Page 138 2. Proof Sketch......Page 139 3. The Artificial Games......Page 140 4. Games and Game Sums......Page 142 5. Switch Games......Page 143 6. Switch games in Go......Page 146 References......Page 148 1. Global Wins and Global Threats......Page 150 2. A CGT Model Based on Loopy Games......Page 152 3. An Algorithm Based on Cutoffs in the Game Tree......Page 153 4. Application to Chess Endgames......Page 157 5. Summary and Outlook......Page 161 References......Page 162 1. Introduction......Page 164 2. Hex and Its History......Page 165 3. Virtual Connections and Semi-Connections......Page 166 4. Deduction Rules......Page 168 5. Hierarchy of Virtual Connections......Page 171 6. Electrical Resistor Circuits......Page 172 7. Hexy Plays Hex......Page 174 Acknowledgements......Page 175 Appendix......Page 176 References......Page 177 1. Introduction......Page 180 3. Regions in “n-k Space”......Page 182 4. The Linearized Approximation to n_k......Page 187 5. Hypercube Tic-Tac-Toe and Combinatorial Phase Space......Page 188 6. Misere Hypercube Tic-Tac-Toe......Page 190 8. On the Boundary Between Regions 3 and 4......Page 191 Supplemental Annotated Bibliography......Page 193 Introduction and Notation......Page 196 1. The Ordinals, Very Briefly......Page 197 2. Size......Page 198 4. Other Termination Criteria......Page 200 5. The Fundamental Theorem......Page 201 6. Two Constructions......Page 204 7. P-Ordered Positions......Page 206 8. Side-Top Positions......Page 207 9. Two-wide Chomp......Page 209 10. Three-Wide Chomp......Page 212 11. A Three-Dimensional Example......Page 216 12. Open Questions......Page 223 13. Conclusion......Page 224 References......Page 225 1. Introduction......Page 226 2. Fast, Memory Efficient Retrograde Algorithm......Page 227 3. Reducing the Size of the Database......Page 230 4. Results from the Database......Page 233 5. The aegp-aaee Endgame......Page 236 References......Page 239 The New Classics......Page 242 Introduction......Page 244 Isolated Go......Page 248 The Global Problem......Page 250 Conclusion......Page 253 References......Page 254 1. Introduction......Page 256 2. Board Partitioning in Amazons......Page 257 3. Line Segment Graphs......Page 258 4. Filling Territory and Defective Areas......Page 262 5. Zugzwang in Amazons......Page 265 6. Programs that Play Amazons......Page 270 References......Page 272 1. Introduction......Page 274 2. Amazons......Page 275 3. Analyzing Amazons......Page 277 4. Technical Aspects......Page 278 5. Game-Theoretic Results......Page 282 References......Page 290 1. Introduction......Page 292 2. Preliminaries......Page 293 3. Idiosyncrasies of the Exponentially Large Game-Graph......Page 296 4. The Additivity of γ......Page 299 5. The Structure of γ......Page 301 6. Sparse Vectors Suffice......Page 304 7. An O(n^6) Algorithm for γ for the Case q=1......Page 306 8. Forcing a Win in Cellular Automata Games for 1-Regular Games......Page 310 9. Epilogue......Page 315 Acknowledgment......Page 316 References......Page 317 1. Introduction......Page 320 2. 2 \times n Boards......Page 321 3. Boards of Width 3, 4, 5, 7, 9, 11 and Others......Page 323 4. Playing on Cylinders and Tori......Page 325 References......Page 327 Introduction to Loony Endgames and Controlled Value......Page 330 The Formula for Controlled Value......Page 331 “Very Long” Defined......Page 332 Extracting a Profitable Subbracelet......Page 339 Comments......Page 341 References......Page 343 Introduction......Page 344 References......Page 351 1. Solitaire......Page 354 2. Duotaire......Page 357 References......Page 362 1. Introduction......Page 364 2. The NP-Completeness Proof......Page 365 3. Phutball and Checkers......Page 369 References......Page 372 1. Introduction......Page 374 2. Oddish Phutball......Page 376 References......Page 379 1. Introduction......Page 382 3. Automorphism-based strategy......Page 384 4. Closure properties of \mathcal{c}_{auto}......Page 386 5. Complexity of \mathcal{c}_{auto}......Page 389 6. Game AVOID (K_n, P_2)......Page 391 References......Page 393 1. Introduction......Page 396 3. Main Theorem......Page 397 4. Conclusion......Page 398 5. Bibliography......Page 399 Puzzles and Life......Page 400 1. Introduction......Page 402 2. One Column in Polynomial Time......Page 403 3. Hardness for 5 Colors and 2 Columns......Page 410 4. Hardness for 3 Colors and 5 Columns......Page 412 5. Conclusion......Page 415 References......Page 416 1. Introduction......Page 418 2. Model......Page 421 3. Triangular Grid......Page 422 4. General Tools......Page 428 5. Square Grid......Page 430 References......Page 443 1. Introduction......Page 446 2. A Brief History of Spaceship Searching......Page 448 3. Notation and Classification of Patterns......Page 449 4. State Space......Page 452 5. Search Strategies......Page 455 6. Lookahead......Page 457 7. Fast Neighbor-Finding Algorithm......Page 459 8. Conclusions......Page 462 References......Page 464 Surveys......Page 468 Unsolved Problems in Combinatorial Games......Page 470 2. Why are Games Intriguing and Tempting?......Page 488 3. Why are Combinatorial Games Hard?......Page 490 5. Why Is the Bibliography Vast?......Page 492 7. The Dynamics of the Literature......Page 493 9. Idiosyncrasies......Page 494 11. The Bibliography......Page 495 This book is a state-of-the-art look at combinatorial games, that is, games not involving chance or hidden information. It contains a fascinating collection of articles by some of the top names in the field, such as Elwyn Berlekamp and John Conway, plus other researchers in mathematics and computer science, together with some top game players. The articles run the gamut from new theoretical approaches (infinite games, generalizations of game values, 2-player cellular automata, Alpha-Beta pruning under partial orders) to the very latest in some of the hottest games (Amazons, Chomp, Dot-and-Boxes, Go, Chess, Hex). Many of these advances reflect the interplay of the computer science and the mathematics. The book ends with an updated bibliography by A. Fraenkel and an updated and annotated list of combinatorial game theory problems by R. K. Guy. Not situations that cannot be won, such as an election campaign that is outspent a hundred to one, but combinatorial games, those that involve no chance or hidden information, including such classics as chess, checkers, and go. Researchers in combinatorial game theory, mathematics, and computer science join veteran game players to look at some new perspectives on them. The 32 papers are from a July 2000 conference in Berkeley, California. They are not indexed. Annotation copyrighted by Book News, Inc., Portland, OR We assume the reader is familiar with the first volume of Winning Ways [Berlekamp et al. 1982], including Conway's axiomatization of G, the group of partesan games under addition, which can also be found in [Conway 1976].