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

[David Fotland]

It saves a lot of memory to keep 8 copies of the board and one copy of the
patterns.  That's what I do, and what Goliath did.

David

> -----Original Message-----
> From: computer-go-bounces at computer-go.org 
> [mailto:computer-go-bounces at computer-go.org] On Behalf Of 
> David G Doshay
> Sent: Friday, June 16, 2006 9:02 AM
> To: computer-go
> Subject: Re: [computer-go] Rotate the dog or the tail?
> 
> 
> 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/
> 
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org 
> http://www.computer-go.org/mailman/listinfo/computer-go/
>