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

[Arend Bayer <arend.bayer@xxxxxx>]

On Thu, 20 Jan 2005, Peter Drake wrote:

> On Thursday, January 20, 2005, at 11:22  AM, Arend Bayer wrote:
> 
> > Yes, that is basically what we do, with the following differences:
> >  - the spiral Tanguy used in GNU Go's implementation is diagnoally
> 
> Is there any particular reason for this choice?

None except it turned out to be faster :) The reason depends on our
pattern database: There are many patterns like this:

..OO             reverse sente sagari
.OYX
.*..
....
----

that only match somewhere at the edge, and the diagonal spiral tends to
find out faster whether the anchor ('Y') has the right distance to the
edge.

> >  - 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).
> 
> Out of curiosity, an array of what?  Are there point objects (or structs, or
> whatever) or is it something simpler?

Just ints with value 0 (empty), 1 (white), 2 (black) or 3 (off-board).
What else would you need?

> > 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.
> 
> If copying the board is needed in any global search, is multiplying the size
> of the board structure by 9 a problem?

I have never seen it on profiles, so no.

Arend

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