Re: [gnugo-devel] more on dfa

[Dave Denholm]

Tanguy URVOY <address@hidden> writes:

> Arend Bayer wrote:
> > I've tried to understand how you would implement this, and I think
> > there is one point missing in your explanation in the texinfo:
> > 
> > If there is, compared to the last DFA run, one additional stone placed,
> > you want to directly jump to that state (for each starting point and each
> > spiral orientation) in which the DFA was right before it visited the
> > intersection where this stone was placed.
> 
> Yes, this is the main principle.
> 
> > However, in the current implementation, this would forget all patterns
> > that have been matched already before the respective DFA spiral reached this
> > position.
> 
> The idea was to maintain for each intersection
> the list of matched patterns ids in memory
> (we must suppress the quicksort).
> We also keep a 2 integers stack for each intersection:
> the first entry of the stack gives the reached state at a given
> deepness, the
> second entry gives the position in pattern's ids list.
> With this system, we do not forget anything: 
> we restart the scan from the last move and we update (if needed)
> the end of the list of mached patterns.
> 
> 
> > 
> > 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.
> 


Agreed - I had been wondering how to change things to make a tight inner loop
while there are no attributes.


> > 
> > These attributes could be handled by a separate list, that would be much
> > smaller because most states do _not_ have a transition to the error
> > state.
> 
> I would be happy to know the amount of states without 
> out-transitions.
> If you are right this may be a good compression of the DFA.
> Can you explain how this list works ?
> Will you use a hash table ?
> 
> 
> > I am writing this because:
> > 1. This could be implemented independently of the incremental matcher
> > (and would be a step towards it).
> 
> agreed.
> 
> > 2. It would immediately have two benefits: Save some memory, make the
> > inner-most loop of the DFA simpler (because there is no longer a need to
> > check for the attribute), and it should have good cache benefits (there will
> > be four instead of five (short-)ints per dfa state, so more dfa states
> > fit into a cache line, and we get good alignment for free).
> 
> huu ?
> We would need to check 4 integers at each step to see
> if there is an edge to the error state.
> Four tests instead of one,this is not what 
> i call a simplification!
> However this is not so important, modern processors 
> should be as fast with 1 or 4 tests.
> 
> Still i dont know how we will seek for the attributes.
> 


A picture that sprang into my mind when I read this was to use
the adjacent entry in the dfa.


So if a node has any transition to an error state, then the next
node actually contains a representation of the pattern list.


eg   42 :   44  47  0  99
     43 :    0   0 77   0
     44 :   <etc>


So node (ie dfa state) 42 says to go to state 44 if board is 0, 47 if 1, 99 if 
3.
2 is a terminal node.

So "state" 43 is not actually a state, but contains the pattern list (77 in 
this case)



The main dfa loop is something along the lines of

 while ( (next = dfa[state].states[board[spiral[k]]) != 0)
    state = next;

 /* get here => terminal node, and the the pattern list is
  * dfa[state+1].states[board[spiral[k]]]
  */




Using relative rather than absolute offsets might reduce
some work in the inner loop.

Eg if dfa could be a pointer to the current node, then


 while ( (delta = dfa->states[board[spiral[k]]) != 0)
    dfa += delta;


with delta of 0 indicating illegal transition.



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