[computer-go] Caching of local search in NeuroGo?

[Mark Boon]

On 9-aug-2006, at 0:58, Chrilly wrote:
>
> with this restrictions the ladder routine generates 10-20 nodes per  
> evaluation. The ladder code runs at about 1.5 MegaPos/sec on a 3  
> GHz Pentum. So the ladder code alone reduces the speed of the eval  
> to 75-150 KNodes. A more evolved local search which handles also 3- 
> Liberty problems would make things worse.
> Currently Suzie makes 20KNodes/sec. This is very far away from my  
> initial goal of 100KNodes and already quite close to the 10KNodes  
> mentioned by Mark Boon some time ago. But there are currently no  
> optimizations like the local cache.
>

The evaluation I had in mind would probably spend about one third to  
one half of its time on tactical searches. 3-liberty problems usually  
take many more moves than ladders.

The 10KNodes was not some wild guess of mine. I've spent a lot of  
time in the past developing a useful evaluation with as little  
computation as possible. Of course there's always room for some  
clever optimizations, but I would be very surprised if you can make  
one 10 times faster. There are simply some things that always need to  
be done that you can't get around doing, like calculating some  
influence, constructing groups and territory and such. The size of  
the board dictates this is always going to cost a minimal amount of  
work.

Markus Enzenberger is right in saying that it's faster to recompute  
ladders than trying to cache their results. For 3-liberty problems  
it's a little different. Still, I wouldn't try to solve this problem  
by caching.

Let me give you a hint: instead of approaching this from the tactical  
search and try to decide whether it has become invalid, try seeing it  
from the point of view when a move is played which tactical searches  
in may invalidate. Don't expect to find an easy solution though, it's  
a lot of work to get this even close to working satisfactorily.

The other thing to do is trying to avoid doing 3-liberty search  
altogether. You may find that the most expensive 3-liberty searches  
actually don't give you any relevant information, so only do them  
when really necessary.

Mark