Re: computer-go: Speed of PN-Search

[uzsxtn@xxxxxxxxxxx]

Hi Frank,

> I'm a computer go newbie, having the crazy idea to develop a good
> go-program. :-)
> I just implemented a Proof-Number-Search-algorithm to detect wether blocks
> can build enough eyes to live or not. But I'm not happy with it yet. Despite
> some optimizations, the number of nodes it can handle in one second,
> searching a local 5x5-area, is about 1000. It seems a bit slowly to me,
> 'cause if there are only few stones in the area, I can't search deeper than
> depth 3 in an acceptable time.
>
> So my questions: How fast should/could the algorithm be?

I don't think it is possible to answer this question in general, a lot of
approaches are possible. GNU Go's owl code (which does the life-and-death
analysis) is rather slow, I think s.th. like 50-100 nodes
per second on my K6-2 400 MHz (have never measured this exactly). This
is because GNU Go spents a lot of time analyzing the position and
selecting the moves it is going to try. (This selection is based on
a pattern database). It does not try more than 3-4 moves in each position,
and it doesn't visit more than 1000 nodes for each life and death fight.

However, if you do a brute-force search, you probably need to be faster.
Then the main problem then is to write a fast algorithm to analyze
the eye space.

It would certainly be interesting to compare the speed of the
life-and-death analysis in other Go programs.

> Which information should be stored in the nodes?

I guess just about everything that would otherwise need to be recomputed
if you revisit a node. I have never implemented a Proof-Number-Search, but
I assume a problem here is that you need to store this information for a very
large number of nodes (compared to alpha-beta cut). I think that GNU Go's
owl code (without bigger modifications) couldn't be ported to
Proof-Number-Search for this very reason.

> Are there any tricks to speed it up?
I don't know about any Go-specific speedups -- apart from using a
one-dimensional array to represent the go board, as explained somewhere
in M. Müller's papers, or also in the GNU Go documentation. I am pretty
sure you should do that.

Good luck with your program

Arend