Discover

:''This article is on the theory of combinatorial games. For the theory that includes games of chance and games of imperfect knowledge, see Game theory''
'Combinatorial game theory' ('CGT') is a mathematical theory that only studies two-player games which have a ''position'' which the players take turns changing in defined ways or ''moves'' to achieve a defined winning condition. CGT does not study games of chance (like poker), but restricts itself to games whose position is public to both players, and in which the set of available moves is also public. CGT principles can be applied to games like chess, checkers, Go, Hex, and Connect6 but these games are mostly too complicated to allow complete analysis (although the theory has had some recent successes in analyzing Go endgames).
Applying CGT to a ''position'' attempts to determine the optimum sequence of moves for both players until the game ends, and by doing so discover the optimum move in any position. In practice, this process is tortuously difficult unless the game is very simple.
CGT should not be confused with another mathematical theory, traditionally called game theory, used in the theory of economic competition and cooperation. Game theory includes games of chance, games of imperfect knowledge and games in which players move simultaneously, and they tend to represent real-life decision making situations.

Contents

History

Examples

Overview

Formal definitions

Well-founded collections of games

Nimbers

See also

External links

References

History

CGT arose in relation to the theory of impartial games, in which any play available to one player must be available to the other as well. One very important such game is nim, which can be solved completely. Nim is an impartial game for two players, and subject to the ''normal play condition'', which means that a player who cannot move loses. In the 1930s, the Sprague-Grundy theorem showed that all impartial games are equivalent to heaps in nim, thus showing that major unifications are possible in games considered at a combinatorial level (in which detailed strategies matter, not just pay-offs).
In the 1960s, Elwyn R. Berlekamp, John H. Conway and Richard K. Guy jointly introduced the theory of a partisan game, in which the requirement that a play available to one player be available to both is relaxed. Their results were published in their book ''Winning Ways for your Mathematical Plays'' in 1982. However, the first book published on the subject was Conway's ''On Numbers and Games'', also known as ONAG, which introduced the concept of surreal numbers and the generalization to games. ''On Numbers and Games'' was also a fruit of the collaboration between Berlekamp, Conway, and Guy.
John Conway states in ONAG that the inspiration for the theory of partizan games was based on his observation of the play in go endgames.

Examples

The introductory text ''Winning Ways'' introduced a large number of games, but the following were used as motivating examples for the introductory theory:

★ Blue-Red Hackenbush - At the finite level, this partisan combinatorial game allows constructions of games whose values are dyadic rational numbers. At the infinite level, it allows one to construct all real values, as well as many infinite ones which fall within the class of surreal numbers.

★ Blue-Red-Green Hackenbush - Allows for additional game values that are not numbers in the traditional sense, for example, star.

★ Domineering - 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. This allows discussion of a game's temperature.

★ Nim - An impartial game. This allows for the construction of the nimbers. (It can also be seen as a green-only special case of Blue-Red-Green Hackenbush.)
The classic game Go was influential on the early combinatorial game theory, and Berlekamp and Wolfe subsequently developed an endgame and ''temperature'' theory for it (see references). Armed with this they were able to construct plausible Go endgame positions from which they could give expert Go players a choice of sides and then defeat them either way.

Overview

A game, in its simplest terms, is a list of possible "moves" that two players, called ''left'' and ''right'', can make. The game position resulting from any move can be considered to be another game. This idea of viewing games in terms of their possible moves to other games leads to a recursive mathematical definition of games that is standard in combinatorial game theory. In this definition, each game has the notation '{L|R}'. $L$ is the set of game positions that the left player can move to, and $R$ is the set of game positions that the right player can move to; each position in L and R is defined as a game using the same notation.
Use tic-tac-toe as an example, label each of the nine boxes of the standard Tic-Tac-Toe board by ''UL'' for ''Upper Left'', ''CC'' for ''Center Center'', and ''LR'' for ''Lower Right'' (and so on), and suppose that each box may contain an X or O symbol. We use e.g. XUL to stand for the game position in which an X has been placed in the upper left box. Then, the initial position can be described in combinatorial game theory notation as
{| align=center
|$\{XUL,XUC,XUR,XCL,XCC,XCR,dots|OUL,OUC,OUR,OCL,OCC,OCR,dots\}$
|}
Note that, in standard Tic-Tac-Toe play, the players alternate turns, but this alternation is handled implicitly by the definitions of combinatorial game theory rather than being encoded within the game states. The Tic-Tac-Toe game labeled ''XUL'' above could in turn be described by the following notation
{| align=center
|$XUL\; =\; \{XUL\_XUC,XUL\_XUR,\; XUL\_XCL,dots|XUL\_OUC,dots\}$
|}

