Overview

In its broadest sense, combinatorial game theory (CGT) is the study of twoperson, perfect information games of no chance. For each position in such a game, the theory defines a temperature, which is a measure of the importance of the next move. CGT differs from economic game theory, which emphasizes multiplayer games including elements of chance and imperfect information. Most economic games focus on maximizing some payoff or score; CGT was originally more concerned with getting the last move, but it now also applies to games whose outcomes are determined by scores.

CGT is a branch of mathematics. It seeks to find and understand strategies which can provably succeed against any opposition. This differs from the primary goal of human or computer competitors, who are more focused on making fewer serious mistakes than their opponents. CGT seeks to understand every position, including composed problems. It assigns no special importance to any official “opening” position, nor to who gets the first move. Each position is treated as its own game, and both possibilities for who moves next are given appropriate consideration. Most CGT results employ the “divide and conquer” methodology:

• (1) partition the board into disjoint regions;

• (2) analyze each region, condensing it into an appropriate data structure;

• (3) analyze the entire board position as the (disjunctive) sum of these disjoint regions.

The results are so interesting that many combinatorial game theorists now also play and analyze hybrid games, which are sums of positions in different games. Such a hybrid sum is called a gallimaufry.

The most successful application of CGT to Anglo-American checkers has been to composed problems (e.g., [Berlekamp 2002]). Elkies [1996] has successfully applied CGT to composed chess problems, and even to at least one position which occurred in a world championship chess match. But in most historical games of chess and checkers, every position that occurs is already as well understood by players who know no CGT as by those who do.