Combinatorial Game Theory
Combinatorial Game Theory (CGT) is the mathematical study of well-defined games for two players moving alternately with complete information and no element of chance and which are bound to terminate in a finite number of moves; normally the first player unable to move is considered to have lost.^{[1]}
Table of contents |
History
The first book on Combinatorial Game Theory was Donald Knuth's idiosyncratic 1974 (still in print in 2010) mathematical novelette, Surreal Numbers. The first full formal treatment is On Numbers and Games, by John Conway. It was first published in 1976 and has recently been republished. The book Winning Ways (for your Mathematical Plays) (1982, 2003) by Elwyn Berlekamp, John Conway and Richard Guy describes CGT and its applications to a plethora of specific games but says little about go.
Approach
CGT was in part inspired by Go, since many Go end positions (yose) are combinations of independent regions of play. Therefore CGT comes in naturally from the consideration of play on sub-boards. Each such position is a combinatorial game, which can be added to or subtracted from other such games. This is the idea that Go can be played on several boards at once, with alternating play still in operation: each player is able to play just one stone per turn, on one or other board.
For go in practice, the methods of CGT are usually only applied to the yose. Since go is a hot game, chilling is applied to make it more tractable.
CGT analysis has also been applied with some success to considerations of life and death and eyes. There is more on this topic in the SL page on half-eyes - see the references on that page to works by Howard Landman and by Martin Mueller.
Numbers and games
Numbers are special cases of combinatorial games: Go players can take that as meaning that some positions are already secure territory.
- Bill Spight: In Mathematical Go, Berlekamp and Wolfe show how to apply the concept of number to go positions that still have some play left (hot positions). See Chilling.
By convention, the players are Left (Black) and Right (White). Left's scores are positive, Right's scores are negative; we are playing a zero-sum game with a convention that plus scores are good for Left. Either player, however, may be the one to start in a game, and the notation reflects that (no convention that Black starts, therefore).
A game may be represented in slash notation^{[2]}:
- `` { A, B, C, cdots | D, E, F, cdots } ``
To the left of the central vertical bar are the games to which Left (Black) can move, called options or followers. To the right are those to which Right (White) can move.
For example
- `` { 1 | -1} ``
represents a one-point gote play. (Remember that scores are games because numbers are games.) Sometimes it is written +/- 1.
For the formal definition of "game" and some discussion, see abstract game.
In CGT the number 1 means that Left can make a play, but Right cannot (or the equivalent). Go scoring does not obviously translate to CGT numbers, but you can do it. See Mathematical Go by Wolfe and Berlekamp. Interestingly, the form of Go scoring that most straightforwardly translates to CGT numbers is territory scoring with a group tax. See Ancient Chinese Rules and Philosophy.
Anyway, 1 + (-1) = 0: the introduction of addition and equality of games is compatible with the old meanings of '+' and '='. Black can make a play, and then White can make a play, or vice versa. One way to write that game is
- `` { -1 | 1 } ``
Other pages on Combinatorial Game Theory
Most of the material originally here has been redistributed:
- zero in CGT terms.
- Minimax
- /Discussion
- canonical form.
- introduction to infinitesimals.
- thermography.
Original page by Bill Spight; subsequent edits by Charles Matthews.
See also
- CGT path
- Tom's technical introduction to CGT
- Non-technical introduction to CGT?
- A more up-to-date advanced mathematical text on Combinatorial Game Theory is Combinatorial Game Theory by Aaron Siegel, American Mathematical Society, 2013.
[1] This is a summary of the conditions specified in the Extras to Winning Ways, Chapter 1. These conditions may sometimes be relaxed.
[2] See tree representation for Charles Matthews' take on this.