Moving on down the chain, eventually the game might come to this state (a very strange game indeed, but still valid):
{| align=center
|$XUL\_OUR\_XCC\_OCR\_XLC\_OLL\_XCL\_OUC\; =\; \{\; \{|\}\; |\; \{|\}\; \}$
|}
The above game describes a scenario in which there is only one move left for either player, which is the Lower Right corner, and if either player makes that move, that player wins. The {|} in each player's move list is called the zero game, and can actually be abbreviated 0. In the zero game, neither player has any valid moves; thus, whoever's turn it is when the zero game comes up automatically loses.
Additionally, the game which is labeled the rather complex "XUL_OUR_XCC_OCR_XLC_OLL_XCL_OUC" above also has a much simpler notation, and is called the star game, which can also be abbreviated
★ . In the star game, the only valid move leads to the zero game, which means that whoever's turn comes up during the star game automatically wins.
An additional type of game, not found in Tic-Tac-Toe, is a ''loopy'' game, in which a valid move of either ''left'' or ''right'' is a game which can then lead back to the first game. A game that does not possess such moves is called ''nonloopy''.

Formal definitions

A structure $langlemathcal\{C\},L,R$
angle is called a ''collection of games'' if
:$L:mathcal\{C\}$
ightarrow 2^mathcal{C}
and
:$R:mathcal\{C\}$
ightarrow 2^mathcal{C}
where $2^mathcal\{C\}$ is the power set of $mathcal\{C\}$,
and
:
Because $G$ is uniquely determined by $L(G)$ and $R(G)$, $G$ is often denoted $\{L(G),|,R(G)\}$.
The elements of $mathcal\{C\}$ are called ''games'' and by convention they are denoted by the upper case Latin letters $G,H,K,...$. A game represents a contest between two players conventionally named 'Left' and 'Right' (sometimes known as 'bLue' and 'Red'), and $Hin\; L(G)$ (respectively $Hin\; R(G)$) means that player 'Left' (respectively 'Right') is allowed to move from game $G$ to game $H$.
Define the binary relation, $mathrm\{S\},$ (for successor) between games $G,\; Hin\; mathcal\{C\}$ by
:$Gmathrm\{S\}H;$ if and only if $Hin\; L(G)cup\; R(G)$.
The transitive closure of $mathrm\{S\},$ is denoted $mathrm\{P\},$, for position. We say $H$ is a ''position'' of $G$, denoted $Gmathrm\{P\}H,$, when it is possible to get from $G$ to $H$ via a nonempty sequence of moves by 'Left' and 'Right', not necessarily alternating players. $mathcal\{C\}$ is called ''loopy'' if $exists\; Ginmathcal\{C\};Gmathrm\{P\}G$; otherwise $mathcal\{C\}$ is ''nonloopy''. A non-loopy collection $mathcal\{C\}$ is ''well-founded'' when there is no infinite sequence $G\_0,\; G\_1,\; G\_2,\; ...,$ with .
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 $langlemathcal\{C\},L,R$
angle is a collection of games and $G\_0inmathcal\{C\}$ then the game $G\_0$ can be 'played' as follows. The first player, say 'Left', chooses an element $G\_1in\; L(G\_0)$ (if one exists). Then 'Right' chooses an element $G\_2in\; R(G\_1)$ (if one exists). Then 'Left' chooses an element $G\_3in\; L(G\_2)$ and so on. If a player cannot move (i.e. the relevant $L(G\_i),$ or $R(G\_i),$ set is empty) then, by definition, that player loses the game. The game $G\_0$ can similarly be played with 'Right' as the first player by exchanging the roles of $L(G\_i),$ and $R(G\_i),$.

