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 tend to 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). Aaron Siegel has developed a symbol manipulation program which handles most of the theory, including his recent extensions to certain loopy games such as Fox & Geese, and Hare & Hounds.

I will present a broad introductory overview of this subject, and outline its relationships to some of the other areas of mathematics and/or computer science with which it has some overlap: logic, set theory, artificial intelligence, coding theory, complexity theory, statistical game theory, linear programming.

The figure above shows interesting problems in Go, Domineering, checkers, and chess. In Domineering, white must play a gray domino onto an empty pair of horizontally adjacent white squares; black must play onto an empty pair of vertically adjacent black squares. Combinatorial game theory enables one to solve each of these four problems, as well as a fifth problem which is more interesting. In this problem, all four games are played concurrently. At each turn, you may make a legal move in any one on any one of the four boards. In this combined game, the details of the rules (e.g., "compulsory jumps" in checkers, and "kos" in Go) may be defined in any of several different ways, but the winning strategy is robust. It wins under many plausible interpretations of the rules.