Abstract:

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 (popular in Europe in the 1870s, then usually played with coins) Dots and Boxes (a pencil and paper game popular among school children) 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) Go (a popular Asian board game dating back several thousand years, and which supports nearly 2,000 active professionals today)

In all 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.

The book "Mathematical Go" [1994] included a wide range of hard Go endgame problems, most of which had temperature 1. Solutions often entailed special infinitesimals and other abstract mathematical concepts, including "canonical values" not understood by traditional Go players. "Quantitative Go", on the other hand, eshews these more abstract mathematical game values in favor of more emphasis on means and temperatures, whose values are rational numbers that satisfy systems of linear constraints somewhat similar to those encountered in other linear programming problems.

We will present a broad introductory overview of this subject, including a summary of current status of each of the following subproblems:

1. Orthodox Accounting. A precise methodology for keeping track of the small (usually inconsequential) differences between optimum play when a thick stack of coupons is present and when it is not. How the costs or benefits of "unorthodox moves" can be quantified and bounded in terms of a short list of quantities, usually all v. small.
2. Canonical Refinements. Why the complexity of canonical values is often irrelevant, and means and temperatures are sufficient.
3. Top-Down Thermography, including a preliminary program called "Winsolve", which does calculations on human-entered moves.
4. Bottom-Up Thermography, including a preliminary program called "Bruteforce", which resolves even very complicated loopy positions, but not very quickly.
5. Federations of Regions, which may be interdependent.
6. Dogmatic Komasters. A recent innovation which locally quantifies means of troublesome but common hyperactive kos
7. Superkos. Very rare but theoretically fascinating positions in which the game graph contains loops of length >=4 without subloops of length 2, and in which Chinese, Japanese, and western rules differ substantially.
8. Applications to Computer Go.

Several of these problems are related to tree-searching, hashing, and data-structuring issues studied in many artificial intelligence applications, and in some other games which involve bidding strategies.