Tuesday, November 05, 2002
      ( 8:52 AM ) Matt  


Last week there was a really interesting thread on rec.games.go on random go algorithms. The idea was to come up with a consistently weak algorithm. It would be consistent in that it would be difficult to exploit any particular weakness. For example, even the strongest go programs today will have some weakness which, if you know how to exploit it, you can easily beat the program. Therefore, even if the program plays at approximately a 10 kyu level, you need not be 10 kyu or better to beat it, if you know this one little trick. The problem with a completely random go player is that it is difficult to tell it when to stop. It will eventually begin to fill its own eyes, and even turn groups which are unconditionally alive into dead groups.

The most interesting algorithm presented in this thread is called the crawler. Holigar posted a brief description of this algorithm to rec.games.go. The basic idea is that it makes the play which increases its number of liberties greatest, ties broken randomly. Holigar claims that the result is to start in a random place, and then extend a horizontal or vertical line of stones until an edge, or enemy stones are reached. It then turns in a different direction.

I gave some thought to this algorithm, and would like to make it a little more concrete. First, I define number of liberties as the number of empty intersections adjacent to at least one friendly stone. With this definition, it seems that playing a move which is non-adjacent to any previous stone is the preferred play as this creates four new liberties instead of the 2 created by playing adjacent to a friendly stone. To achieve the behavior described by Holigar, I impose a group penalty. I define a group as a maximal set of mutually adjacent stones. This is sometimes called a string in go algorithms. The value of the group penalty must be 2 or more to encourage adjacent plays. It should also be less than 4 so that new groups may be formed.

This leads us to an equation like this:

S = l - kg

where S is the score for a position, l is the number of liberties, k is the group penalty, and g is the number of groups.

This can be extended and generalized to include a score for the opponent's position:

S = k0 lf + k1 gf + k2 le + k3 ge

Here kn are constants which characterize the algorithm. lf and le are liberties of friendly and enemy stones respectively. gf and ge are the numbers of friendly and enemy groups respectively. My first intuition is that k0 should be positive, and k1, k2, and k3 should be negative. To implement holigar's algorithm, I suggest values of 2, -5, 0, 0.

# -

Comments: Post a Comment

Dreams I have...

Powered by Blogger
Feel free to e-mail me.

free hit counter