General graph go

This formulation of these rules is due to Mark Wainwright with some editing by myself. We describe three versions, with commentary by Mark in italics.

Rules of "General Graph Go"

Here are the rules of General Graph Go (GGG). They encapsulate the rules of go as they might be formulated by a mathematician. (Me, for instance.)

It can be seen that, as we all know, there are only two rules of play (rules 2 and 3); the other three rules are needed to set up the necessary context and determine a winner. The superko rule is used, as one might expect.

The rules allow self-capture. They could easily be modified to forbid it, but it is slightly conciser to allow it. As they stand, they force the players to remove all dead groups and, of course, this is a defect that would take somewhat more space to correct.

One practical reason to forbid self-capture might be that now not only will superko force termination, but the termination will now happen in reasonable time. But practical considerations were never of much interest to mathematicians, so stet.

General Graph Go with Scoring

0. Go is played by two players (`Black' and `White') on a coloured graph (V, E, f), consisting of a vertex set V, a set of edges (unordered pairs of vertices) E, and a 3-colouring of V, that is, a function f from V to the set of three colours {black, white, null}. Null-coloured vertices are called `empty'.

1. A relation ~ is defined on V as follows : u~v if u and v have the same colour, and {u,v} is in E (there is an edge from u to v). The reflexive transitive closure of this relation is an equivalence relation, the equivalence classes being called groups. An empty vertex adjacent to a black or white group is called a liberty of the group.
(The notion of reflexive transitive closure (smallest reflexive transitive relation containing ~) obviates the need for the longer definition of `chain'.)

2. Black and White play alternately, Black starting. A move for a player consists of colouring an empty vertex with his own colour, then removing (null-colouring) all his opponent's groups with no liberties, and then removing all his own groups with no liberties. On a player's turn, he may either make a move or say `pass' or `resign'.

3. A player may not make a move which gives a position (colouring of V) that has occurred earlier in the game.

4. The game ends after two consecutive passes or one resignation. A player's score at the end of the game is the number of vertices of his own colour, plus the number of empty vertices in groups with no neighbour of his opponent's colour. The player with the greater score wins, unless one player resigned, in which case the resigning player loses.

Notes: the most common starting position is a 19x19 orthogonal grid of points with edges between nearest neighbours, and all points initially empty. Smaller orthogonal square boards are also common. Handicaps can be given by using an initial position where some points are coloured black, and possibly giving first move to White. Ancient Chinese games used a starting position with both black and white points in the starting position. Komi of n can be effectively given by changing the winning condition, or (if n > 2) by giving (V,E,f) two components, one a path of length n where the endpoints are empty and the other points white. It is usual for V to be finite.

Conway Go without replacement

1. A relation ~ subset of VxV is defined as follows : u~v if f(u)=f(v), and {u,v} is in E (there is an edge from u to v). The reflexive transitive closure in VxV of this relation is an equivalence relation, the equivalence classes being called groups. An empty vertex adjacent to a black or white group is called a liberty of the group.
(The notion of reflexive transitive closure (smallest reflexive transitive relation containing ~) obviates the need for the longer definition of `chain'.)

3. A player may not make a move which gives a position (colouring of V) that has occurred earlier in the game.

4. The game ends when one player is unable to make a move, or one player resigns. The player unable to make a move, or who resigned loses.

These rules work, but the game that results is not that similar to go in the treatment of territory:

Consider this position on a 5x5 board:

. . . . .
X X X X X
O X X X X
O O O O O
. O . O .

A clear win for Black, you might think, under normal rules, whether area- or territory-based. Unfortunately, you can see that under `Conway Go without replacement' rules, White cheerfully wins this game, whether it is White or Black to move next. (White just plays in the middle of Black's territory for as long as he can.) Nor is this a special property of strange endings. They key to this kind of Conway go is that you don't want your opponent to be able to make blobby groups in your territory, otherwise she can get nearly as many moves out of it as you can. So you make your territory in long thin strips and try to carve it up as much as you can; large moyos are pretty worthless. So this game, though it has interesting features, is quite different from go.

In light of this, we also define:

Conway Go with Replacement

0. Go is played by two players (`Black' and `White') on a coloured graph (V, E, f) and non-negative integers P, Q (prisoners). The coloured graph consists of a vertex set V, a set of edges (unordered pairs of vertices) E, and a 3-colouring of V, that is, a function f from V to the set of three colours {black, white, null}. Null-coloured vertices are called `empty'.

2. Black and White play alternately, Black starting. A move for a player consists of colouring an empty vertex with his own colour, then removing (null-colouring) all his opponent's groups with no liberties, and then removing all his own groups with no liberties. If a black or white group consisting of n vertices is removed, add n to the value in Q or P respectively.

A pass for a player consists of saying `pass' and reducing by one the value in P or Q, if the player is Black or White respectively. If the value is zero, then the player is not allowed to pass.

On a player's turn, she makes a move, or passes (if allowed to), or says `resign'.

3. A player may not make a move which gives a position (colouring of V) that has occurred earlier in the game.
Note that passing does not contitute a move.

4. The game ends when one player is unable to make a move, or one player resigns. The player unable to make a move, or who resigned loses.

This solves the problems with `Conway Go without Replacement' by allowing passes, `replacing' prisoners in the opponent's bowl:

The key to making this game go-like is to say that captured stones do not disappear in puffs of smoke, but are retained by the capturing player. Either player can, instead of a move, take a previously captured stone and eat it. (Or "return it to the opponent's bowl" as one might say, or even "pass it back to the opponent" making a nice pun on "pass" which the AGA rules use a slightly different form of.) All those extra moves your opponent got inside your territory now avail her nothing, because each one will give you an extra prisoner which you will be able to use later as a free pass. The resulting game is go as we know it (up to the usual caveats of idiosyncratic life-and-death behaviour in pathological positions, and off-by-one errors in the score).

For my purposes - showing that some version of general graph go is equivalent to the specialisation of topological go I'm using `Conway Go without Replacement'. Topological go in general doesn't have a way to count the number of stones captured by a move, so the concept of prisoners is a shaky one. One would sometimes come out with more than one possible answer for how many stones were captured, or even infinitely many stones captured, since the board position is really about points in the space rather than the sets of them making up stones. Perhaps something to do with putting a measure space structure on the go-space would allow for ways to define both territory and 'number' of prisoners captured.