Main Page | See live article | Alphabetical index

Combinatorial game theory

This is a discussion of combinatorial game theory (CGT) from a theoretical mathematical viewpoint. For a pedagogical discussion, see combinatorial game theory (pedagogy). For its history, see combinatorial game theory (history).

A structure is called a collection of games if and where is the power set of and . The elements of 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 and itself by iff .

is called loopy if  where  is the transitive closure of R. Otherwise, it's called nonloopy.

If there exists an element 0 of , with , then we call it the zero element.

Lemma 1: The zero element, if it exists is unique.

Table of contents
1 Finite nonloopy games
2 Nimbers
3 Surreal numbers

Finite nonloopy games

Lemma 2: If is finite and nonloopy, then it contains a zero element.

Let be the smallest collection of games containing 0 and .

Lemma 3: All finite nonloopy games are isomorphic to a subcollection of .

So, without any loss of generality, we can work solely with .

We can define a binary operator recursively by

and .

Lemma 4: This definition is well-defined and unique.

Lemma 5: .

The set of second-player-win games, P is defined recursively as follows: I'll add the definition later; it's getting late

The negative of a game is defined recursively as follows: .

Lemma 6: This definition is well-defined and unique.

The relation is defined by iff .

Lemma 7: is an equivalence relation.

Lemma 8: .

Lemma 9: .

Therefore, the operations + and - can be defined on the quotient set defined by the equivalence relation

Lemma 10: The binary operation + acting upon the quotient set is an Abelian group with - as the inverse function and 0 as the identity.

Nimbers

An impartial game is one where .

The set of nimbers is defined as the smallest subcollection containing 0 and containing for every G in the subcollection.

Nimbers are the combinatorial game theoretic analogue of the ordinals and in fact, we can define a function from the ordinals to nimbers.

Sprague-Grundy Theorem: Every impartial game is -equivalent to a nimber. See Sprague-Grundy theorem.

Surreal numbers

See Surreal numbers.