Combinatorial game theory

This article may be too technical for most readers to understand. Please expand it to make it accessible to non-experts — without removing the technical details — and remove this notice when this has been accomplished.

Combinatorial game theory (CGT) is a mathematical theory that studies a certain kind of game. These games are all two-player games which have a position, which the players take turns changing in certain well-defined ways or moves, trying to achieve a well-defined winning condition. CGT does not study games of chance (like poker), but restricts itself to games whose position is public to both players, and in which the set of available moves is also public.

In simple terms, by applying CGT to a position you are attempting to determine the optimum sequence of moves for both players until the game ends, and by doing so discovering the optimum move in the current position. In practice, this process is tortuously difficult unless the game is very simple.

CGT should not be confused with another mathematical theory, traditionally called game theory, used in the theory of economic competition and cooperation: this other theory does involve chance and imperfect knowledge, and has the players deciding their moves simultaneously.

The modern CGT tradition goes back to the solution of Nim. It can, in principle, be applied to games like Chess, checkers, Go, Hex, and similar board games, but these games are mostly too complicated to allow complete analysis. The theory has had some recent successes in analyzing Go endgames, however.

The founders of the general theory were Elwyn Berlekamp, John Conway and Richard Guy, in collaborative work during the 1960s that took some time to be published fully.

For a pedagogical discussion, see Combinatorial game theory (pedagogy). For its history, see Combinatorial game theory (history).

Contents

1 Formal definitions

2 Finite nonloopy games

Formal definitions

A structure $\langle\mathcal{C},L,R\rangle$ is called a collection of games if

$L:\mathcal{C}\rightarrow 2^\mathcal{C}$

and

$R:\mathcal{C}\rightarrow 2^\mathcal{C}$

where $2^\mathcal{C}$ is the power set of $\mathcal{C},$

and

$\forall G,H\in\mathcal{C}\,[L(G)=L(H)\land R(G)=R(H)]\Rightarrow G=H.$

The elements of $\mathcal{C}$ are called games and the convention here is that they would be denoted by the upper case Latin letters G,H,K,... .

Define the binary relation, R (for reachable) between $\mathcal{C}$ and itself by

$GRH\,\!$ iff $G\in L(H)\cup R(H)$ .

$\mathcal{C}$ is called loopy if $\exists G\in\mathcal{C}\,G\bar{R}G$ where $\bar{R}$ is the transitive closure of R. Otherwise, it's called nonloopy.

If there exists an element 0 of $\mathcal{C}$ , with $L(0)=R(0)=\emptyset$ , then we call it the zero element. The zero element, if it exists, is unique.

If $\langle\mathcal{C},L,R\rangle$ is a collection of games and $G_0\in\mathcal{C}$ then the game $G 0$ can be 'played' as follows: There are two players, called Left and Right. First, Left chooses an element $G_1\in L(G_0)$ (if one exists). Then Right chooses an element $G_2\in R(G_1)$ (if one exists). Then Left chooses an element $G_3\in L(G_2)$ and so on. If a player cannot move (i.e. the relevant $L$ or $R$ set is empty) then, by definition, they lose the game.

Finite nonloopy games

If $\mathcal{C}$ is finite and nonloopy, then it contains a zero element.

Let $\mathcal{C}_{fin}$ be the smallest collection of games containing 0 and such that

For all finite $\mathcal{L},\mathcal{R}\subset\mathcal{C}_{fin}$ , there exists $K\in\mathcal{C}_{fin}$ such that $L(K)=\mathcal{L},R(K)=\mathcal{R}$ .

Then all finite nonloopy games are isomorphic to a subcollection of $\mathcal{C}_{fin}$ . We can work solely with $\mathcal{C}_{fin}$ .

Define a binary operator

$+:\mathcal{C}_{fin}\times\mathcal{C}_{fin}\rightarrow\mathcal{C}_{fin}$

recursively by

$L(G+H)=(L(G)+H)\cup(G+L(H))$ and $R(G+H)=(R(G)+H)\cup(G+R(H))$ .

This definition of addition of games is well-defined and unique; and it is commutative. Intuitively, one should think of the game $G + H$ as consisting of the two games $G$ and $H$ being played "side by side": On his turn, Left can either make a move in $G$ and leave $H$ alone, or vice versa, and likewise for Right.

The negative of a game is defined recursively as follows:

$\forall G\in\mathcal{C}_{fin} L(-G)=\{-K:K\in R(G)\}\land R(-G)=\{-K:K\in L(G)\}$ .

This definition is well-defined and unique. Intuitively, -G is just "G with Left and Right reversed".

Define a set of games $P_L\subset\mathcal{C}_{fin}$ recursively as follows:

$G\in P_L$ iff $\forall H\in L(G): -H\notin P_L$ .

A player loses precisely when they run out of moves. The above definition characterizes games such that no matter what the left player does, the right player can force them to eventually run out of moves. One might call them "Left to play and lose" games.

One can similarly define $P R$ , and we note that $P_R = \{-G : G\in P_L\}$ . Next, define

$P = P_L \cap P_R$ .

$P$ is the set of second-player-win games (whoever moves first, the second player can force a win). A useful exercise at this point is to show that $\forall G\in\mathcal{C}_{fin}: G + (-G)\in P$ . This observation motivates the following:

Define a relation $\simeq$ by $G\simeq H$ iff $G+(-H)\in P$ . This is an equivalence relation; and it respects the addition and negative operations. Therefore, the operations + and - can be defined on the quotient set defined by the equivalence relation $\simeq$ . Finally one can show that the addition is an abelian group operation.

Nimbers

An impartial game is one where $\forall G\in\mathcal{C}\, L(G)=R(G)$ .

The set of nimbers is defined as the smallest subcollection containing 0 and containing $\{G\cup L(G)|G\cup R(G)\}$ for every G in the subcollection.

Nimbers are the combinatorial game theoretic analogue of the ordinal numbers. A function from the ordinals to nimbers is defined. The Sprague-Grundy theorem states that every impartial game is $\simeq$ -equivalent to a nimber.

Domineering

An example of a partial game is Domineering. In this game, a grid is drawn, on which Left can play vertical dominoes and Right can play horizontal dominoes. Various interesting Games, such as hot games, appear in Domineering, due to the fact that there is sometimes an incentive to move, and sometimes not.

References

Elwyn Berlekamp & David Wolfe (1997). Mathematical Go:Chilling Gets the Last Point. A K Peters Ltd. ISBN 1568810326.
John Horton Conway (2001). On Numbers And Games. A K Peters Ltd. ISBN 1568811276.simple:Combinatorial game theory