Combinatorial Game Theory

Keywords: 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

Approach

Numbers and games

Other pages on Combinatorial Game Theory

See also

[edit]

History

The first book on Combinatorial Game Theory was Donald Knuth's idiosyncratic 1974 mathematical novelette, Surreal Numbers, which was still [ext] in print in 2023. The first full formal treatment is On Numbers and Games, by John Conway. It was first published in 1976 and was republished in a second edition in 2001. 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.

[edit]

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.

[edit]

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 } ``

[edit]

Other pages on Combinatorial Game Theory

Most of the material originally here has been redistributed:

Introduction to Combinatorial Game Theory

Original page by Bill Spight; subsequent edits by Charles Matthews.

[edit]