Re: [gnugo-devel] DFA rewrite

[Arend Bayer]

On Sun, 1 Sep 2002, Evan Berggren Daniel wrote:

> 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.

That's right (also, it stores them all only for one orientation, and
then walks through the board in each of the 8 possible orientations).

> 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.

Hmm, unfortunately I'd assume this estimate is unreasonable. Look at
the output of mkpat:

./mkpat -D -m -b owl_attackpat < ./owl_attackpats.db >owl_attackpat.c
---------------------------
dfa for owl_attackpat
size: 355 kB for 300 patterns
---------------------------

./mkpat -D -m -b owl_vital_apat < ./owl_vital_apats.db >owl_vital_apat.c
---------------------------
dfa for owl_vital_apat
size: 21 kB for 50 patterns
---------------------------

./mkpat -D -m -b owl_defendpat < ./owl_defendpats.db >owl_defendpat.c
---------------------------
dfa for owl_defendpat
size: 692 kB for 420 patterns
---------------------------

So you see that the size of the DFA (prop. to the number of states) is
a highly non-linear function of the number of patterns.

I think Trevor once wanted to try out how storing all possible
orientations of each pattern into the DFA affects it's size and runtime.
(This would be an intermediate speed-size trade-off similar to the one
you are suggesting.)

Trevor, did you actually try this?


Arend