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

[Martin Mueller <mmueller@xxxxxxxxxxxxxx>]

> As to edge detection: my pattern-matcher currently does the check for 
> edges
> after the fact, when the DFA reaches a leaf in the matching process. 
> As Eric
> Boesch pointed out here a while ago though, it's possible to store any
> discriminating feature in the DFA you like. So the optimal strategy is 
> to
> insert nodes in the DFA that do the edge detection at the point where 
> this
> edge feature becomes the most discrimitating feature of the (subset of)
> patterns you try to store. I haven't implemented anything like that yet
> though. I would first want to get an idea of the speed-gain it would 
> give,
> it's not obvious to me the gain would be very large. Checking on a
> black-white-empty feature always splits the set in three, and I don't 
> think
> an edge feature can beat that very often.
This sounds very similar to what my matcher is doing. It uses a tree to 
do a 4-way splitting on the value of a particular point: Black, White, 
Empty, or dontCare. Each leaf node in the tree is either a candidate 
pattern or NIL. For building the tree, there are some heuristics to 
select the best, "most-splitting" index in the pattern map. It looks at 
the subset of patterns that can still match giving the comparisons so 
far, then maximizes an evaluation function. The ideal case is that 1/3 
of patterns is black, 1/3 white, 1/3 empty, and 0 dontCare at the test 
point. Each possible point is evaluated and the best is chosen.

This way, you can adapt to the particular input data. I also started 
out with some kind of spiral, but found that this dynamic selection of 
test points is faster.

There is a whole bunch of optimizations you can do on top of the basic 
tree structure. It is all briefly described in my PhD thesis.
http://www.cs.ualberta.ca/~mmueller/publications.html

A disadvantage (or rather, a trade-off) of this method is that you only 
get candidate patterns. At the leaf of the tree you have looked only at 
a few points within the pattern. So you need a final comparison of the 
whole pattern map against the board. But since most patterns are small, 
this takes only a few 32-bit operations (or soon, even fewer 64 bit 
ops)

	Martin

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