Combinatorial game theory

Combinatorial game theory (CGT) is a mathematical theory of games, which while part of game theory in a broad sense has its own tradition going back to the solution of Nim. It deals abstractly with a very large range of games for two players (only) that can be reduced to tree-like structures, with a characteristic ending rule: the player left with no (legal) play loses. On that rather slender basis has been constructed a theory that can be applied to some traditional games (most notably go), as well as a large number of new games the investigation of which it has stimulated. The founders of the general theory were Elwyn Berlekamp, John Conway and Richard Guy, in collaborative work during the 1960s that took some time fully to be published.

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

Formal definitions

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

<math>L:\mathcal{C}\rightarrow 2^\mathcal{C}<math>

and

<math>R:\mathcal{C}\rightarrow 2^\mathcal{C}<math>

where <math>2^\mathcal{C}<math> is the power set of <math>\mathcal{C},<math>

and

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

The elements of <math>\mathcal{C}<math> 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 <math>\mathcal{C}<math> and itself by

<math>GRH\,\!<math> iff <math>G\in L(H)\cup R(H)<math>.

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

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

Finite nonloopy games

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

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

<math>\forall G,H\in\mathcal{C}_{fin} \exists K\in\mathcal{C}_{fin} L(K)=G\land R(K)=H<math>.

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

Define a binary operator

<math>+:\mathcal{C}_{fin}\times\mathcal{C}_{fin}\rightarrow\mathcal{C}_{fin}<math>

recursively by

<math>L(G+H)=(L(G)+H)\cup(G+L(H))<math> and <math>R(G+H)=(R(G)+H)\cup(G+R(H))<math>.

This definition of addition of games is well-defined and unique; and it is commutative.

The set of second-player-win games, P is defined recursively. The negative of a game is defined recursively as follows:

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

This definition is well-defined and unique.

The relation <math>\simeq<math> is defined by <math>G\simeq H<math> iff <math>G+(-H)\in P<math>. It 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 <math>\simeq<math>. Finally one can show that the addition is an abelian group operation.

Nimbers

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

The set of nimbers is defined as the smallest subcollection containing 0 and containing <math>\{G\cup L(G)|G\cup R(G)\}<math> 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 <math>\simeq<math>-equivalent to a nimber.

See also

• Surreal number
• Zero game
• Fuzzy game