RE: computer-go: Proof number search

["Anders Kierulf" <anders@xxxxxxxxxxx>]

SmartGo is using proof number search to solve tactical problems:
captures, semeai, and connections. (For ladders, a simple recursive
algorithm suffices. Life and death is handled by GoTools.) Our
experience is that proof number search works better than alpha-beta for
tactical problems in Go.

Before using proof number search, SmartGo used a combination of
depth-first search (for a few hundred nodes) followed by iterative
deepening, with a lot of effort invested in getting the move order
right. The depth-first portion speeded up simple problems where the move
ordering was correct, while the iterative deepening helped avoid getting
stuck in deep branches when the move ordering was off.

Measuring the capture problems encountered in an actual game showed that
proof number search solved 10% more problems in 25% less time. (Which is
a good gain, but no silver bullet.) In addition, the search is less
sensitive to move ordering, so that part could be speeded up. We've also
found that it makes sense to assign proof and disproof numbers to
terminal nodes that depend on the evaluation, rather than simply 1, to
exploit knowledge of each particular tactics.

Proof number search has some tricky implementation issues, in particular
the handling of transpositions. As you keep the search tree in memory,
you essentially have to keep a DAG rather than a tree, and proof numbers
may have to be backed up to multiple parent nodes. It's not exactly
low-hanging fruit. :-)

Anders Kierulf
www.smartgo.com

Peter Drake 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/