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

["Anders Kierulf" <anders@xxxxxxxxxxx>]

> > Why not test the distance of Y to the edge before even starting to 
> > check whether all the points in the spiral match?
> 
> Because with DFA you match all patterns at once.  You cannot filter
> out patterns in advance, you just get a list of matching patterns.

You can filter patterns in advance by creating a separate DFA for each
distance of the anchor point to the edge. You're then matching fewer
patterns, and so each match should be faster. (The worst-case is still the
same, but the average case should be better.) Of course, you're wasting
memory because all the non-edge patterns are repeated for each DFA.

You could also create a separate DFA for the non-edge patterns and then test
both the non-edge and the distance-specific DFA to get all the matches.
Might still be faster than using a single DFA, but not clear.

Anders Kierulf
www.smartgo.com


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