In this section we present results obtained with the computer program Gobble (version 1.0) that plays go on the 9x9 board using simulated annealing to find ``the best'' move. The point is that nothing more than simulated annealing is implemented on top of the bare go playing rules to allow us to study the method.
We will not describe the program in detail, since this would obscure rather than help the general discussion. Anyone with some experience in programming will agree that an implementation of the algorithm should be straightforward. One technical issue we have to mention is how we define the end of a game (recall that we want to play games routinely to the very end). On first sight this is at least intuitively clear to human players, but while the rules for playing moves in go are elegant and simple, rules for when the game ends and how the result is to be counted are surprisingly complex. The latter two issues are related, and there are in fact different (Japanese, Chinese, ...) rules which in rare cases like a multilple ko or special seki give slightly different results.
We adopt for the moment the following prescription. The computer only passes if either no legal move is available or all legal moves reduce the eye space of one of its groups from two to one. The (over-) simplification lies in the definition of an eye, which is defined to be a field whose direct neighbors are all of the same color and whose diagonal neighbors contain no more than 1 stone of the opposite color (0 for border and corner fields). The reader may convince himself that this definition of an eye is correct for most situations, excluding sekis. When both sides have to pass, the game is over and the result is determined via Chinese counting. These are standard rules except that the computer player does not realize that stones in a seki are alive. Sekis can be dealt with once passing is allowed as an option, but we leave it at that for simplicity and speed.
Let us also mention a few points about the probabilistic aspects of
the program and the annealing schedule. Determination of a good
annealing schedule is a matter of experimentation [2], here
is what we found useful. First we order the moves strictly by value,
which corresponds to a probability of 1 that a move with better value
is played first. Then we sweep over the list once from best to worst
move and switch the order of two neighboring moves with probability
pswap. The probability p(n) that a move is shifted n≥1
steps down the list is
p(n) | = | (pswap)n = exp(- n/T), | (3) |
T | = | -1/ln pswap≥0. | (4) |
Gobble was developed on a 286/16 PC, which translates into very slow and powerless by todays workstation standards. We restrict our attention to the 9x9 board. One important aspect of statistical methods like simulated annealing is that some minimal amount of data is needed to find the signal in the noise. Let us denote by strategy A the algorithm of order 0 described in the previous section. Strategy A requires several hundred games to be played before the data is reasonably reliable which takes on the order of 1 minute on the PC and a few seconds on a IBM/RISC workstation. (Typical physics applications in Monte Carlo are allowed to run for days or weeks, but we have game play with humans in mind.)