This fascinating look at combinatorial games, that is, games not involving chance or hidden information, offers updates on standard games such as Go and Hex, on impartial games such as Chomp and Wythoff's Nim, and on aspects of games with infinitesimal values, plus analyses of the complexity of some games and puzzles and surveys on algorithmic game theory, on playing to lose, and on coping with cycles. The volume is rounded out with an up-to-date bibliography by Fraenkel and, for readers eager to get their hands dirty, a list of unsolved problems by Guy and Nowakowski. Highlights include some of Siegel's groundbreaking work on loopy games, the unveiling by Friedman and Landsberg of the use of renormalization to give very intriguing results about Chomp, and Nakamura's "Counting Liberties in Capturing Races of Go." Like its predecessors, this book should be on the shelf of all serious games enthusiasts.
Author(s): Michael H. Albert, Richard J. Nowakowski
Series: Mathematical Sciences Research Institute Publications
Edition: 1
Publisher: Cambridge University Press
Year: 2009
Language: English
Pages: 586
About
......Page 1
Games of No Chance 3......Page 5
Copyright
......Page 6
Contents......Page 7
Preface......Page 9
Surveys......Page 11
1. Introduction......Page 13
2. Combinatorial Game Theory......Page 14
3. Constraint logic......Page 19
4. Algorithms for two-player games......Page 20
5. Algorithms for puzzles......Page 35
6. Cellular automata and life......Page 54
References......Page 55
1. Introduction......Page 67
3. Pascal’s Beans......Page 70
4. Guiles......Page 73
5. The indistinguishability quotient construction......Page 75
6. Misere indistinguishability quotients......Page 77
7. What is a wild misere game?......Page 81
8. More wild quotients......Page 83
9. Computing presentations and MisereSolver......Page 85
10. Outlook......Page 89
Appendix: Genus theory......Page 91
References......Page 97
1. Introduction......Page 101
2. Loops large and small......Page 104
3. Stoppers......Page 106
4. Sides......Page 111
5. Some specific partizan games......Page 117
6. Impartial loopy games......Page 123
7. Conjunctive and selective sums......Page 127
8. Algorithms and computation......Page 129
References......Page 132
1. Introduction......Page 135
2. Games as a group......Page 136
3. Games as a partial order......Page 137
5. Counting games......Page 139
Acknowledgment......Page 140
References......Page 141
Standards......Page 143
Goal threats, temperature and Monte-Carlo Go......Page 145
1. Introduction......Page 146
3. Tactical goals......Page 147
4. A search algorithm for verifying threats......Page 149
5. Evaluation of goals......Page 152
6. Evaluation of moves......Page 153
7. Experimental results......Page 155
8. Conclusion and future work......Page 157
References......Page 158
1. Introduction......Page 161
2. Virtual connections......Page 162
3. Mustplay regions......Page 163
4. A Hex solver based on mustplay analysis......Page 164
5. Dead cell analysis......Page 166
6. A win-set for Puzzle 3......Page 169
References......Page 170
1. Introduction......Page 173
2. Results of a previous investigation......Page 175
3. Proving Tiger’s draw......Page 179
4. Implementation, optimization, verification......Page 181
References......Page 185
1. Introduction......Page 187
2. Capturing races......Page 188
3. Analysis of capturing races using CGT......Page 190
4. Examples......Page 195
5. Corridors......Page 201
Acknowledgements......Page 205
References......Page 206
1. Introduction......Page 207
2. Preliminaries......Page 208
3. Positions with one Frog......Page 210
4. Natural starting positions......Page 211
5. Some familiar values......Page 217
6. A little museum......Page 222
7. A solution......Page 223
References......Page 224
1. Introduction......Page 225
2. Preliminaries......Page 226
3. Fusion......Page 229
4. Long irreducible cycles......Page 232
5. Simplification of alternating cycles......Page 236
Appendix: Algorithms for comparing games......Page 238
References......Page 242
1. Introduction......Page 243
2. The ko status of a life-and-death problem......Page 245
3. Characterization of bent-4-type positions......Page 248
4. Modification of the status defining procedure......Page 250
5. Summary......Page 254
Appendix: Limitations......Page 255
References......Page 256
1. Introduction......Page 259
2. Unique representations......Page 260
3. The generation of positions......Page 261
4. The evaluation of positions......Page 263
5. Computational aspects......Page 265
6. Unusual positions in the database......Page 267
7. The influence of external liberties......Page 273
References......Page 277
Complexity......Page 279
1. Introduction......Page 281
2. Gadgets used in the reduction......Page 284
3. PSPACE-completeness......Page 288
4. Opposing telescopes that overlap in at most one space......Page 291
5. Summary and outlook......Page 293
References......Page 294
1. Introduction......Page 297
2. Reduction framework......Page 299
3. Amazons......Page 301
4. Konane......Page 307
5. Cross Purposes......Page 309
References......Page 315
Impartial......Page 317
1. Introduction......Page 319
2. The general framework......Page 320
3. Double bumping......Page 322
4. Finite chains......Page 325
5. Dense linear order......Page 330
6. Observations and open problems......Page 335
References......Page 336
1. Introduction......Page 339
2. P-positions for general End-Wythoff games......Page 340
3. P-positions for special positions......Page 343
4. Generating P-positions in polynomial time......Page 351
References......Page 356
1. Introduction......Page 359
2. Renormalization framework......Page 362
3. Implications and new directions......Page 378
4. Open questions......Page 382
References......Page 384
1. Introduction......Page 387
2. Closeness of the g-values to the 0-values......Page 393
3. A recursive algorithm for the n-th g-value......Page 406
Appendix: Lemmas of Section 2.5......Page 417
References......Page 420
Theory of the small......Page 421
Yellow-Brown Hackenbush......Page 423
Historical note......Page 427
References......Page 428
Introduction......Page 429
Ordinal numbers......Page 430
Partizan End Nim......Page 431
Some examples......Page 434
References......Page 435
1. Introduction......Page 437
2. Preliminaries......Page 438
3. Temper......Page 441
4. Reduced canonical forms......Page 443
5. Reduction by ε......Page 448
6. All-small reductions......Page 451
References......Page 454
1. Introduction......Page 457
3. {1} versus {k}......Page 458
4. {1, 2k} versus {1, 2k+1}......Page 459
5. {1, others} versus {1, 3, 5,..., 2k+1}......Page 460
6. Odd versus Even......Page 463
7. {1, odds} versus {2, 4}......Page 468
References......Page 471
Columns......Page 473
A. Taking and breaking games......Page 475
B. Pushing and placing pieces......Page 484
C. Playing with pencil and paper......Page 490
D. Disturbing and destroying......Page 491
E. Theory of games......Page 493
References......Page 498
2. Why are games intriguing and tempting?......Page 501
3. Why are combinatorial games hard?......Page 504
6. Why isn’t it larger?......Page 506
7. The dynamics of the literature......Page 507
9. Idiosyncrasies......Page 508
11. The bibliography......Page 509
