[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [gnugo-devel] Global Serach

From: David G Doshay
Subject: Re: [gnugo-devel] Global Serach
Date: Mon, 28 Nov 2005 16:56:51 -0800

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.


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

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.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]