RE: [computer-go] Pattern Matcher

[Arend Bayer <arend.bayer@xxxxxx>]

On Mon, 8 Nov 2004, Mark Boon wrote:

> My pattern-matcher does exactly that (be it in a not very sophisticated way
> I think), create an optimized decision-tree. GNU Go generates C codes from
> it's patterns. I questioned if generated C-code could get the same kind of
> optimization as my decision-tree, but didn't get a very good answer on it. I

I think Daniel Bump answered it already, but I will try again. The
generated C-code is only used to check the logical constraints, and is
just one functions for every pattern.

Probably comparable to your decision tree is our DFA matcher (written by
Tanguy Urvoy), which is descriebed in good detail in the documentation:
http://www.gnu.org/software/gnugo/gnugo_10.html#SEC130

>From the optimizations we have tried and done on this since it was first
written, I can only say that these depend a lot both on the
characteristics of the pattern database, and on the usage patterns. So I
doubt it makes much sense to compare the speed of 2 pattern matchers in
the abstract.

Personally, I think it is pretty fast. (In particular, fast enough that
nobody so far has felt the need to implement an incremental version of
it.) The drawbacks are that the DFA data is pretty large (114 kB for
479 patterns, with a tendency to grow exponentially with the number
of patterns), and it is mostly bound by memory latency. (In fact, it
seems like the only part of GNU Go for which this is the case.)

Arend

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