Re: [gnugo-devel] DFA matching in Gnugo

[Arend Bayer]

Hi Mike,

> I would like to use the DFA matcher in gnugo, but it seems considerably 
> tied to the implementation of gnugo and it doesn't support 
> adding/subtracting patterns w/o rebuilding the whole DFA, which should be 
> possible at least in the simple cases.  I was wondering if you had any 

I don't think there is any standalone DFA code availabe.

I guess there should not be a problem with the DFA matcher itself (in
the file engine/matchpat.c).
You will have to make some hacks to the DFA built: The DFA built works in
a couple of steps:
<datase>.db ---mkpat.c--> <database>.c ---compiler--> object file that
gets linked with gnugo.

If you want to have realtime modification of the DFA, you will have to
surpass the <database>.c step. This should not be difficult, as the internal
format of the DFA in mkpat.c (before it gets exported into the .c-file) is
the same as in the object file (if I remember correctly). If you do this,
then it will be easy to add patterns instantly: The DFA is actually built
by incrementally adding pattern after pattern.
However, to remove a pattern you will have to add some code. You will
have to traverse the DFA according to the pattern in question, and look
for any unnecessary branches that could get cut off. This might be
time consuming.

> DFA-generators/DFA matching code that would be more standalone and would 
> allow simple addition of patterns to the DFA.  Alternatively, I would also 
> appreciate any additional documentation for the DFA matching in gnugo, as 
> the main manual treats it rather lightly.
I am afraid there is, as far as I know, not more documentation than in
the manual (and the comments in the code).

Good luck with your program,
Arend