Games of No Chance
Edited by Richard Nowakowski
Preface
Combinatorial Game Theory, as an academic discipline, is still in its infancy. Many analyses of individual games have appeared in print, starting in 1902 with C. L. Bouton's analysis of the game of Nim. (For exact references to the works mentioned here, please see A. Fraenkel's bibliography in this volume.) It is was not until the 1930's that a consistent theory for impartial games was developed, independently, by R. Sprague and P. M. Grundy, later to be expanded and expounded upon by R. K. Guy and C. A. B. Smith. (Guy is still going strong, as evidenced by his energy at this Workshop.) J. H. Conway then developed the theory of partizan games, which represented a major advance. Based on this theory, D. Knuth wrote his modern moral tale, Surreal Numbers. The collaboration of E. R. Berlekamp, J. H. Conway and R. K. Guy gave us Winning Ways, which "set to music", or at least to "rhyme", the theory so far. In the process, many more games were discovered and analyzed: but more were discovered than solved!
This Workshop, held from 11 to 21 July 1994, gave evidence of the growing interest in combinatorial games on the part of experts from many fields: mathematicians, computer scientists, researchers in artificial intelligence, economists, and other social scientists. Players, some of whom make their living from games, also attended. Visitors such as D. Knuth and H. Wilf dropped in for a few hours or days and gave impromptu lectures. There was much cross-fertilization of ideas, as could be expected from a meeting of people from such varied backgrounds. One major paper by A. Fraenkel was conceived and essentially written during the Workshop, being inspired by V. Pless's talk.
But the Workshop was not all seminars. There were books, games and puzzles on display. Two official tournaments, Dots-and-Boxes and Domineering, attracted a lot of participants, and carried $500 first prizes (funded by E. R. B.) The final matches were shown over closed-circuit TV, so that the spectators could have a running commentary! Neither game is completely solved: Dots-and-Boxes is played by many school children, yet still holds mysteries for adults.
The articles in this volume are divided into four groups. Part I is introductory. Part II contains papers on some of the "classical" games, such as chess and Go. Part III studies many other games, of greatly varying degrees of difficulty. Part IV contains articles that push the traditional theory in new directions: for example, by considering games more general than the strict definition of combinatorial games allows (see pages 1 and 363). The book closes with a list of unsolved problems by R. K. Guy, and a Master Bibliography by A. Fraenkel. The increasing role of computers can be witnessed throughout, in areas ranging from the solution of particular games to the use of the computer in teaching humans.
Many thanks must go the staff of MSRI, who helped make the Workshop a success. The facilities were wonderful. Thanks are due also to the Workshop chairs, E. R. Berlekamp and R. K. Guy. Together with the rest of the organizing committee (J. H. Conway, N. D. Elkies, A. S. Fraenkel, J. G. Propp, K. Thompson, and myself), they put together a wonderful and rich program.
In the preparation of this book, we are especially grateful to Silvio Levy, who essentially rewrote two of the articles, edited all the others, found good placements for the more than 200 figures, redrew some of them, and arranged the typesetting.
Richard J. Nowakowski