Re: [computer-go] 9x9 search, tsume-go (was Re: ComputerOlympiad photo)

[David Fotland <fotland@xxxxxxxxxxxxxxx>]

> (I'm aware that people -- including, I think, David Fotland on this
> list -- have reported higher than 80% success at choosing the right
> move in such problems. But what I mean by "solve" is to arrive at a
> 100% certain answer, so that the program either returns "this *is* the
> move" or "I'm not absolutely sure, I need to think more". That is,
> "solve" as pros solve such problems, or as computers solve the
> corresponding chess problems.)
Go Tools by Thomas Wolf can solve 100% of those problems very 
quickly.  It's designed as
a go problem solver, but it took many, many years to write.

Many Faces is not a problem solver.  It treats go problems in the
context of a game.  For a reasonable speed casual game (about 250 moves),
Many Faces has to make each move in 15 to 30 seconds.  So I can only allocate
5 to 15 seconds to any one life and death problem.  I treat all problems as
whole board problems, since in a real game there are often semeai involved,
so I do full board evaluations.  I can allocate a few hundred evaluations to
each node in a life and death search.  Most problems need 5 to 10 ply of 
search,
so the search has to be very highly pruned.  I use a best-first algorithm 
rather
than alpha-beta for this search, since the tree is so small I can easily 
keep it all,
and traversing the tree is hundreds of times faster than evaluating.  I 
cache trees
from move to move so I can refine the search each move.

If you use Benson's or Muller's life and death algorithm you will have to 
search much
deeper, perhaps 10 to 20 ply.  Many Faces recognizes eye shapes when they are
quite incomplete.  This keeps the life/death search small, but mans that I 
have to
prove tactical stability for each string the group, and tactical stability 
of each connection,
as part of the evaluation.  So each evaluation needs 10's of thousands of 
nodes of tactical
search.

So Many Faces will never "solve" a problem.  It is trying instead to have a 
high probability of
correctly evaluating the status of a group with a few seconds of 
search.  Unless the problem
is very small, it will never have enough time to do a complete exhaustive 
search.

There is a large amount of code in move selection, and partial eye shape 
evaluation.  Because
the move selection is so highly pruned, it often doesn't benefit from more 
time.

David Fotland


_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://computer-go.org/mailman/listinfo/computer-go