Re: [gnugo-devel] Re: global lookahead, distributed go

[David G Doshay]

On Apr 6, 2004, at 6:48 PM, ab wrote:

> Hi!
>
> David G Doshay wrote:
> > So far lookahead-GnuGo seem to be 3 or 4 stones stronger than regular 
> > Gnu
> Go. There are still a number of issues with
> > this approach we are trying to work out.
> very interesting...
> "3 or 4 stones" is already really a lot!

Yes ... but ...

I think that while we can gain a 3 to 4 stone advantage in "nearly self 
play"
the true increase in strength against a human or another program will be
less. Some of the advantage is that we can correctly predict exactly how
our opponent would have played when we do lookahead. We would not
be as accurate against other players or programs.

> I think this effectively add a kind of search that is not currently
> implemented in gnugo and could (does?) reveal some strategic effects of
> moves instead of just tactical things. Of course really big surprises 
> won't
> be possible, because the selection of the next move is limited to 
> gnugo's
> top10 moves.

Not true. While most of the lookahead paths start from gnugo's estimate
of our best moves, there are entries in the lookahead list that are 
not. We
also ask gnugo what we would move if we were the other player. There
usually, but not always, are entries on this list that are not on the 
"our"
best move list. We are trying different algorithms for selecting the 
paths
from these two lists.

>  Is it an advantage to broaden the selection on the first move
> (add moves that do only sometimes work) and search only till it becomes
> apparent that they don't work?

That would be efficient, but right now all lookahead paths are the same
depth before evaluation.

> How many moves do you generate (inner nodes of tree) typically?

1 genmove for the OUR list
1 genmove for the THEIR list, but they both happen at the same time
because they are each sent to a different cpu.

As many as 8 lookahead paths are selected, simply because we have
8 cpus in the cluster. Then the number of genmove calls is twice the
lookahead depth for the simplest case. In this case the cluster gives us
the width of the lookahead paths in parallel, but clocktime goes only
as the depth.

Sometimes the first pass for selecting lookahead paths results in a
narrower list than 8. In those cases we can split out new lookahead
paths from the short list the next time it is our move.

>  how many leafs do you evaluate typically?

8

> Are you using unmodified versions of gnugo?

we have to add hooks to insert our MPI into gnugo. The more parts of
gnugo we try to use the more places we have to put those hooks. It
has turned out that different programmers use slightly different paths
to generate their moves. Other than that we have not modified any
functional part of gnugo.

> With a small appropriate client this would perhaps be an idea for a
> distributed go project?

This could easily grow in a number of directions. We are staying
flexible and choosing our direction depending upon what we find.

> Except for the exploration (what you're already doing) of the limits 
> of this
>  approach (serious goal), it could also be fun for the
> users to see what is beeing calculated locally and what the resulting 
> move
> is with all calculations considered.

We do not save the lookahead paths. I am not sure exactly what front
end we might use to save or display those paths even if we did. We do
save the head of each path in the sgf file.

> * traffic would be low (send 1 Position per some seconds+the result, a
> number of moves)

We don't even display those moves for ourselves, and with then generated
in parallel we would have to do some serious thinking about how they 
would
best be displayed.

> * users could connect/disconnect whenever they want to
> * run 2 (or 3 games) simultaneous and let the users vote for the next 
> move
> on one board while another board is being evaluated
> (at least while no server initiated tests are running)
> * in competition to a possible(?) solving >=6x6-Go distributed-project

We have not been thinking about interactive exploration. When we are at 
a
good point we will make all of our source available and then you will 
be free
to take it where you desire.

> I think an interesting (not just) fun project.

Thanks, some of us are having fun too. We are also using the MPI
infrastructure for doing physics research, and that is particularly fun
and interesting for me.

> P.S.: Could you possibly post some sgf-files of some calculated games?

I have posted some in the past, although the files that were needed to
see what we were doing were a huge pain to look at. We now can do
nicer things in the sgf file for viewing with Go-Ban (we are doing all 
our
work on Macs). We will post some more as soon as we get the next few
things worked out., which should be in 2 or so more weeks.


Cheers,
David