Computer Go/Tromp-Taylor Rules

Go is played on a 19x19 square grid of points, by two players called Black and White.
Each point on the grid may be colored black, white or empty.
A point P, not colored C, is said to reach C, if there is a path of (vertically or horizontally) adjacent points of P's color from P to a point of color C.
Clearing a color is the process of emptying all points of that color that don't reach empty.
Starting with an empty grid, the players alternate turns, starting with Black.
A turn is either a pass; or a move that doesn't repeat an earlier grid coloring.
A move consists of coloring an empty point one's own color; then clearing the opponent color, and then clearing one's own color.
The game ends after two consecutive passes.
A player's score is the number of points of her color, plus the number of empty points that reach only her color.
The player with the higher score at the end of the game is the winner. Equal scores result in a tie.

Discussion

The most common criticism of Tromp-Taylor rules is that they do not describe a method for removing "dead stones" from the board. If both players are required to play until all stones on the board are alive²,

games can be very tedious to play or to watch
it becomes a waste of time to continue once both players know the eventual outcome of the game
computer programs that are designed with Japanese rules in mind may not even be able to play to that point without a significant redesign

Removing dead stones

NOTE: According to Tromp-Taylor rules no stones are removed after two consecutive passes!

After two consecutive passes, stones which both players agree could eventually be captured are removed from the board. But what if there are stones on the board that one player believes could eventually be captured, but the other player disagrees?

Note: in practice, disagreements between humans are extremely rare. Novice players frequently make mistakes in determining which stones could eventually be captured, but they do not typically disagree. It is a considerably more significant problem in Computer Go, where novice programs are less skilled than any human. Programs which pass and then do not agree on which stones are alive make Computer Go look ridiculous to most human players.

Third-party mediation

The simplest solution is to use a third-party in cases of disagreement. This third-party could be a human judge, or a computer program that is capable of automatically determining which stones could eventually be captured.

Potential problems:

The third-party may be incorrect or biased, especially if the third-party is a computer program
It may be too time-consuming or take too many resources to have a third-party judge (for example in large tournaments, or on automated servers where hundreds of games end every minute)
There may not even be a third-party available

Chinese rules

After two consecutive passes, if there is a disagreement, the disagreement must be settled by further actual play. In a programmatic environment, this may look something like this:

Both players provide a list of all the stones they believe could eventually be captured.
If the lists differ, play continues, starting with the player who first passed.
If both players immediately pass again (thus making four consecutive passes), the game is over and all stones on the board are considered alive.
If later in the game both players again pass, the process is repeated.

Note that this can never result in an infinite loop, because each time through this process another stone must be added to the board or the game ends.

Potential Problems:

In timed games, one player may run out of time and lose while trying to capture stones that are obviously dead. In some circumstances, "clean-up" moves can involve life-and-death problems that take considerable time, especially for computer programs, to play through properly.

Japanese rules

After two consecutive passes, disagreements must be settled by further play, much like Chinese rules. However, since this may alter the score of the game under territory scoring, the board position that existed at the end of the two passes must be copied to a second board, and the disputed position resolved on that board. The resultant state of any disputed group(s)—alive or dead—is then applied to the group on the original board, and the second board discarded.

Potential Problems:

In addition to the problems with the Chinese rules solution, it is inconvenient to duplicate the board position in order to play out disputed positions. Most computer programs are not designed to do this sort of dispute resolution, and most protocols are not designed to support it.

KGS Computer Go Tournament rules

The KGS Computer Go Tournament rules are in essence identical to the Chinese rules, except that, after the first disagreement, the players are advised to manually capture all stones they believe are dead. After the next two consecutive passes, rather than repeating the process, the game is immediately considered over and all stones on the board are counted alive and scored as such. See: http://www.weddslist.com/kgs/rules.html#gep

Note: this protocol has been proposed but is not currently in use for KGS Computer Go Tournaments; currently disputes are resolved by third-party mediation.

Considerations

When attempting to develop a sensible method of resolving the issue of dead stone disagreement, it may be helpful to keep a few points in mind:

Some Go engines are very simplistic and do not or cannot produce an accurate list of dead stones. Any solution should not penalize such programs; it should elegantly fall back on the default Tromp-Taylor method of counting all stones on the board as alive.
In the case where the two players are never able to agree on which stones could eventually be captured, the method should not allow an infinite loop, nor should it prevent a player from capturing stones that can indeed be captured.
A solution should be able to resolve situations where all groups on the board are unsettled (for example, if there are only two or three stones on the board)
A solution should take into account when:
- a player has one of their opponent's groups marked as dead when their opponent doesn't
- a player has one of their own groups marked as dead when their opponent doesn't
- any combination of the above

Abusive Behavior

It is feasible that a computer program (or a player) might:

purposefully not provide an accurate list of dead stones, thus forcing their opponent to continue the game, hoping the opponent makes a mistake or loses on time
place stones with no chance of survival inside of an opponent's large eye, hoping that the game will end with some of these ought-to-be-dead stones still on the board

These sorts of abusive behaviors "make sense" under many rulesets, but they are very annoying to humans in general. Tactics like these should be considered rude, but they should primarily be opposed socially, not programmatically. However, it is worthwhile to make sure that a proposed solution doesn't overly reward such behavior.

Footnotes

John's Go Page. http://tromp.github.io/go.html
For the purposes of this page, "alive" means stones that are counted as points at the end of the game, and "dead" means stones that would eventually be captured if play continued.