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

[Paul Pogonyshev <pogonyshev@xxxxxxx>]

Arend Bayer wrote:
> > >  - 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?

An array of chars, actually.

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

This board is only used for DFA pattern matching, for other purposes we
use a "sane" 19x19 board with a little padding for off-board values.
Copying 19x19 chars per node is nowhere a speed problem.  The DFA match
itself will take much much more time.

Paul

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