[gnugo-devel] dfa optimizer

[pogonyshev]

i has been experiencing problems with my phone line and
was unable to send this from home -Paul
---------------------------------------------------------------

here we go :)

fortunately, the bug i introduced in intermediate stages didn't influence
size optimization much :) although the results are worse this time, they
are still very good. new function dfa_rotate_string() which i broke off
from dfa_add_string() takes noticeable time (several seconds at
optimization startup), but i'm too tired to speed it up right now.

- new dfa builder implemented in dfa.c
- dfa size reduction algorithm implemented
- dfa transformation hints (.dtr) files added to repository

dfa size reduction:
                           before           after       iterations
owl_defendpats.db       334k (34049)    105k (10592)      3x10000
owl_attackpats.db       242k (24700)     81k  (8194)      2x10000
owl_vital_apats.db       11k  (1126)      8k   (868)        10000
aa_attackpats.db          3k   (352)      2k   (242)         5000

total                   590k (60227)    196k (19896)        65000

still 3 times size reduction :) all results are with 3.3.17-pre-1.

i haven't measured speed, but i'm quite certain that if it has changed,
then to the better side ;)

currently i'm running regressions. the only changes so far (trevord.tst):

./regress.sh . trevorc.tst
130 unexpected FAIL: Correct 'H9', got 'H6'
1440 unexpected PASS!

i assume that they are accidental. most likely caused by different
patterns sequence after sorting.

optimizer interface looks this way: for each dfa database we have a small
text file which stores suggested variations (transformations) for each
pattern. these files should be added to cvs. i chose `.dtr' suffix (dfa
transformations) but you can change it to anything you like. when you want
to use these stored hints, you supply them with -t option to `mkpat', e.g.

  ./mkpat -D -m -b -t owl_defendpats.dtr owl_defendpat <owl_defendpats.db\
        >owl_defendpat.c

when you want to update hints, run it like

  ./mkpat -d 10000 -m -b -t owl_defendpats.dtr owl_defendpat
<owl_defendpats.db

it will first read the hints from the .dtr file (if it exists), then try
to optimize dfa and store updated hints back to the .dtr file. 10000 is
the number of iterations (use anything you like here). if you want to
optimize from scratch (transformation 0), simply delete the .dtr file.

we may also add `make' targets for dfa optimization. but i'd not make them
dependent on the databases. otherwise, any change to a database will cause
an optimizer run, which takes considerable time. we should just run the
optimizer once a database has accumulated quite a few changes. and we
certainly should have a long optimization session before 3.4 release ;)

when a .db file is edited, `mkpat' still tries to use the old hints. the
degree of its success depends on what exactly has happened to the database.

if some patterns has been modified and some new has been added, it will (at
least should) do well - new patterns will use transformation 0, others will
keep the optimized transformations.

if some patterns has been deleted, renamed or moved, hints for these
patterns and all patterns which follow them will be lost. in this case
you may either edit the corresponding .dtr file (deleting, editing or
moving corresponding lines), or rebuild it from scratch.

optimizer doesn't take too much time (less than 15 minutes to achieve the
level of .dtr files i submit). updating instead of building from scratch is
much faster, of course.

i tried a completely deterministic algorithm in addition to the current one,
but it turned out to be less effective. actually, the current algorithn is
also deterministic, since gg_rand() is. in fact it should even be platform-
independent.

the current algorithm was tuned against non-bugfixed dfa strings, but i
doubt the fix changed its effeciency significantly. in any case, this can
be improved later.

attached tarball contains the patch (changes to dfa.c, dfa.h, mkpat.c and
Makefile.am) and four .dtr files.

as usually, we'll need a vc repair patch (though vc must keep building even
without one, just its dfas will be non-optimized).

Paul

-- 
+++ GMX - Mail, Messaging & more  http://www.gmx.net +++
NEU: Mit GMX ins Internet. Rund um die Uhr für 1 ct/ Min. surfen!

patch.tar.gz
Description: application/gzip-compressed