The rules of Go for mathematicians · Pablo Parguiña's Website

A lot of people in the West are first exposed to Go with the Japanese ruleset. However, it’s a bit of a mess, with several patches, and worse, some books seem to try to hide the complexity. Go is a complex game as-is, but the rules don’t need to be, the complexity is an emergent property that makes it fun. If you are comfortable with first year undergrad math and want to know a well-defined set of rules, keep reading. We will be discussing the Tromp-Taylor ruleset, which is perhaps the most elegant and short of them all. But don’t worry, Go with Tromp-Taylor is Go, and in practice any ruleset yields the same result in almost every case. This is not a fringe thing to learn, it’s just the simplest.

Disclaimer: strictly speaking, the following rules are a generalization of Tromp-Taylor rules to $N$ players and arbitrary finite, undirected graphs. However, I’m otherwise deviating from those rules as little as possible. I think part of the beauty of this game can only be appreciated if you see it generalized.

Go IRL

It’s a two-player board game played by turns with black and white stones. The most common and important board size is 19x19. The goal is (roughly) to enclose more territory than the other player, and on each turn the player may put a stone at any place on the board, provided that the spot is not already occupied by another stone (with some other restrictions we’ll get to later). Players may not move stones unless they need to be removed (because they are dead).

In this post we’ll be making heavy use of a 9x9 board for the examples, but in the end we’ll see other, more interesting graphs.

Math definitions

Board, game, points

Go is played on a finite, undirected graph

G = (V, E)

where $V$ is the set of vertices/nodes and $E$ is the set of edges between them.

Nodes on the graph can be colored/labeled. For $N$ players, let the set of colors be:

\mathcal C = \{\mathsf 0, c_1, \ldots, c_N\}

For the special case of two players I shall use:

\mathcal C = \{\mathsf 0, \mathsf{B}, \mathsf{W}\}

