[computer-go] How to cache local tactical searches?

[Peter Drake]

You might try the method I used for caching the result of life-and- 
death searches in a recent paper:

http://www.lclark.edu/~drake/go/icai2006-final-drake.pdf

Peter Drake
Assistant Professor of Computer Science
Lewis & Clark College
http://www.lclark.edu/~drake/




On Jul 31, 2006, at 1:29 AM, Chrilly wrote:

> The eval of Suzie has a ladder-searcher which I plan now to extend  
> to Geta's and simple 3-Liberty Problems. Although the ladder-code  
> is reasonable fast, in more complicated positions the speed of the  
> eval goes down considerable due to the local tacitical search. So  
> far I use the most primitive cache method. A hash-table with the  
> global hash-code. Due to iterative deeping there are some cache- 
> hits, but the percentage is much lower than with a more clever  
> cache-scheme.
> One idea is that the local search marks a Dirty-Bitmap. All the  
> intersection which have been visited (and probably also the  
> neighbours of the visited stones, because e.g. the status of a  
> ladder-breaker depends also on its liberties). The dirty Bitmap and  
> the current Board-Bitmaps are stored. When the local search is  
> called again, the old result is used, if the new board matches the  
> stored one on the intersections of the dirty bitmap.
> I do not know if the method works in case of ladders at all, e.g.  
> the liberties of a ladder breaker can depend on a stone in a  
> completly other part of the board. Its not my intention to have a  
> perfect ladder code. The question is, if the idea is flawed at all  
> and not only in some tricky special cases.
> A also do not know if the BitMap Key is the best way. I am not  
> really satiesfied with this idea. One has to store 3 Bitmaps and  
> also the comparision is relative slow (but of course much faster  
> than doing the search again). Any other suggestions?
>
> Chrilly
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://computer-go.org/pipermail/computer-go/attachments/20060731/7e69704b/attachment.htm