[computer-go] (no subject)

[Peter Drake]

Orego has moved three rungs up the 9x9 ladder, defeating  
JacquelineGo, Godot, and Gogo.

Our program is very similar to Remi Coulom’s Crazy Stone, with the  
following differences:

- Our move selection algorithm is to choose randomly with probability  
p, otherwise choose the currently best move. p varies linearly from 1  
down to 0 over the course of a turn.

- Our backup algorithm is to take the average of the children,  
weighted by the number of runs through those children. A similar  
formula appears in Chaslot et al’s “Monte-Carlo Strategies for  
Computer Go” at the beginning of section 3.2. The idea is that, as  
more and more runs occur, the vast majority of moves are through the  
best branch. We also avoid giving much weight to a poorly-explored  
branch.

- We keep the relevant part of the tree between turns. We can often  
keep about half of our work after we move (and half of that after the  
opponent’s move), especially during forcing sequences.

- We use the probability of winning rather than the estimated score.  
Several people on the computer Go mailing list have reported this as  
a big win.

- We copped out at put in one piece of domain-specific knowledge: the  
program always opens in the center.

Future work:

- Rather than hand-build an opening book, we could do perhaps a  
million runs on the empty board and save that tree.

- This algorithm is probably very amenable to parallelization.

- We would like to be able to break the board down into unrelated  
areas. This is probably crucial for 19x19 play. Ideas include  
partitioning the board by strongly-controlled points and looking at  
correlations between points’ expected fates.


Peter Drake
Assistant Professor of Computer Science
Lewis & Clark College
http://www.lclark.edu/~drake/