[computer-go] Rotate the dog or the tail?

[David G Doshay]

We are adding a database of patterns to SlugGo and are storing all 8.

Cheers,
David



On 16, Jun 2006, at 1:13 AM, Chrilly wrote:

> In all the pattern-matching articles I know off only 1 pattern  
> orientation is stored and the area around the board-point is  
> rotated. I do not understand the advantage of this method.
> It should be more efficient for matching to store the pattern 8 times.
> Lets assume a Hashing-Method like described by Mark Boon.
>
> The size of the Pattern-Hashtable is no argument. Even with 3000  
> patterns one gets at most 24000 mirror-patterns. Assuming 20 Bytes/ 
> Pattern makes 500 KByte. This is even for a mobile-Go nowadays no  
> Problem. Maybe I make a logic error, but the number of matching  
> operations should be (in the mean) the same, if one looks up 8  
> mirrors in 3000 Patterns or 1 original in 24000 mirrors.
> But looking up 8 mirrors jumps around in the Hashtable, whereas the  
> 1 original pattern searches in a linear way through the Hashtable.  
> One needs also only 1 Hash-Adress calculation (which is cheap).
> There should be only 1 cache-miss at the first pattern, the  
> following patterns are already prefetched. A cache-miss is the most  
> expensive "operation" on current CPUs. Additionally one does not  
> need to rotate the board (which is not so cheap). One starts also  
> only 1 matching loop and not 8. Every loop-termination causes a  
> branch-misprediction. This is the second most expensive operation.
>
> This assumes, that the Hashtable is not organized as n-linked- 
> listst (like in the Mark Boon code), but as a single Array.  
> Patterns with Hashcode 0 are in position 0...h0, with Hashcode1  
> from h0+1...h1,,,,
> One simply needs for every Hashcode a pointer to the starting  
> region of the Array. As the patterns are only updated at startup  
> (or even read in from disk), building up such an array is simple.  
> Also the Array-Size is not criticial. The number of patterns is  
> known beforehand.
>
> In the paper by P.Drake et al. for every pattern a normalized  
> position with a gravity concept is developed. It do not know the  
> details of this method, but from intuition is sounds complicated  
> and slow to calculated gravity and the the corresponding pattern.
>
> Chrilly
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/