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 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
- GRH 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.
Finite nonloopy games
If is finite and nonloopy, then it contains a zero element.
Let be the smallest collection of
games containing 0 and such that
- .
Then all finite nonloopy games are isomorphic to a subcollection of . We can work solely with .
Define a binary operator
-
recursively by
- and .
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:
- .
This definition is well-defined and unique.
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.
See also
|