Re: [computer-go] Spiral pattern matching and data structures

[Arend Bayer <arend.bayer@xxxxxx>]

On Thu, 20 Jan 2005, Peter Drake wrote:

> I read Tanguy Urvoy's paper on pattern matching in gnugo:
> 
> http://citeseer.nj.nec.com/481629.html


> A key feature of this pattern matcher is that one-dimensional patterns are
> compared against points in a spiral spreading out from the point under
> consideration.  A pattern that would normally be represented by a larger
> two-dimensional rectangle is thus simply represented as a longer
> one-dimensional string.
> 
> I'm thinking about data structures for implementing this.  Suppose we have a
> two-dimensional array of point objects, each of which has pointers to its four
> neighbors.  We can store one constant sequence storing the pointers to follow
> along the spiral, e.g.:
> 
> south, east, north, north, west, west, south, south, south, east, east, east
> ...
> 
> (we could even store several versions of this for rotation and reflection
> invariance)

Yes, that is basically what we do, with the following differences:
 - the spiral Tanguy used in GNU Go's implementation is diagnoally
 - instead of storing the direction at each point, we store the offset 
	to the starting position
 - which is particularly effective since I changed this to a board
	representation by a one-dimensional array (as usual)
(i.e., there are no pointers involved).

> Here's my question:  what happens at the edge of the board? 

> One approach is to put the "real" board in the center of a much larger array
> of off-board points, but this is unsatisfying because of the amount of memory
> involved.  Does anyone have a better approach?  What does gnugo do?

We use this bigger board. Ours is 3*19 * 3*19, a bit bigger than we
would need, but that's still small enough to fit into the L1 cache on
most processors I would guess.
The bottleneck of the DFA algorithm is the memory access to the actual
DFA, anyway.

Arend


_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/