Math Annex 1100
Department of Mathematics
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.