Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

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 "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.