More Games of no Chance
Contents
Preface xi
The Big Picture 1
Idempotents Among Partisan Games 3
Elwyn Berlekamp
On the Lattice Structure of Finite Games 25
Dan Calistrate, Marc Paulhus, and David Wolfe
More Infinite Games 31
John H. Conway
Alpha-Beta Pruning Under Partial Orders 37
Matthew L. Ginsberg and Alan Jaffray
The Abstract Structure of the Group of Games 49
David Moews
The Old Classics 59
Higher Nimbers in Pawn Endgames on Large Chessboards 61
Noam D. Elkies
Restoring Fairness to Dukego 79
Greg Martin
Go Thermography: The 4/21/98 Jiang–Rui Endgame 89
Bill Spight
An Application of Mathematical Game Theory to Go Endgames: Some
Width-Two-Entrance Rooms With and Without Kos 107
Takenobu Takizawa
Go Endgames Are PSPACE-Hard 125
David Wolfe
Global Threats in Combinatorial Games: A Computation Model with
Applications to Chess Endgames 137
Fabian M¨aser
The Game of Hex: The Hierarchical Approach 151
Vadim V. Anshelevich
Hypercube Tic-Tac-Toe 167
Solomon W. Golomb and Alfred W. Hales
Transfinite Chomp 183
Scott Huddleston and Jerry Shurman
A Memory Efficient Retrograde Algorithm and Its Application to Chinese
Chess Endgames 213
Ren Wu and Donald F. Beal
The New Classics 229
The 4G4G4G4G4 Problems and Solutions 231
Elwyn Berlekamp
Experiments in Computer Amazons 243
Martin M¨uller and Theodore Tegos
Exhaustive Search in Amazons 261
Raymond Georg Snatzke
Two-Player Games on Cellular Automata 279
Aviezri S. Fraenkel
Who Wins Domineering on Rectangular Boards? 307
Michael Lachmann, Cristopher Moore, and Ivan Rapaport
Forcing Your Opponent to Stay in Control of a Loony Dot-and-Boxes
Endgame 317
Elwyn Berlekamp and Katherine Scott
1 × n Konane: A Summary of Results 331
Alice Chan and Alice Tsai
1-Dimensional Peg Solitaire, and Duotaire 341
Cristopher Moore and David Eppstein
Phutball Endgames Are Hard 351
Erik D. Demaine, Martin L. Demaine, and David Eppstein
One-Dimensional Phutball 361
J. P. Grossman and Richard J. Nowakowski
A Symmetric Strategy in Graph Avoidance Games 369
Frank Harary, Wolfgang Slany, and Oleg Verbitsky
A Simple FSM-Based Proof of the Additive Periodicity of the
Sprague–Grundy Function of Wythoff’s Game 383
Howard Landman
Puzzles and Life 387
The Complexity of Clickomania 389
Therese C. Biedl, Erik D. Demaine, Martin L. Demaine,
Rudolf Fleischer, Lars Jacobsen, and Ian Munro
Coin-Moving Puzzles 405
Erik D. Demaine, Martin L. Demaine, and Helena A. Verrill
Searching for Spaceships 433
David Eppstein
Surveys 455
Unsolved Problems in Combinatorial Game Theory: Updated 457
Richard K. Guy and Richard J. Nowakowski
Bibliography of Combinatorial Games: Updated 475
Aviezri S. Fraenkel