Well-founded collections of games

If $mathcal\{C\}$ is well-founded, then it contains a zero element.
Let $mathcal\{C\}\_\{fin\}$ be the smallest well-founded collection of games containing 0 and such that
:For all well-founded collections $mathcal\{L\},mathcal\{R\}subsetmathcal\{C\}\_\{fin\}$, there exists $Kinmathcal\{C\}\_\{fin\}$ such that $L(K)=mathcal\{L\},R(K)=mathcal\{R\}$.
Then all well-founded collections of 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\}\; imesmathcal\{C\}\_\{fin\}$
ightarrowmathcal{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'' (also called the ''disjunctive sum'' of the games) is well-defined for well-founded games 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": Each player in turn may make a move in either $G$ or $H$, but not both. The analysis of this operator is motivated by games such as Go, Sprouts, and Domineering, which split into parts that are independent except in that a player may move in only one part per turn.
The ''negative'' of a game is defined recursively as follows:
:.
This definition is similarly well-defined. Intuitively, $-G$ is just "G with 'Left' and 'Right' reversed".
Define a set of games $P\_Lsubsetmathcal\{C\}\_\{fin\}$ recursively as follows:
:$Gin\; P\_L$ if and only if
otin P_L.
A player loses precisely when they run out of moves. The above definition characterizes games such that with 'Left' to move, no matter what 'Left' does, 'Right' can respond so that 'Left' will 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\; :\; Gin\; 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 . This observation motivates the following:
Define a relation $simeq$ by $Gsimeq\; H$ if and only if $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, at every position of the game, the same moves are available to both players. For instance, Nim is impartial, as any set of objects that can be removed by one player can be removed by the other. However, tic-tac-toe is not impartial, because a move by one player leaves a different position than a move to the same square by the other player. For any ordinal number, one can define an impartial game generalizing Nim in which, on each move, either player may replace the number with any smaller ordinal number; the games defined in this way are known as nimbers. The ''Sprague-Grundy theorem'' states that every impartial game is $simeq$-equivalent to a nimber.

See also

★ Surreal number

★ Zero game

★ Fuzzy game

★ star (game)

★ Game complexity

★ Connect6

★ Go (board game)

★ Chess

External links

★ List of combinatorial game theory links at the homepage of David Eppstein

★ An Introduction to Conway's games and numbers by Dierk Schleicher and Michael Stoll

★ Combinational Game Theory terms summary by Bill Spight

★ Combinatorial Game Theory Workshop, Banff International Research Station, June 1995

References

★ On Numbers And Games, John Horton Conway, , , Academic Press, 1976, ISBN 0-12-186350-6

★
★ On Numbers And Games (2nd ed.), ---, , , A K Peters Ltd, 2001, ISBN 1-56881-127-6

★ Winning Ways for your Mathematical Plays, E. Berlekamp, J. H. Conway, R. Guy, , , Academic Press, 1982, ISBN 0-12-091101-9, ISBN 0-12-091102-7

★
★ Winning Ways for your Mathematical Plays (2nd ed.), ---, , , A K Peters Ltd, 2001--2004, ISBN 1-56881-130-6, ISBN 1-56881-142-X, ISBN 1-56881-143-8, ISBN 1-56881-144-6

★ Mathematical Go: Chilling Gets the Last Point, Elwyn Berlekamp & David Wolfe, , , A K Peters Ltd, 1997, ISBN 1-56881-032-6

★ Luck, Logic and White Lies: The Mathematics of Games, Jorg Bewersdorff, , , A K Peters Ltd, 2004, ISBN 1-56881-210-8, §§ 21-26