Re: [gnugo-devel] DFA rewrite

[Inge Wallin]

Evan Daniel wrote:
> 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.

This is a good idea, but there is a little problem.

If you do a profile of the running engine, you can clearly see that
pattern matching itself takes less than 10% of the run time and
reading takes almost 90%.  All this reading comes from constraints in
the pattern, i.e. once a pattern has matched some reading is done to
see if it really applies.

So if you get a factor 30 speedup of the pattern matching, the maximum
you will get overall is 9,7% (97% of 10%).  You have to think if this
is worth it, considering the large extra use of memory that the
gigantic DFA will incur.

I think that the biggest gain will come from reducing the overall
number of patterns that are matched and also making cheaper
constraints. 

(Note: The exact percentages above may be somewhat off since they are
quoted from memory.)

         -Inge