I’ve actually been spending more time working on my projects lately than writing about them, yay! I promise I’ll try to write more often, though. (At least if life settles down a bit.)
I’ve been working lately on implementing the “end-game protocol” for my Go server. The game of Go is a little odd in that there’s no concrete point at which the game is over. The object is to surround territory on the board, and when a player feels that all the territory on the board is solidly captured and well-defended, he simply passes. If both players pass, then the game is considered over.
After both players pass, there will likely be left on the board stones that could have been captured throughout the course of the game. The players will typically recognize that these stones are, in fact, “dead,” and remove them after passing but before counting the score.
It turns out to be rather difficult for a computer program to figure out which stones are “dead,” so servers where computer programs typically play don’t have any mechanism for removing dead stones from the board, since that would make things more complicated. The programs just tediously spend the time capturing all the stones, one by one, until all “dead” stones have actually been removed from the board through play.
This would be outrageously boring for human players to do. In fact, I don’t know of a single server for humans that requires them to capture all stones manually, like servers for computer programs do. (I think one of the Facebook Go apps did originally, but hardly anyone used it until they added a “mark stones dead” feature.)
Normal Go servers just have the players click on the dead stones to remove them from the board. Human players almost always agree on which stones are dead, but on the rare occasion when they disagree, most Go servers don’t have any way to deal with this. On KGS (one of the most common Go servers in the US), the players will typically ask a stronger player for help resolving the issue. The stronger player will take one glance at the situation, and tell the players whether the stones are, in fact, capturable.
This tactic works for human-versus-human matches, but obviously it is more difficult when there is a computer involved. How do you “convince” a computer that it’s wrong about the status of some troublesome stones?
For my server, I wanted it to work well for both human and computer program matches, so I had to devise a way to resolve disputes about dead stones. I ended up implementing a very simple approach—if after two passes, the players disagree, then play continues. If both players pass again, then all disputed stones are considered alive. This gives the player who thinks they’re dead incentive to actually capture the stones through play. If he cannot do so, then he will have to pass and the game will be over.
I now have this end-game protocol implemented and working well. Although it’s not going across the REST server yet, I’m able to play against GnuGo and successfully resolve games where we “disagree” about the status. The client still needs a bit of cleaning up, but the concepts are sound and the functionality is there.
Entries (RSS)