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

[Paul Pogonyshev <pogonyshev@xxxxxxx>]

Anders Kierulf wrote:
> Question: When checking the spiral of points around an anchor, you probably
> repeat that for all symmetries? Or do you include the symmetric patterns in
> the DFA?

We have a single DFA, which is matched 8 times, once for each symmetry
transformation.  We tried to build pre-rotated DFAs, but they turned out
to be so huge, that they were not worth it.

> Either way, if you're just testing patterns along an edge, you
> could avoid some of those symmetries?

Yes, but this requires the split by edge distance you described.  Maybe such
split is really a good idea.

Unfortunately, one cannot hope for more than some 2--3% of speedup on it with
GNU Go: last time I checked DFA matching took less than 10% runtime.  2--3% is
a worthy speedup of course, but not large enough to make me want implement
edge-distance-split right now...  :(  Maybe someone else will voluntier.

Paul

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