QUANTITATIVE GO, AND SOME OTHER COMBINATORIAL GAMES

A LECTURE BY PROF. ELWYN BERLEKAMP
University of California at Berkeley

Elwyn Berlekamp

Combinatorial game theory is concerned with two-person perfect-information games, especially those classes of positions for which winning strategies can be stated explicitly, or at least proved to exist. The powerful mathematical methods (often requiring only paper and pencil, no computers) are most successful when applied to games whose positions often decompose into "sums". The many examples of such games include Nim, Dots and Boxes, Hackenbush (best played with colored chalk and erasures), Domineering (played with dominoes on a checkerboard), Konane (popular in ancient Hawaii), Amazons (invented less than fifteen years ago, but which has attracted a substantial following on the Internet), and Go (a popular Asian board game dating back several thousand years, and which supports nearly 2,000 active professionals today). The theory also applies very well to the fascinating new game called "Clobber", invented in Nova Scotia in the summer of 2001. In many of these games, a mathematically defined "temperature" provides a numerical measure of the value of the next move. The extension of this notion to loopy positions, such as kos in Go, appeared in "Games of No Chance" in 1996. A subsequent extension, called "Environmental Go", includes a stack of coupons in addition to the Go board. This has led to fruitful collaborations between game theoreticians and professional 9-dan Go players. For the past four years, we have been developing methods and techniques which allow us to get rigorous analyses of the last 50 to 100 moves of some professional games, and we not infrequently discover fatal mistakes. We will present a broad introductory overview of this subject, including a fascinating problem in which Go, chess, checkers, and domineering are all played concurrently. The time may now be ripe for new efforts to combine modern mathematical game theory with alpha-beta pruning and other traditional AI minimax search techniques.

About the speaker:

Elwyn Berlekamp has been Professor of Mathematics and of Electrical Engineering/Computer Science at UC Berkeley since 1971. He was associate chairman of EECS for computer science at Berkeley in 1975-77. In the late 1980s he also served four years on the UC President's Science Advisory Committee for Los Alamos and Livermore National Laboratories.

In the early 1980s, Berlekamp took industrial leaves and reduced his faculty appointment to part-time to pursue off-campus ventures. He was founder and president of Cyclotomics, which was acquired by Eastman Kodak in 1985 and renamed "Kodak Berkeley Research", and a cofounder of several other successful companies, including IC Designs and Cylink. (NASDAQ: CYLK)

Berlekamp has 12 patented inventions (now all public domain), mostly dealing with algorithms and devices for synchronization and error-correction. He has nearly 100 publications, including 2 books on algebraic coding theory and 4 books on the mathematical theory of combinatorial games, the most recent of which is "The Dots and Boxes Game", recently published by AK Peters. This book will be featured in Scientific American's January 2001 issue. Berlekamp is a member of the National Academy of Sciences, the National Academy of Engineering, and of the American Academy of Arts and Sciences. From 1994-1998, he was chairman of the board of trustees of the Mathematical Sciences Research Institute (MSRI).

Since 1991, Berlekamp's primary research interest has been extensions of the mathematical theory of games and applications to Go. He chaired the organizing committee of a workshop at MSRI in July 2000, about which more information can be found at www.msri.org.

Contact information:

Elwyn Berlekamp berlek@math.berkeley.edu
Hazelnut
64 Shattuck Square, Suite 212e
Berkeley, CA 94704
Pnone: (510) 849-4214
Web: