Re: computer-go: Speed of PN-Search

[frank-steinmann@xxxxxxxxxxx (Frank Steinmann)]

Thanks, I think, that will help me. My algorithm is not very smart in
detecting terminal nodes yet, but the pattern database I'm building will do
a good job here.
And I'll have a look at Wolf's heuristic.

Frank

----- Original Message -----
From: "David Fotland" <fotland@xxxxxxxxxxxxxxxxx>
To: <computer-go@xxxxxxxxxxxxxxxxx>
Sent: Tuesday, July 09, 2002 10:36 PM
Subject: Re: computer-go: Speed of PN-Search


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