encyclopedia

Categories: Game theory | Combinatorial game theory

Combinatorial game theory

(Redirected from Combinatorial game)

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).

Contents

1 Formal definitions

2 Finite nonloopy games

3 Nimbers

4 Domineering

5 See also

Formal definitions

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

$L:\mathcal{C}\rightarrow 2^\mathcal{C}$

and

$R:\mathcal{C}\rightarrow 2^\mathcal{C}$

where $2^\mathcal{C}$ is the power set of $\mathcal{C},$

and

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

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

$GRH\,\!$ iff $G\in L(H)\cup R(H)$ .

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

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

If $\langle\mathcal{C},L,R\rangle$ is a collection of games and $G_0\in\mathcal{C}$ then the game $G 0$ can be 'played' as follows: There are two players, called Left and Right. First, Left chooses an element $G_1\in L(G_0)$ (if one exists). Then Right chooses an element $G_2\in R(G_1)$ (if one exists). Then Left chooses an element $G_3\in L(G_2)$ and so on. If a player cannot move (i.e. the relevant $L$ or $R$ set is empty) then, by definition, they lose the game.

Finite nonloopy games

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

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

For all finite $\mathcal{L},\mathcal{R}\subset\mathcal{C}_{fin}$ , there exists $K\in\mathcal{C}_{fin}$ such that $L(K)=\mathcal{L},R(K)=\mathcal{R}$ .

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

Define a binary operator

$+:\mathcal{C}_{fin}\times\mathcal{C}_{fin}\rightarrow\mathcal{C}_{fin}$

recursively by

$L(G+H)=(L(G)+H)\cup(G+L(H))$ and $R(G+H)=(R(G)+H)\cup(G+R(H))$ .

This definition of addition of games is well-defined and unique; and it is commutative. Intuitively, one should think of the game $G + H$ as consisting of the two games $G$ and $H$ being played "side by side": On his turn, Left can either make a move in $G$ and leave $H$ alone, or vice versa, and likewise for Right.

The negative of a game is defined recursively as follows:

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

This definition is well-defined and unique. Intuitively, -G is just "G with Left and Right reversed".

Define a set of games $P_L\subset\mathcal{C}_{fin}$ recursively as follows:

$G\in P_L$ iff $\forall H\in L(G): -H\notin P_L$ .

A player loses precisely when they run out of moves. The above definition characterizes games such that no matter what the left player does, the right player can force them to eventually run out of moves. One might call them "Left to play and lose" games.

One can similarly define $P R$ , and we note that $P_R = \{-G : G\in P_L\}$ . Next, define

$P = P_L \cap P_R$ .

$P$ is the set of second-player-win games (whoever moves first, the second player can force a win). A useful exercise at this point is to show that $\forall G\in\mathcal{C}_{fin}: G + (-G)\in P$ . This observation motivates the following:

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

Nimbers

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

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

Domineering

An example of a partial game is Domineering. In this game, a grid is drawn, on which Left can play vertical dominoes and Right can play horizontal dominoes. Various interesting Games, such as hot games , appear in Domineering, due to the fact that there is sometimes an incentive to move, and sometimes not.