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

[Don Dailey]

Of course the issue is the speed vs memory tradeoff.   My question is
how much does it degrade the performance of Many Faces, Goliath, or
Orego?   

My guess is that Many Faces would be doing it if it was much of a
performance benefit, so presumably it doesn't spend much time on pattern
matching (or there are so many patterns that it's imperative to be
stingy on memory.)

So it comes down to what percentage of the total execution time of your
programs is spent finding these patterns and how much performance do you
give away by doing it the more memory efficient way.     And of course
does your program use so much memory that it's critical to worry about
this.

- Don



On Sat, 2006-06-17 at 07:41 -0700, Peter Drake wrote:
> That's what we're currently doing with Orego.
> 
> On Jun 17, 2006, at 12:09 AM, David Fotland wrote:
> 
> > 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/
> >>
> >
> > _______________________________________________
> > computer-go mailing list
> > computer-go at computer-go.org
> > http://www.computer-go.org/mailman/listinfo/computer-go/
> 
> Peter Drake
> Assistant Professor of Computer Science
> Lewis & Clark College
> http://www.lclark.edu/~drake/
> 
> 
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/