Combinatorial game theory Guide, Meaning , Facts, Information and Description
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).
| Table of contents |
|
2 Finite nonloopy games 3 Nimbers 4 See also |
A structure is called a collection of games if
Formal definitions
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. The zero element, if it exists, is unique.
If is finite and nonloopy, then it contains a zero element.
Let be the smallest collection of games containing 0 and such that
Finite nonloopy games
Then all finite nonloopy games are isomorphic to a subcollection of . We can work solely with .
Define a binary operator
- and .
The set of second-player-win games, P is defined recursively. The negative of a game is defined recursively as follows:
- .
The relation is defined by iff . 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 . Finally one can show that the addition is an abelian group operation.
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 ordinal numbers. A function from the ordinals to nimbers is defined. The Sprague-Grundy theorem states that every impartial game is -equivalent to a nimber.