Re: computer-go: Speed of PN-Search

[David Fotland <fotland@xxxxxxxxxxxxxxx>]

You should probably be smarter about detecting terminal
nodes, to reduce the search depth.  Many Faces does life
and death search at something like 20 nodes per second, but
only searches a few dozen nodes per problem.  At each node
Many Faces calculates tactical stability for all strings, tactical
connectivity for all connections, point control for the diagonals
of each possible eye, and pattern matches the resulting shapes
to get bounds on the number of eyes.

You can look at Dyer's work to see another approach, keeping
a database of the eye value of all small surrounded eyes.

Often there is one or a few moves that are very clearly better than
the others, so a modification to PN search to take this into
account should work pretty well.  I don't use PN search, but the
search I use is closer to PN than to alpha-beta, I suppose.

Be sure to use Wolf's heuristic of trying the opponent's refuting
move next (if your move A at ply N is refuted by opponent's move B
at ply N+1, try B next at ply N).  It's very effective.

David Fotland

At 11:15 AM 7/9/2002 +0200, you wrote:
> Hi all,
> 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? Are there any
> tricks to speed it up? Which information should be stored in the nodes?
>
> Thanks
> Frank