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

[Chris Fant]

As long as your patterns don't contain don't-cares, you can have a
transform that can take a pattern hash input and output the pattern
hash of the rotated pattern.  Then you only have to store it once and
match it once.

On 6/16/06, David G Doshay <ddoshay at mac.com> wrote:
> 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/
>