Re: [gnugo-devel] montecarlo

[Heikki Levanto]

On Wed, Apr 11, 2007 at 02:47:06PM +0200, Wolfgang Manner wrote:
> The april edition of "Pour la Science" (which is the french version of
> Scientific American) has an article on MonteCarlo methods for go programming.
> i thought a little about it, and dont see how this can work.
> However they claim to have some success, in particular for 9x9 games.
> who knows more about that ?
> Is this a subject one should look into ?
> what do people think ?

I have made a few experiments, and it actually seems to work. Better on
9x9, but tolerably well on 19x19.

The main idea is simple: Since it is hard to evaluate go positions,
let's play them out as fast as possible. That means (almost) totally
random, only taking care not to fill 1-point eyes, and not to play
suicides. As long as both sides play equally badly, the winning ratio
says something about whose position is better. The key is to make it
fast (40.000 playouts/sec on 9x9 on my AMD-64), and to make enough of
them.

One of the simplest ways to use this is to try all legal moves, play a
number of playouts from each, and choose the one with best winning rate.
This leads to some silly anomalies, like playing totally random when one
player is clearly winning (all moves lead to 100% win or loss), going
for a half-point win;  and the program liking to play silly ataris, even
when the played stone itself is in atari, because there is always a
chance that the program gets to play a second stone before the opponents
random play happens to capture the stone.

These things can be minimized with some tricks. Most effective is to
make a probabilistic tree search (UCT), using the Monte Carlo playouts
as an evaluation function for the leaves, and iteratively deepening
those that look promising. Such programs are doing quite well on 9x9.

There is an ongoing tournament for 9x9 programs at
   http://cgos.boardspace.net/9x9/index.html
Gnu Go has played there for a while (I don't know with what settings),
and has gained about 1800 ELO points on their rating system. The best
programs are based on UCT, and are around 2500, considerably better.

Lukas Lew has written a nice library fotr MC playouts and some UCT
codetoo. It can be found at 
    http://www.mimuw.edu.pl/~lew/
It is a good starting point for studying the techniques.


Hope this helps

   - Heikki



-- 
Heikki Levanto   "In Murphy We Turst"     heikki (at) lsd (dot) dk