Re: computer-go: Speed of PN-Search

[frank-steinmann@xxxxxxxxxxx (Frank Steinmann)]

> 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.

Yes, I do a brute-force search, but I'm about to build up a pattern
database, so I'll think about what's the best way to use it.

> > 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.

No, I don't need to store very much nodes. I found a good way to reduce the
number of nodes stored in the tree, because I had some memory-problems. The
number of nodes is never bigger than the search depth. But less information
would speed up copying the nodes.

> > 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.

I've read Müller's paper. I use two one-dimensional boolean-arrays to
represent the board. Maybe I should try an integer-array like Müller
describes.

> Good luck with your program

Thanks :-)

Frank