[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## [gnugo-devel] DFA rewrite

**From**: |
Evan Berggren Daniel |

**Subject**: |
[gnugo-devel] DFA rewrite |

**Date**: |
Sun, 1 Sep 2002 00:38:46 -0400 (EDT) |

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

**[gnugo-devel] DFA rewrite**,
*Evan Berggren Daniel* **<=**