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 |
|
2 Nimbers 3 Surreal numbers |
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
Finite nonloopy games
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.
