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

[David Fotland]

Many faces spends very little time on pattern matching, perhaps 2 percent,
since it is only used for full board move generation.  Tactical move
generation is all hand crafted C decagons trees.  

When the pattern code was written the whole program still had to fit in 600
KB to run under DOS, before Windows 95 existed :(  So memory usage for
patterns was critical.  That's why the joseki database was encoded in about
10 bits per move.

I don't lose any performance for being memory efficient.  It just means
keeping 8 copies of the board bitmap.  Updating the board bitmap when a move
is made takes no time.

David

> -----Original Message-----
> From: computer-go-bounces at computer-go.org 
> [mailto:computer-go-bounces at computer-go.org] On Behalf Of Don Dailey
> Sent: Saturday, June 17, 2006 4:26 PM
> To: computer-go
> Subject: Re: [computer-go] Rotate the dog or the tail?
> 
> 
> 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/
> 
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org 
> http://www.computer-go.org/mailman/listinfo/computer-go/
>