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

[Chaslot G (CS)]

> 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.

Last year, together with Bruno Bouzy, we published an article in which
we store the 8 orientations of one pattern. In this paper you will also
find several ideas, which I hope you will like.

It can be found at this address, on the website of Bruno Bouzy:
http://www.math-info.univ-paris5.fr/~bouzy/publications/bouzy-chaslot-ci
g05.pdf

I think you underestimate the number of patterns that have to be stored.
In Indigo (Bronze Medal in the Olympiad this year on 19*19), the number
of automatically learnt patterns is about 100,000. And this can still be
increased significantly (cf the paper).

Storing 1 pattern or 8 patterns really depends on the context: number of
patterns, memory available and frequency of the pattern matching...

Best,

Guillaume


-----Original Message-----
From: computer-go-bounces at computer-go.org
[mailto:computer-go-bounces at computer-go.org] On Behalf Of Chrilly
Sent: Friday, June 16, 2006 10:14 AM
To: computer-go
Subject: [computer-go] Rotate the dog or the tail? 

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/