Re: computer-go: Proof number search

[Vincent Diepeveen <diep@xxxxxxxxx>]

Hello,

for my chessprogram i have experimented a lot with the different algorithms:

Proof Number Search

A more interesting thing is the different conspiracy number searches.

CNS1 and CNS2.

CNS2 i directly have put through the toilet, because it is double checking
and when i played P.Conners (which ran at 180 processors or more) i simply
outsearched it.

CNS1 i have done extensive experiments with. I concluded that not only
these algorithms are very instable, basically the weak spot of both of them
is the hard fact that the search is dependant upon the evaluation quality.

For example when evaluation concludes: "this branch has just 1 move", then
CNS will deepen it. Note that it is possible to use it with nullmove. I
used it with big memory (256MB in experiments a few years ago was a *lot*)
so i could fill the memory for several minutes before it was filled. I
therefore didn't need to find solutions for searching more positions than
the memory could hold. So no overwrite errors occured.

Anyway, back to the deepening of lines. 

If your eval already evaluated it well, then CNS will do well.

You already see the problem. If your eval already knows what it is, then
why need to extend it?

You want to search the *unknown*. 

In Go, of course most searches are done very unprofessional, because of the
huge branching factor (10.0 with empty board when using nullmove) and slow
nodes a second for global evaluations.

So CNS looks tempting. But the fundamental problem is the fact that the
search is dependant upon how well your evaluation is.

Then secondly, this is true for both searches, they have overhead which a
normal search does not have.

The overhead is not easy to understand for those who do not know exactly
know how the algorithms work.

Basically you must determine a number which either disproofs something or
which proofs something. In both algorithms.

The overhead is getting that number higher. In alfabeta+ selective search,
there is no need for that overhead. A cutoff is a cutoff simply, even when
1 position gives the cutoff.

In CNS you need to search nonsense in order to show the algorithm that this
branch is not interesting to search deeper.

That overhead is *significant*.

At 19:57 14-5-2003 -0700, 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/
>
>
>
>