Re: [gnugo-devel] GNU Go as an oracle

[bump]

> GNU Go can certainly be improved a lot by continued tuning, bug-fixing,
> improving the integration of the readconnect code and -- maybe most
> important -- fundamental improvements in the owl code. But I agree with
> Dan (assume this is your motivation for oracle), that in the long run we
> will have to do some local or global alpha-beta search.

Yes, exactly.

GNU Go can be made stronger than current engines without radical
changes. But to make a really strong engine we're going to have to
do something different. 

I think the key is semilocal search, generating moves in a
restricted area of the board, generating, saving and maintaining
from move to move a small move tree.  When the opponent moves, the
tree is pruned at the base, then deepened if necessary. 

It will be good if the owl code must be callable at deeper levels
of the tree without horizon effects. This is the purpose of the
oracle, a second GNU Go process which thinks stackp==0.

The biggest obstacle is speed. The schemes I have in mind would be
too slow currently and also require multiple GNU Go processes
communicating by unix pipes so there will be portability
problems. So when this stuff is ready to go into the engine it will
have to be a configure option turned off by default.

Having multiple GNU Go engines working on a problem might work
well on multiprocessor machines.

I see two possibilities.

(1) Search based on a metamachine. Use top_moves to generate move 
candidates, then search a tree. I'm working on this now.

Around the time I posted this patch I was pessimistic because dreihirn
experiments of mine seem to show that even selecting among the top 3 or 10
moves is not good enough to make a strong engine. However I have
modified shapes, genmove and move_reasons so that moves only within
a limited area are generated, and I think after this modification
it will be possible to try this.

I think it will be important to save and maintain a small local
move tree in different areas of the board.

(2) Search based on a new pattern database.

Generate a small move tree, evaluate the nodes, use alpha beta
or minmax to find the best move.

Endgame play might be a good place to start. Generate a small
move tree for each local area, save these trees from move to
move, use combinatorial game theory to find the best move.

I started to work on this when I was pessimistic about the
metamachine approach, hence the tiny pattern database in the
patch. Currently I'm looking at (1) again. I'm trying to
add a metamachine to the patch.

> At the moment we are probably not yet ready for starting this. However,
> I think we should keep it in mind as a goal and at least not make it
> harder to get there.

I'm not sure we're not ready for starting this. I do think it
will be a while before it is practical and such a goal should not
prevent us from (for example) undertaking to rewrite the owl code.

I'm continuing to work on this patch and will probably post an updated
version in a few days. 

> One important step would be to shift the move valuation step by step to
> a strict before move/after move comparison. (I.e. we should evaluate
> positions, not moves).  This might be a little harder to tune, but I think
> in the end it is more clear and possibly cleaner code.

This can be accomplished quickly within the context of metamachine search.
Currently the evaluation of positions is not good enough, for example
interface/gtp_examples/metamachine.c is weaker than gnugo. 

What you have in mind is different. You want a single GNU Go
process to use a revised move valuation scheme. This is not
incompatible with what I'm doing and is probably a step in the
right direction.

Dan