Re: computer-go: Proof number search

[Erik van der Werf <E.vanderWerf@xxxxxxxxxxxxx>]

PN is an interesting algorithm, though there are some drawbacks:
1) The tree must be stored in memory.
2) It does not exploit knowledge about the game.
3) If PN does not provide an answer the search effort is usually wasted.
(In contrast to Alpha beta with a Transposition Table)

There may be ways to overcome some of these problems, e.g. by using
modern PN variants such PN^2, PN* or DF-PN, but I don't have any
personal experience with these algorithms. Using knowledge about the
game can sometimes avoid search completely. If you use PN it should
probably be done only for well defined sub-tasks for which you can make
an estimation whether an answer can be found at all (before starting the
search).

Erik

PS I think Martin Mueller was doing some things with PN recently.
PS2 Maybe you should take a look at Thomsen's lambda-search, or
Cazenave's GAPS.



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/