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

[Peter Drake]

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/