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

["Mark Boon" <tesuji@xxxxxxxxx>]

> -----Original Message-----
> From: computer-go-bounces@xxxxxxxxxxxxxxxxx
> [mailto:computer-go-bounces@xxxxxxxxxxxxxxxxx]On Behalf Of Martin Mueller
> Sent: Friday, January 21, 2005 0:36
> To: computer-go
> Subject: Re: [computer-go] Spiral pattern matching and data structures
>
>
> 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)
>

Indeed, this is exactly how it works.

This last step at the leaf can get expensive if a large empty area remains
and is tested against an almost empty board. So for some sets of patterns it
works more efficiently than others.

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