(\text {I will also call them Empty, Black, and White; and I'll use lowercase } c \text{ for a specific color)}

A coloring of the board is a function:¹

\lambda: V \to \mathcal C

A point is just a vertex $v \in V$ and its color is $\lambda(v)$ .

A stone is a non-empty point. We’ll say things like “placing a stone at point P” as a shorthand of “coloring an empty point $P$ as $\lambda(P) = c \neq \mathsf 0$ ”

Since the graph doesn’t change during the game, we can say that a game played for $n$ turns is a sequence of colorings:

(\lambda_i)=\lambda_0, ..., \lambda_n

(where $\lambda_0$ is the coloring before any player has done anything)

One immediate consequence of the above in typical go boards is that stones placed diagonally from each other are not adjacent:

A

Reaching

A point $P_0$ with color $c_0$ is said to reach color $c_1 \neq c_0$ if and only if there exists a path of points of color $c_0$ that ends adjacent to a point of color $c_1$ . That is, $P_0$ reaches $c_1$ if and only if:

\exists \text{ a path } (P_0, \ldots, P_m), \exists Q \in V

such that:

\lambda(P_i)=c_0 \: (i=0,\ldots,m),\quad \lambda(Q)= c_1, \quad \left\{P_m,Q\right\} \in E

(The last bit means that $P_m$ and $Q$ are adjacent because there exists an edge between them. Note also that $m=0$ is fine, it just means that $P_0$ is directly adjacent).

When $Q$ is Empty and $P_m$ is non-empty, $Q$ is called a liberty of the connected component containing $P_m$ .

In the example below we consider several cases at once.

A

Clearing

We are now interested in stones/points that don’t reach Empty. When we describe the actual game loop we’ll see that such stones are dead.²

Example 3 The black stone/point doesn’t reach Empty and is therefore dead.

Example 4 None of the white stones reach Empty, they are also dead.

Hopefully you can see that white points like the above form a cluster such that if one of the points reaches Empty, all of them do.

Proof

Let $G_c \subseteq G$ be the subgraph of points colored $c$ , and let $S \subseteq G_c$ be a connected component of $G_c$ (i.e., a subgraph of $G_c$ where for every two points there exists a path from one to the other and the subgraph cannot be enlarged without breaking the connectedness).

Proposition: If $B \in S$ reaches Empty, $A$ reaches Empty $\forall A \in S$ .

Proof: Since $B$ reaches Empty, there exists a path $BC = (B, \ldots, C) \subseteq G_c$ from $B$ to some point $C$ adjacent to an empty point $D$ of the full graph $G$ . Since $S$ is a connected component of $G_c$ , we also have that $C \in S$ . That means that, for every $A \in S$ , there exists a path $AC \subseteq G_c$ that ends at $C$ , which is adjacent to $D$ . Therefore $A$ reaches Empty. $\square$

Example 5 This white cluster is alive for now (one of its points is adjacent to an empty point, so they all reach Empty), but it’s easy to see that it’s going to die if white doesn’t do something about it.

Clearing a color $c$ means finding all the points of that color that don’t reach Empty and setting their color to Empty. In example 4 this would correspond to removing the dead white stones.

Note that clearing Empty is allowed by this definition but doing so doesn’t change anything.

Moves

A move is performed by a player, and it consists of 3 steps:

Setting the color of an empty point as the color of that player. (In real life, this corresponds to placing a stone of the color of that player).
Clearing the color of each opponent (simultaneously).
Clearing one’s own color.

This is better seen with an example.

Example 6 At first, there are 7 white stones. White puts an 8th, which doesn’t produce any clearing. Then, black places a stone and clears two groups of white stones (the 7 stones marked □ and the single stone marked △). After that, no clearing of black is necessary, even if for an instant it looks like the black stone doesn’t reach Empty.

The example above shows that the order of clearing is important: you can place the black stone on a point where it wouldn’t reach Empty and it doesn’t die, because it’s clearing the white stones first. After the clearing, the black stone does reach Empty, so it doesn’t get cleared in step 3.

In truth, it’s impossible to clear both some enemy stones and your own on the same move. But before that, note that, after a move:

Exactly one empty point changes color (the one where the stone was placed), unless it got cleared in step 3.
Non-empty points might change to empty through clearing.

Proof

We assume, without loss of generality, that it’s Black’s turn.

Notation. Let:

$\lambda$ be the coloring at the beginning of a black turn.
$\mu$ be the coloring after placing the black stone at $P$ .
$\nu$ be the coloring after clearing all opponent colors, but before clearing Black.
$\lambda_{\mathrm{final}}$ be the coloring at the end of the turn.
By “cluster” we’ll mean a connected component $A$ where all points are of the same non-empty color.
The set of liberties of a cluster $A$ under the coloring $\varphi$ is $L_{\varphi}(A)$ . Since every non-empty point $X$ belongs to a unique cluster under a coloring $\varphi$ , and liberties are defined only for clusters, we may also write $L_{\varphi}(X)$ as a shorthand for $L_{\varphi}(A)$ .
Interpret $\lambda(A)$ as $\lambda(X)$ for some $X \in A$ . Since $A$ is a cluster, all points in it have the same color.

Proposition:

Assume that every cluster reaches Empty before black plays.

Let $P\in V$ be the empty point where black plays, meaning:

\lambda(P)=\mathsf 0, \quad \mu(P) = \mathsf B, \quad \mu(X)=\lambda(X)\quad \forall X\neq P

(i.e., $P$ starts empty, becomes black, and no other point becomes black).

We are going to prove that if there exists some set of points $S \subset V$ forming an opponent cluster under $\lambda$ that gets cleared after the move, that is:

\exists S \mid \lambda(S) = c \: \text{ and } \: \lambda_{\mathrm{final}}(Y) = \mathsf 0 \quad \forall Y \in S

Then, the newly placed stone doesn’t get cleared:

\lambda_{\mathrm{final}}(P)=\mathsf B \tag {1}

and no pre-existing black cluster is cleared either, i.e.:

\lambda(X)=\mathsf B \implies \lambda_{\mathrm{final}}(X)=\mathsf B \tag {2}

Proof:

Step 1 ( $\lambda \to \mu$ ): Placing a stone at $P$ .

As already stated, $\mu(P)=\mathsf B$ , nothing else changes color.

Step 2 ( $\mu \to \nu$ ): Clearing opponents.

Black points don’t change, so in particular $\nu(P)=\mathsf B$ .

Let $S$ be an opponent cluster cleared after Black plays at $P$ . Then

L_\lambda(S)\neq\varnothing, \quad L_\mu(S)=\varnothing

and the only point that changed color between $\lambda$ and $\mu$ was $P$ , therefore, $P$ was the only remaining liberty, i.e.:

L_\lambda(S)=\{P\}

So there exists some $Q\in S$ adjacent to $P$ , that is, $\{Q,P\}\in E$ .

Since $S$ is cleared when passing from $\mu$ to $\nu$ , in particular, $Q$ is cleared: $\nu(Q)=\mathsf 0$ .

Step 3 ( $\nu \to \lambda_{\mathrm{final}}$ ): Clearing black.

Since $\nu(Q)=\mathsf 0$ and $P$ and $Q$ are adjacent, $P$ has a liberty under $\nu$ , i.e $Q \in L_\nu(P)$ .

Therefore the black component containing $P$ reaches Empty and is not cleared:

\lambda_{\mathrm{final}}(P)=\mathsf B

This proves $(1)$ .

Now let $H$ be any black connected component under $\nu$ .

If $P\in H$ , then, $L_\nu(P)=L_\nu(H)\neq\varnothing$ . It reaches Empty and therefore doesn’t get cleared.
If $P\notin H$ , then $H$ consists only of black stones that were already present before the move. That means that it reached Empty under $\lambda$ through an empty point $R$ different from $P$ (if $P$ were a liberty of $H$ under $\lambda$ , $P$ would be in $H$ after Step 1). Since $R \neq P$ , $\lambda(R)=\mu(R)=\nu(R)=\mathsf 0$ . $H$ reaches empty under all those colorings and therefore doesn’t get cleared.

That proves (2). $\square$

Note that we add the third step because placing a stone where it would die is allowed under Tromp-Taylor rules (not so in other rulesets, where such “suicide” is forbidden).

Territory and score

The territory of color $c \neq \mathsf 0$ is the set of empty points that only reach $c$ :

T_c(\lambda) = \left\{P \in V \mid \lambda(P)=\mathsf 0, \: P \text{ reaches only } c \right\}

The score of a player color $c$ is the number of points of their color plus the territory of that color. In mathspeak:

V_c(\lambda) = \left\{P \in V \mid \lambda(P)=c \right\}

\operatorname{score}(\lambda; c) = |V_c(\lambda)| + |T_c(\lambda)| + K(c)

The term $K(c)$ is komi, an adjustment for the fact that Black moves first and is expected to finish with a higher score. For the general $N$ -player game, each player would receive a different $K(c)$ .

K(\mathsf B)=K(\mathsf W)=0

As you can see, a player’s score is just a function of the coloring. Here are some examples of things that don’t matter for scoring in this way:

Whose turn it is.
Previous states.
Future states, including, for example, which points are likely to stop reaching empty.

The last bit requires some further comments. Take the board from the previous example. The black stones on the top-left corner are about to die, they are one move away from not reaching empty. This doesn’t matter for the score as defined above. Of course, this also suggests that the current score can be quite misleading for unfinished games. We’ll get back to that later.

Rules of the game

I will assume there is no handicap for now.

Rules:

Assign players to colors. The colors have a fixed turn order $c_1,\ldots,c_N$ . In ordinary two-player Go, these are Black then White.
The game starts with all points colored empty.³
During their turn, the player can either move (place a stone) or pass.
A player may move in any empty point, provided that the resulting coloring after the move wasn’t already seen in the game (i.e., if a player moved in turn $i$ , $\lambda_i = \lambda_j, \: j < i$ is illegal).
The game ends after $N$ consecutive passes, where $N$ is the number of players.
The winner of the game is the one with the highest score (ties are allowed).

As you can see, we can’t fully describe the game state with just the current coloring and knowing whose turn it is. We also need to know the previous colorings to check the legality of moves. That rule is called Positional Super-Ko (PSK), and it is necessary to avoid infinite loops.⁴ Repeated colorings are fine if they come from a player passing, of course.

More on komi

The specific amount of komi is always debated. In principle, it should be set to whatever amount makes it equally likely that black or white win when the color each player gets is decided at random. That means that the 6.5 komi is contextual, and different graphs should get different komi. Presumably, with 3+ players, komi should increase the longer it takes for the player of color $c$ to make the first move, starting from 0 for black.

In one server I could find that allows for 3+ players, there seems to be no komi (for whatever reason). These servers don’t seem to have too many players, though, so things could change with more experience.

Handicap

The traditional Japanese handicap system lets the weaker player play black and have some stones pre-placed for them. Then, white makes the first real move. The idea behind it seems to be to teach the weaker player how to play Go by giving them a good initial placement regardless of how they feel like.

That rather opinionated system generalizes poorly, of course, and other systems give the weaker player free placement of the stones, like in China. It’s the Tromp-Taylor proposal as well, and I think it’s fine. You should still try to fine-tune it to make it so that every player has an equal probability of winning though, and I feel like even if you do so correctly, this method will have more variance than the Japanese version. Which might be a feature, not a bug, I’m unsure.

Another obvious option is to simply give komi to the weaker players, of course. Why have two systems when you could just use one? It’s interesting that the Tromp-Taylor approach is so minimalistic in general, yet it doesn’t reuse komi for this.

Can a system of pre-placed stones be defined for arbitrary graphs and players? I doubt it, but it’s an interesting thing to try to define, even if it ends up being reasonable only for some families of graphs.

Comments and some potential questions

Can I surrender?

In practical implementations, of course it’s allowed and it’s very common. In theory, however, under Tromp-Taylor you can only pass and you are forced to watch the game until the end of time or until you decide not to pass again, for some reason.

Can groups of stones that don’t reach Empty be on the board despite being dead?

Before the first move, no, because all the points are empty, so there are no stones.

After a move finishes, again no, for two reasons:

A move clears all player colors.
Clearing colors expands the number of empty points, so the number of points that reach Empty can only go up or stay the same. It can’t happen that, after clearing, some stones are suddenly dead that weren’t so before.

I think I might add an induction proof as an edit at some point.

Is the game guaranteed to stop?

Yes. Remember that we required finite graphs. A graph with $|V|$ vertices and $|\mathcal C|$ colors has $|\mathcal C|^{|V|}$ possible colorings. That finite number is actually way bigger than the actual number of possible configurations in Go, since many of those colorings are illegal or impossible to produce in a game. Furthermore, PSK makes the set of unseen colorings shrink with every non-pass move. At some point, there are no more legal moves (worst case, because all the colorings have been seen) and players are forced to pass. When all players pass, the game ends.

Of course, all players will pass way before they run out of legal moves (remember that suicide is legal, so if they had to play every possible legal move they’d need to start committing suicide at some point! That doesn’t sound fun at all).

That brings us to the important point of early stopping of games, but first we need to talk about another life or death matter.

Life and death

A consequence of the rules of Go that is not obvious to anybody on a first reading of the rules is that some clusters (also called “groups”) of stones are impossible to capture. Sometimes the unkillable “cluster” is not even one cluster but two or more! Consider this situation:

Example 8 It looks like white can capture (kill) those black stones, the only thing required is to fill the two points marked △. But how? If you place a white stone on one of those places, both of the black groups still reach Empty, but your stone doesn’t! This is suicide, which is allowed under Tromp-Taylor rules (not so in other common rulesets), but in this case it’s not even legal because the coloring would be exactly the same as before. As White, there is absolutely nothing you can do about this “group” of black stones, and they are said to be alive unconditionally.

Early stopping of games

As we explained, playing out the games until there are no more possible moves is not just tiresome and pointless but undesirable, since it’d force players to make suicidal moves. Much like in chess, people often surrender earlier. In Go, it’s actually way earlier.

This means that, as a matter of actually playing and having fun, we need some way of stopping early and agree on who won. Trouble is, it’s computationally infeasible to search all the possible plays.⁵ Worse, if you stop early, under these rules the score could be seemingly anything. Consider the following example:

Example 9 Before playing the white stone, black has a lot of territory in the center (marked with tiny black squares). Notice how placing just one tiny stone shifts the score considerably (and the winner, if the game were to end at that very moment). Recall that, before placing the white stone, all those empty points reach only Black, so they are black territory. After placing it, however, they reach both Black and White, so they’re nobody’s territory.

So how can we make this work?

Traditionally, when both players pass, the game doesn’t actually end. Players need to agree on which groups of stones are unkillable (“alive”) and which ones are effectively dead. The lonely white stone in the example above would most certainly be considered dead by any reasonable player. I believe it’s actually impossible for white to “make life” inside that territory if black plays even mildly competently (let alone optimally). But what if White doesn’t agree? Here the answer varies between rulesets. The messier ones, such as the Japanese and Korean rulesets, need a sandbox of sorts during the so-called confirmation phase: players play out the local situation they disagree about, and once the stones have been shown to be alive or dead, the game is reset to the position before the sandboxed sub-game. The need for this sub-game is a consequence of how they define score that I won’t get into. Suffice it to say that the other systems, the so-called “area-scoring” rulesets, like the Chinese, the American, and others, also make players play out their disagreements, but they don’t require a sandboxed sub-game.⁶

Automated systems use heuristics to determine what’s alive and what’s not and choose to pass when there’s nothing good to do. GNU Go, for example, does this.

Another possibility would be to use superhuman AI programs like KataGo as an arbiter/oracle to tell you who won. However, at the moment of this writing, it has some systematic flaws that can be exploited, so it can’t function as an oracle of truth for tournaments (pro players would specifically optimize for KataGo, as opposed to winning in the opinion of other experienced humans). You might think of using it casually, among weak players, and that can work. Only issue is that sometimes you won’t understand why it says that some player lost. To the inexperienced eye, things that are dead can look alive and vice versa. And even if you agree, a weak player would blunder in playing out the life and death situations, so KataGo is not representative of “what would have happened if we both played this out until the end?”, which is what you probably wanted.

To me, this all means that the traditional agreement mechanism is practical, and it works. But ideally, newbies would have their endgame watched by some strong player so he can guide them on which groups are alive and dead. Then, after they decide who won in this way, they can also play it out and see for themselves if they want.

Where can I play Go?

If you live in a big city, chances are there is a go club somewhere. But that’s contextual. My general recommendation is OGS, which is a western server and it’s, of course, free. Start a custom game with the following settings (they should get automatically stored as your default for other games afterwards):

Board size: 9x9
Rules: Chinese
Game Speed: live
Time Control: Byo-Yomi
Main time: 5 minutes
Time per period: 15 seconds
Periods: 5

You can leave the rest at the default settings.

I need more help understanding this game

Unless you are a very careful and thoughtful reader, you will likely need to watch some tutorials for complete beginners to fully grasp the rules and their immediate implications. I suggest the first 5 videos in this playlist. After that, just play some games, try to improve by yourself and if you find yourself stuck, take a look at the Clossi Approach videos. They are fantastic. Just watch the first and try to apply the stuff in further games. Only then watch the second.

I also benefitted from reading Go For Beginners. However, it uses Japanese rules without explaining the sandbox mechanism, which is a big omission in my view and makes some examples confusing.

Beyond the standard grid

There is a website with variants of Go. Some are just Go on unusual graphs, like:

Sunflower The full game can be seen here .

You can even play it on a cube:

Go on a cube You can interact with it here . This could actually be made with magnets and a 3D printer\dots

A server that allows for 3+ players is this. However, it only admits square grids. Another problem with this multiplayer Go is that it’s too easy to kill stones:

Easy kill I play Black. Then, before I ever get another turn, the other players gang on my poor little stone.

I think a fix, at least for 3 or 4 player games, is to create a different grid, one where each vertex has more edges:

Triangular tessellation with hexagonal shape In this grid, only 6 vertices have 3 edges, the ones on the corners. The ones on the sides have 4 edges, and interior vertices have 6 edges. This makes it way more difficult for players to kill stones, so it should compensate for the problem described above. The grid in this example has 331 points, and it’s therefore similar in size to the 19x19 board, which has 361. I have yet to find a way of testing this board in real play, there’s seemingly no server that would allow both this board and 3+ players. I should also mention that this should be easy to make with a wooden board and a laser engraver. I might order one.

Conclusion

Go is one of those games where the rules are simple (or can be), but getting good is really hard. The game has been around for millennia and it shows. It also has some really dedicated players and professionals. I believe it’s well worth a chance and if not, then I hope at least this post was interesting to you.

Just don’t get stuck in infinite loops.

As a programmer you might be tempted to think of a struct {.vertex, .color}, but the math is cleaner and the reading is easier if we separate the color as its own thing. Imagine that we have an array of vertices, an array of edges (adjacency matrix) and an array of colors. The .get() method of the color array would be the $\lambda$ function that we are talking about here. ↩︎
Or “captured”, though this term makes more sense in rulesets like the Japanese. ↩︎
You could change this rule to allow for different initial colorings, provided that they don’t contain dead stones. ↩︎
Another option is considering both the coloring and whose turn it is, which is called Situational Super-Ko (SSK). You need either one of these rules for the game to end. Both methods are equally easy to implement: in PSK you make an array of hashes, where each hash is a function of the coloring; while for SSK each hash is a function of the coloring and a boolean specifying whether it’s white’s turn or black’s (or maybe an 8-bit unsigned integer if you want more players). Either way, not difficult. SSK is closer to what you intuitively care about: not going back to a game state exactly identical to a previous one. If the coloring is the same as before but it’s someone else’s turn now, it’s just not the same situation as before, so in principle it should be allowed. PSK forbids it, SSK allows it. Note, however, that neither PSK nor SSK account for all the Groundhog Day-type situations. For example, in a square grid, a 90-degree rotation of a past coloring would be allowed under both PSK and SSK, yet it’s clear that you are back to the same situation. This doesn’t change the fact that the game is finite, however, it’s just annoying. ↩︎
Which is why machines didn’t beat even strong amateur players until the 2010s, you can’t just do a tree search. ↩︎
Tromp-Taylor is also rightly considered area-scoring (“area-scoring” just refers to the fact that stones on the board are counted as score of the owner, unlike territory-scoring systems, where they don’t count). But as you can see it doesn’t have any early stopping mechanism like other rulesets in “its family”. In theory, Tromp-Taylor gets played until the very end. In practice, it’s always implemented with ways of stopping early. Again, this ruleset is theoretical and mathematically clean, in practical implementations some things change. ↩︎