More games of no chance

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