Games of No ChanceRichard J. Nowakowski Is Nine-Men's Morris, in the hands of perfect players, a win for white or for black--or a draw? Can king, rook, and knight always defeat king and two knights in chess? What can Go players learn from economists? What are nimbers, tinies, switches, minies? This book deals with combinatorial games, that is, games not involving chance or hidden information. Their study is at once old and young: though some games, such as chess, have been analyzed for centuries, the first full analysis of a nontrivial combinatorial game (Nim) only appeared in 1902. This book deals with combinatorial games, that is, games not involving chance or hidden information. Their study is at once old and young: though some games, such as chess, have been analyzed for centuries, the first full anlaysis of a nontrivial combinatorial game (Nim) only appeared in 1902. The first part of this book will be accessible to anyone, regardless of background: it contains introductory expositions, reports of unusual contest between an angel and a devil. For those who want to delve more deeply, the book also contains combinatorial studies of chess and Go; reports on computer advances such as the solution of Nine-Men's Morris and Pentominoes; and new theoretical approaches to such problems as games with many players. If you have read and enjoyed Martin Gardner, or if you like to learn and analyze new games, this book is for you. |
Contents
All Games Bright and Beautiful | 1 |
The Angel Problem | 3 |
Scenic Trails Ascending from SeaLevel Nim to Alpine Chess | 13 |
What Is a Game? | 43 |
Impartial Games | 61 |
ChampionshipLevel Play of DotsandBoxes | 79 |
ChampionshipLevel Play of Domineering | 85 |
The Gamesmans Toolkit | 93 |
Sowing Games | 287 |
New Toads and Frogs Results | 299 |
A Graphical XBased FrontEnd for Domineering | 311 |
Infinitesimals and CoinSliding | 315 |
Geography Played on Products of Directed Cycles | 329 |
A First Player Win | 339 |
New Values for Top Entails | 345 |
TakeAway Games | 351 |
Strides on Classical Ground | 99 |
Solving Nine Mens Morris | 101 |
Human Perfection at Checkers? | 115 |
Solving the Game of Checkers | 119 |
Combinatorial Game Theory in Chess Endgames | 135 |
Multilinear Algebra and Chess Endgames | 151 |
Using Similar Positions to Search Game Trees | 193 |
Where Is the ThousandDollar Ko? | 203 |
Eyespace Values in Go | 227 |
Loopy Games and Go | 259 |
Experiments in Computer Go Endgames | 273 |
Taming the Menagerie | 285 |
New Theoretical Vistas | 363 |
The Economists View of Combinatorial Games | 365 |
Games with Infinitely Many Moves and Slightly Imperfect Information | 407 |
The Reduced Canonical Form of a Game | 409 |
ErrorCorrecting Codes Derived from Combinatorial Games | 417 |
Tutoring Strategies in GameTree Search | 433 |
About David Richman | 437 |
Richman Games | 439 |
Stable Winning Coalitions | 451 |
Unsolved Problems in Combinatorial Games | 475 |
Selected Bibliography with a Succinct Gourmet Introduction | 493 |
Other editions - View all
Common terms and phrases
A. S. Fraenkel Algois algorithm Amelung Amer analysis annihilation games atomic weight Berlekamp and Wolfe Black Cambridge canonical form checkers chess coalitions coins combinatorial game theory complete Computer Science databases defined Diagram digraph Discrete Math Domineering Dots-and-Boxes E. R. Berlekamp Elwyn Berlekamp endgame example eyes eyespace Figure finite function game G game tree graph heap impartial games infinitesimal integer Internat J. H. Conway kothreats Left legal move Lemma loopy games loses Math Games misère Moews Molien MSRI MSRI Publications Volume mutual Zugzwang nim-value Nine Men's Morris Nowakowski opponent options P-positions partizan partizan games pawn pieces polynomial position problem Proc PROOF Publications Volume 29 R. K. Guy retrograde analysis Right rules sequence solved square Table tax rate temperature Theodor Molien Theorem thermographs Tinsley Toads token towers of Hanoi vector vertex vertices White winning strategy Yesha zero Zugzwang