Re: [gnugo-devel] more on dfa

[Dave Denholm]

Dave Denholm <address@hidden> writes:

> Dave Denholm <address@hidden> writes:
> 
> > Tanguy URVOY <address@hidden> writes:
> > 
> > > Arend Bayer wrote:
> 
> > > > 
> > > > There is a clean way to solve this problem: Instead of having attributes
> > > > for all states, we could only have attributes for those states that have
> > > > a transition into the error state. I.e., only at the very end of the DFA
> > > > spiral we generate a list of all patterns that got matched.
> > > 
> > > This is a good optimization of the DFA
> > > to put the attributes only in the states with
> > > an output transition to the error state.
> >

Well, I had a go, and have a version in which all patterns are
pushed down the tree to the terminal states. I kept the
attributes too, so I could check the two approaches against
each other.

Unfortunately, the dfa merges the tree where it can, so there
can be multiple paths to the terminal state, each picking up
different patterns.

Eg a section of owl_attackpat.c

/*  3384 */ {    0, {  3385,  3387,  3387,  -543 }},/* 
O.......................??$$$$??$x..o..x?$$$$$$$$?$$x?o$o */
/*  3385 */ {  388, {  3386,  3386,  -540,  -540 }},/* 
O.......................??$$$$??$x..o..x?$$$$$$$$?$$x?o$o. */
/*  3386 */ {  389, {  -536,  -536,  -536,  -536 }},/* 
O.......................??$$$$??$x..o..x?$$$$$$$$?$$x?o$o.x */
/*  3387 */ {    0, {  3386,  3386,  -543,  -543 }},/* 
O.......................??$$$$??$x..o..x?$$$$$$$$?$$x?o$oX */
/*  3388 */ {    0, {  3389,  -543,  -543,  -543 }},/* 
O.......................??$$$$??$x..o..x?$$$$$$$$?$$x?o$$ */

State 3386 can be reached either as

3384 -> 3385 -> 3386  - picking up attribute list 388 and 389

or

3384 -> 3387 -> 3386  - skipping list 388 

(the comment at the end is the string that reaches that state. It is clearly
wrong here because I generated it assuming the tree could not merge after
splitting.)


The -ve numbers are terminal states, but indicate the final pattern list
to use.



So I (or someone) will have to figure out how to modify the sync product
to not merge the branches, at least for paths containing different
attributes.

Might be easier to fix it up at the end by duplicating the part after
the merge point if the paths going into the merge contain different
pattern lists.


There is one other minor optimisation that can be made using the new
representation : state 3387 says to go to state 3386 if the board
contains . or X ; then state 3386 says the pattern in attribute
389 is matched, and then we don't care what happens next. But since
we can store different terminal markers, then state 3387 could just have
been

/*  3387 */ {    0, {  -536,  -536,  -543,  -543 }},/* 
O.......................??$$$$??$x..o..x?$$$$$$$$?$$x?o$oX */

since we dont have to invent a new state just to encode a matched pattern.
This says if it is . or X, finish with pattern list 536. Otherwise finish
with [attern list 534.

(Of course, if all merge points are just before terminal states like this,
 then the problem goes away.)



While I'm here, I noticed that dfa.c contains both routines used in
in the main gnugo binary and routines used only in mkpat.

Probably cleaner to split out the dfa construction routines into 
mkdfa.c 

Also, dfa.c constructs the dfa using the types used by gnugo, but there
is no particular reason why the datatypes used to build the dfa need
to match the final representation of the dfa.

dd
-- 
address@hidden          http://www.insignia.com