[gnugo-devel] DFA rewrite

[Evan Berggren Daniel]

OK, I haven't looked at code more than a tiny bit, but all this discussion
about DFA speeds got me to wondering.  I think the DFA pattern matcher can
be implemented more effectively than it currently is.

My understanding is that the DFA currently only matches patterns at a
specific location, and is then tried for each square of the board,
generating a list of all patterns that match and where.

So, my suggestion is to build the DFA to match against the entire board,
using a much larger state table but a potential speed increase of a factor
of ~30 (the number of squares in the largest pattern).  I think this trade
off is worth it.

I think the state table would, if built carefully, be on the order of 5-50
MB.  There is some justification for this that I can go over if people
think that's an unreasonable estimate.

The only worry would be that state generation would be slow, but this is
not a problem.  For testing compiles (eg pattern database tuning), the old
DFA could be used, and for release compiles long compile times are ok.

I would like to undertake this if it seems like a useful and workable
idea.  I can describe my scheme for generating a compact state table in
more detail if needed.

Thanks

Evan Daniel