[computer-go] UCT finds the right answer, but...

[Peter Drake]

On Nov 7, 2006, at 11:10 AM, Magnus Persson wrote:

> Quoting Peter Drake <drake at lclark.edu>:
>
>
>> The probability of winning by starting at b2 is greater than the   
>> probability starting elsewhere, but shouldn't it approach 1.0,  
>> since  b2 is a winning move? Do others get this same behavior?  
>> Does anyone  have an explanation?
>
> The situation is still such that random play can mess things up.  
> Even if black
> is winning UCT search for white will pick those moves which allows  
> black to
> make bad moves deeper in the tree.

I've had similar experiences with other variants of Monte Carlo Go.  
Incidentally, I think this makes ladders particularly difficult.

Thanks, good to know it's not just my program that exhibits this  
behavior.

> What you should do is to print out the winning percentage for the  
> principle
> variation and not only the top move. In valkyria the winning score  
> do not
> change much at the root but following the tree down a winning  
> variation often
> increase the winning percentage 5-10 % at each ply until it reache  
> a point
> where random play always lead to a win.

It doesn't always work out that way, but sometimes it does:

B2:0.292577
H9:0.291222
C2:0.29693
G2:0.292865
G6:0.312761
B1:0.35
J2:0.666667
PASS

The important thing is that UCT (very!) quickly finds the correct move.

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