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

[Peter Drake]

The article is about a way of storing results for life-and-death  
searches, which are of course local.  I suspect that it could be  
useful for other local searches, but I have not tried this; there may  
be complications.

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




On Jul 31, 2006, at 10:05 AM, Chrilly wrote:

> Thanks for the pointer to the article.
> The article is very interesting, but its not about local search. I  
> assum you mean the indexing scheme which is better than plain- 
> vanilla bitboards.
>
> Chrilly
>
>
> ----- Original Message -----
> From: Peter Drake
> To: computer-go
> Sent: Monday, July 31, 2006 6:21 PM
> Subject: Re: [computer-go] How to cache local tactical searches?
>
> 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/
>
>
>
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
> _______________________________________________
> 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/0836cd33/attachment.htm