Combinatorial Game Theory (version 10)

    ***** UNDER CONSTRUCTION *****

I'll do this right, later. But this seemed like a good place to reply to Jan, now. --BillSpight

Combinatorial Game Theory was developed by John Conway in the 1970s in On Numbers and Games, recently republished. It was in part inspired by go, since many go end positions are combinations of independent regions of play. Each such position is a combinatorial game, which can be added to or subtracted from other such games. Numbers are special cases of combinatorial games.

By convention, the players are Left (Black) and Right (White). Left scores are positive, White scores are negative. A game may be represented in slash notation:

                   {A, B, C, ... | D, E, F, ...}

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.

                   {1 | -1}

represents a 1 point gote. (Remember that scores are games because numbers are games.) Sometimes it is written +/- 1.

JanDeWit: I took a look at "On Numbers And Games" by Conway in the local university bookstore today, so now I understand why 1 + (-1) = 0. You beat me to starting this page, Bill!

I'll adopt the convention of prefixing 'CGT' to any page on Combinatorial Game Theory not directly relating to Go, so my this is the list of references I've built up so far.

Bill: Jan, I see I misread your + - on the Half Eye page, thinking you intended plus or minus. Thanks for the parentheses. :-)

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 most straightforward form of go scoring that translates to CGT numbers is territory scoring with a group tax. See the Ancient Chinese Rules and Philosophy page.

Anyway, 1 + (-1) = 0. Black can make a play, and then White can make a play, or vice versa. One way to write that is

                   { -1 | 1 }

Here is a 0 in go:

OTF: Zero (Seki)  

One way to write it is

                   { 6 | -10 || 8 | -8 }

If Black plays first White can reply and get 10 points (White scores are negative); if White plays first Black can reply and get 8 points. Neither player can afford to play.

Here is another 0:

OTF: Zero (Miai)  

We can write it

                   { 2 | 0 || 0 | -2 }

JanDeWit: You're confusing numbers and minimax outcomes :-) Writing a computer program to do this kind of stuff "really" helps in understanding. So far I can write:

     i2g = intToGame -- converts integers to games
     g1 = (i2g 6) ! (i2g (-10))
     g2 = (i2g 8) ! (i2g (-8))
     g3 = g1 ! g2

'value g1' gives "First player to go wins(fuzzy)" as does 'value g2', however 'value g3' returns "Second player to go wins(=0)". Not bad for 130 lines of code, eh? Those 130 lines also incorporate a basic mechanism for playing games interactively...

Bill, if you could shed some light on how to convert games to canonical form and some more standard terminology? That really would help me to bridge the gap from my self-taught understanding to knowing what all those research papers are about... I know * = Dame = {0|0}, but what does up = {0|*} mean in terms of Go? What is the 'tiny' operator?