Re: [gnugo-devel] Global Serach

[David G Doshay]

On 28, Nov 2005, at 4:40 AM, Petri Pitkanen wrote:

> How difficult it would be to build a global alfa-beta search on
> top/into of Gnu Go? I tried browsing the code and came to conclusion
> that it would be pretty difficult since:
> - GnuGo does not have evaluation function, But move value function,
> This would need to be propagated in search tree
> - Alternating needed between plys could be bit tricky
>
> Easiest could be some script language implementation built on top of
> modified GTP Ie. Special command that would request from GNU-Go list
> of moves together with their values.
>
> I would like to try this as I am quite sure that GG is strong enough
> that global look ahead would do some good. Also it should be as easy
> as possible since main goal would be to know does it help.
>
> Petri PItkänen

On 28, Nov 2005, at 2:15 PM, Gunnar Farnebäck wrote:

> Petri wrote:
> > How difficult it would be to build a global alfa-beta search on
> > top/into of Gnu Go?
>
> Feel free to try it out. Be aware that there are two other ongoing
> efforts in this area; David Doshay et al work on SlugGo and Evan
> Daniel works on GoFigure. You should be able to find some information
> about those by searching the mail archives for this list and the
> computer-go list.
>
> /Gunnar

Hello Petri,

SlugGo does global lookahead on top of GNU Go. What we do is a little
different than what you suggest in that we do not do any alpha-beta on
the lookahead sequences because we put each lookahead sequence
on a different cpu in a cluster. This parallelizes the search, and each 
path
takes much the same time, so there is no clean way I know of right now 
to
benefit from the alpha-beta pruning (although Li Liao in China wants to
work with us on some parallel alpha-beta).

I agree that one needs a metric for success at the end of the sequence, 
as
well as an algorithm for choosing the depth of each lookahead sequence.
We simplify the second by just doing fixed depth and a predetermined 
fixed
branching pattern (sometimes no branching at all). Our metric is a
combination of influence and territory (both already in GNU Go, although
we fiddle with them and have two time dependent weighting functions
because influence is more important in the beginning and territory is 
all that
matters at the end). Because we are unsure of the correct balance 
between
our global evaluation and GNU Go's move_value, we combine the pre and
post lookahead values, and also have another pre-lookahead fitness
function we toss in too. We are now doing some machine learning and
genetic algorithm work to see if we can find the best algebraic 
combination
of these values.

While I agree that there will be some tricky parts to doing it in an 
alpha-beta
manner on a single cpu, I do not think that there are any real 
impediments.
Right now we use MPI for the message passing between the nodes in the
cluster, but MPI can also be used on one cpu to separate the lookahead
steps from the main GNU Go loop. But MPI has a steep learning curve, and
if I were starting over I would probably use Java, which has pretty 
handy
message passing. We have a side project running right now to replace the
MPI in SlugGo with Java ... nothing to report on that yet.

If all you want to know is if it works, the answer we have (over more 
than
4,000 games) is: most of the time. SlugGo plays much better against Many
Faces than does GNU Go, but is rated much the same on KGS. Most of the
time SlugGo is correct when it overrules GNU Go, but sometimes it is 
very
wrong.

If you have any detailed questions about SlugGo, feel free to contact me
directly, off of the list. I have blathered on in great detail here 
about what
SlugGo does, and we don't need to expose everybody to that again.



Cheers,
David