[gnugo-devel] a new dfa builder

[Paul Pogonyshev]

i have a new, quite fast dfa builder here. it isn't finished yet, but i'm
completely certain it will generate valid dfas. the reason is that it
produces dfas of identical size with the current builder (number of states
matches precisely).

it may take some days for me to get it to completely working state (i'll
need to implement a writer to .c file, a shuffler, like in the current
implementation and probably bugfix attributes generation - it can't be
checked right now and i don't even know if there are bugs).

the reason i started this is a dfa size reduction idea. currently, we add
patterns to dfa only with transformation 0. now consider this algorithm:

  we build dfa with all patterns untransformed (transformation 0).

  next, we (randomly) change transformation of some patterns, say every
  fourth pattern. we build a new dfa. if it happens to be smaller, we keep
  the (random) transformation we made, otherwise return to original
  transformations. this can be repeated several times.

note, that i haven't yet tried this scheme and i cannot predict the results
(i just hope we'll get some decent reduction). the only drawback of this
approach is that the patterns will be stored in the dfa in different
transformation than they present in database. this may lead to somewhat
confusing debug output. however, i don't think that it is very important or
inconvenient.

the new builder is several times faster than the old one and i suspect the
difference grows with the size of database. i managed to build a prerotated
dfa of owl_attackpats.db in a minute. it contained over 3 million states.
the time it takes to buld dfa for owl_defendpats.db 1000 times is about 45
seconds. i haven't yet profiled the builder so the time will probably be
reduced once i find the bottle necks.

i need to know how you would prefer the new builder to be plugged into
mkpat.c once it is completed. i can see four ways:

  - the new builder and the old one are selectable with an option in
    `configure' script. the safest variant, but results in ugly mkpat.c.
  - the new builder is made the default, the old builder is disconnected
    from mkpat.c but kept in dfa.c for emergency case ;)
  - the new builder is added to dfa.c, but is not connected to mkpat.c
    (this one is tough since it will be hard to test the new builder).
  - the old builder is replaced with the new one (somewhat risky).

btw, the new builder currently takes about 500 lines in dfa.c and 100 lines
in dfa.h. no comments yet. the function which does non-trivial work takes
less than 100 lines. the code is written in object-oriented way and looks
quite readable to me.

Paul