Speaker

Professor Berlekamp is a Professor of Mathematics at The University of California, Berkeley. His research interests include Algorithms, Applied Analysis, Games, Finance and Information Theory. He is a Fellow of the American Association for the Advancement of Science, as well as a member of Sciences, Xamplify.com and the National Academy of Engineering.

Description

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 “suns”. 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 (Weiqi).

In most 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 three 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 modem mathematical game theory with alpha-beta pruning and other traditional Al minimax search techniques.