[computer-go] Spiral pattern matching and data structures

[Peter Drake <drake@xxxxxxxxxx>]

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)

Here's my question:  what happens at the edge of the board?  If I move 
east from a point on the east edge of the board, I will reach either a 
null pointer or perhaps some sentinel object representing all off-board 
points.  If the spiral would continue back onto the board, how can I 
follow it?

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?

Peter Drake
Assistant Professor of Computer Science
Lewis & Clark College
http://www.lclark.edu/~drake/

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