Quantitative Go and some other combinatorial games

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

Here is a picture containing positions in four game boards: Go, Domineering, checkers, chess.   This is a carefully composed (contrived?) problem(s).  The four warmup problems are to play each game.  The more interesting and more challenging problem is to play them all concurrently.  Each player makes one move on one board, and then it becomes the other player's turn.  There are lots of ways of specifying what's the objective of this game (e.g., get the last move, checkmate the opponent's chess king...) and several plausible ways of defining what's legal w.r.t. compulsory checkers' jumps and the ko ban in Go, but the winning strategy is so robust that it doesn't depend on such fine points of the rules.