Re: computer-go: Proof number search

["P.J.Leonard" <P.J.Leonard@xxxxxxxxxx>]

 I have implemented PN search for tactical problems.

 I think the problem Dave is highlighting is that in go it may be
impossible (with the given resources) to prove many problems
that have a wide branching tree. In my version of the search
I iteratively expand the tree with sets of moves that have been
order using a heuristic. So you start be trying to prove a goal
just using the best moves/responces. If this becomes complex
then you start introducing the moves which scored less on the heuristic.


 There is a similar approach which has been published (sorry I can
not recall the reference just now).


 I believe that PN combinbed with heuristics is the best way foward
for solving GO problems. But your proof statement should be in terms
of heuristics goals that prune the search. (e.g. can I capture using
only the suggested moves with a heuristic greater than a given value).
This initially gives you a result that can be refined by lowering
the value to expand the tree.

 For many go problems the result of search is not binary (e.g. maximise
territory) in this case it may be possible to use PN search to prove
a statement that proves a move can achieve a certain value. Again
setting a low target should give a result which can be refined by
increaing the target. This approach requires a search which allows
the status of terminal nodes to change when the target changes.

 Having said all this. I think the most difficult problem in go is
still heuristic evaluation. Work increasing your heuristics is
probably going to increase the strength of your program more
than using a fancy search scheme.

 Good luck  Paul.







David Fotland wrote:
> It's an interesting algorithm, but not for Many Faces.  PN search works 
> best when the
> tree is irregular, perhaps with long forcing sequences, since it focuses 
> the search
> where there is less work to be done.  It assumes no knowledge about move 
> ordering.
>
> In go tactics, it is pretty easy to accurately order the moves, but its 
> hard to absolutley
> eliminate all but a few moves unless there is a ladder.  In a ladder it 
> is trivial to find
> the best move quickly, so there is no need for PN search.
>
> If you don't want to spend the time to count potential new liberties or 
> potential new eyes
> to do move ordering, then PN search might help.  BUt if you are doing 
> life and death without
> recognizing eye shapes you have to read so much deeper you had better 
> have a really fast
> computer :)
>
> Regards,
>
> David
>
> At 05:37 PM 5/14/2003 -0700, you wrote:
>
> > I'm reading Dennis Breuker's thesis (thanks for the link, Erik), and 
> > it's fascinating.
> >
> > This "proof number search" algorithm sounds like it would be fabulous 
> > for ladders and life-and-death.  Is anybody using this for Go, or was 
> > I just handed a piece of low-hanging fruit?  :-)
> >
> >
> > Peter Drake
> > Assistant Professor of Computer Science
> > Lewis & Clark College
> > http://www.lclark.edu/~drake/