JOE GIBBS POLITZ
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. Linked resources may have their own licenses, refer to them for details.
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. Linked resources may have their own licenses, refer to them for details.
Terminating and Scoring Go
Go is a complicated game. It’s so complicated that determining who has won is a nontrivial task. Scores in games played by humans are arrived at by consensus and seldom seem controversial, but the complex cases can be quite puzzling. The problem is hard for computers, too. Simplified versions of both so-called Japanese and Chinese rules are used by online Go services, and the OGS even has a disclaimer:
Some sekis contain false eyes that cannot be removed - this count as points in Chinese rules but not in Japanese rules. OGS implements a complex algorithm to detects those situation (sic). Since it’s quite tricky situation to detects, the scoring algorithm might have some flaw and wrongly detects false eyes. If this happens in one of your games please raise a support ticket and we will get the game resolved.To me, this quote sounds an awful lot like amateur attempts at sound program analyses and type-checking. “We wrote something that’s really hard and complicated; if you find something that it lets happen that you don’t like, that’s a bug and you should let us know.” But there’s no actual truth to compare against other than a sequence of counterexamples. That is, it’s not clear if we could prove the algorithm correct, or if a correct but inefficient version exists.
I think it’s fascinating that there isn’t a canonical algorithm for determining the score of a Go game, or even if the game is finished. While I can’t hope to settle scoring for all of Go in a single post, it’s a fun exercise to see what happens if we try to develop one unambiguous definition of termination for Go. Note that coming up with such a definition isn't likely to change the outcome of any Go tournaments, past or future. It's simply an attempt to make well-defined an arcane part of the game that is based on experience, history, and best practice.
Everyone who has taught me Go has touted the simplicity and elegance of the rules. I've passed this sentiment on to those I've taught, but in reality the rules are anything but. Go games most closely resemble something like cellular automata à la the Game of Life: local relationships decide whether stones remain on the board or leave, and small differences in nearby board states can result in vastly different global outcomes. If existing similar models are any indication, this should lead to complex traces through the game indeed.
I'm going to introduce the rules of Go with a special eye towards what can get complicated. As always, we play on the vertices of the board (whose size is fixed in a given game, but may vary depending on the desired length and complexity of the game), using black and white pieces. Players can play on most of the vertices most of the time. In the beginning of the game, there are no restrictions. Play might proceed like this:
This is usually the first rule taught: a completely stone is captured when there are no empty spaces around it. So the center white stone would be removed:
Depending on the scoring system being used, this might award points to the black player. For our purposes, it’s enough to keep track of the fact that a stone was captured, and we'll use the information later if we need to.
We also now have our first interesting constraint on the moves white can make next. White is not allowed to play into the empty space in the center in a valiant attempt to commit suicide. From white’s point of view, the board looks more like:
Constraints like this are useful because they tell us what the board might have to look like for white to have no allowed moves, which would suggest some sort of end state for the game.
That first example was a simple capture of a single stone. Stones that touch form groups and live or die together. So if the board looked like:
Then black could capture both center white stones:
As far as constraints on the next play go, white it isn't suicide for white to play in the spots that were just taken, so playing there is allowed (though not necessarily strategic):
But on future moves, white has restricted itself, as moving again in the inner space would be suicide:
Note that white is definitionally not allowed to move in this space; it isn't just poor play.
The moves we've been calling “suicide” moves so far are more subtle than the examples have covered. This is because, in another twist, if playing a move would capture opposing stones, those stones are removed before suicide is checked for. This means that some apparently suicidal moves are in fact fine. Below, white can play at the green mark, even though it is completely surrounded by black stones:
After, the board would look like:
All of the examples to do with captures so far can be summed up in an algorithm for a given stone placement:
The last real rule we need to decide on has to do with repeated board states. Since we can both add and remove stones to the board over the course of the game, and old captured spaces become valid places to play once the old stones are removed, it isn't obvious that a Go game would have to finish. Consider this board, where black can take a white stone by playing at the green mark:
The resulting board gives white the same option...
Which would bring us back to the same on-board state as before:
It’s useful to rule out such infinite loops for a definition of game termination and scoring. (It’s not imperative; we might be able to show that it’s never strategically advantageous for both players to engage in an infinite loop, so we don't need to worry about them for scoring since we only score games in which players are trying to win. But for a starting definition, it’s useful to know that all games actually end.) We are going to take a hard line on such “ko” states, and say that no on-board state is allowed to repeat (this is hard to keep track of in real games, so the rule is usually that black would have to make some other move before returning to capture the white stone). We can update our turn-by-turn algorithm to reflect this:
This definition of a turn has some nice properties. The best is that we can say that any Go game played with these rules must terminate! It's obvious that there are a finite number of on-board states (a mere 3b2), where b is the width of the board. Every valid move visits a new board state (by step 4, this must be true), so play marches towards a state where no valid moves are left for either player. We can safely call this state an end state of the game.
In the rules so far, we've assumed that both players play every turn. This doesn't necessarily seem fair. Consider this game, where we show the whole board nearly full:
Black cannot play in the two red spots because it would be suicide. Similarly, white cannot play in the green spots. But if black plays in either of the two green spots (the only ones allowed), suddenly white can capture rather than suicide at the other, and can take all of black's stones:
The situation would be similarly bad for white if it were white's turn. Thus, this situation is a game of chicken between the players, and whoever is first loses. Both players have built up a strong position with two holes in their group, making them uncapturable unless they sabatoge themselves. To avoid this forced self-sabatoge, the rules allow players to pass the turn rather than play (there is at least one interesting variation here: whether players can pass one turn at a time and still play on subsequent turns, or if they give up their ability to play for the rest of the game, effectively declaring themselves done). In this situation, both black and white would elect to pass indefinitely. For our purposes, we'll clearly lay out the rules of ending the game around our per-turn algorithm above to reflect this case.
Both players passing is the usual ending condition for Go; I'm not aware of any non-tutorial Go game ever that led to only invalid moves for both players with the definition above. What happens after both players pass is the actual scoring to decide who wins.
I'm going to build up a definition of scoring here that isn’t quite how Go is scored in tournaments. In a brief discussion after, I will argue that the tournament scoring methods are (potentially quite accurate) approximations of this scoring system. That is, all those folks in tournaments are really just saving themselves time and not going into all this pedantic nonsense that I'm spouting here. But, my definition will be rigorous and precise, avoiding any need to speculate on what would happen if you “just played it out,” so onward we go.
There are several pieces of information we can use to assign a score after both players have passed:
I’m going to throw out the game history from consideration for calculating scores. There's probably something frightfully complicated that can be done with the history to judge how players do, but in the interest of simplicity, I’ll focus on the board and the captures.
It’s worth taking a minute to think about what would make a definition of scoring both useful and appropriate. I’ll assume that it’s uncontroversial that the goal of the game is to have some sort of control over the board, and this should be reflected in the score, for some definition of control.
Let's think about what control might mean in terms of the end board state, and in terms of captures that may have happened along the way. Each player has an equal number of opportunities to play stones. If no captures happen, the player who passes least will have more stones on the board. I’ll take the position that passing represents some sort of weakness; the lack of the ability to make a move means the passing player has less control over the board. The corollary is that having more stones on the board at the end of the game results in a higher score. So in this game, white wins, since it played more stones and no captures happened (note that black probably passed a number of times at the end of the game to avoid endangering its large group):
White captures: 0, Black captures: 0
White stones: 13, Black stones: 8
Things get interesting when we consider captures. When stones are captured, new space opens up on the board to play in. All other things being equal (e.g. with no further captures or extra passes from one player), both players should be able to fill up about half the space. In practice, since the captured area is (by necessity) already surrounded, it’s usually easier for the capturer to take advantage of the space than the capturee. So, even if we don't count the captures at the end of the game, their effect should be visible in the counts of stones on the board.
For simplicity, I find it interesting to think of the game's score being simply the number of stones of each color left on the board at the end of the game. The extra points gained by captures should be reflected in the extra stones of the opposite color laid down. The differential in captures will be clear, and greater territory is reflected by the opponent either passing or making ineffectual moves that only lead to captured stones.
So, we run the game to termination as we describe above, and then count the number of stones of each color on the board. The player with more wins, simple as that.
I’m cutting this post a bit short, since it’s ballooned quite large already, but if I get around to it sometime I'll compare this simple scoring technique to the Chinese and Japanese rule systems, and discuss why they are appropriate approximations of the simple scheme I've proposed here.