[gnugo-devel] DFA suggestions

[Trevor Morris]

In a recent posting, someone mentioned that it's a shame that
the DFA has to go through many repetitive OFF_BOARD pos'ns.

CONCEPT A:
My first thought is to generate one DFA per point, so the boundaries
would be known at DFA compile time.  This would remove the 
OFF_BOARD state, and require (n=boardsize):
     ((n+1)/2 + ... + 3 + 2 + 1)
       =  (n+1)/2 x ((n+1)/2 + 1) / 2 
       = (n^2 + 4n + 3) / 8
       [ 15 is n=9, 55 if n=19 ]
different DFAs.  These DFAs, I envision would include all pattern
rotations.

CONCEPT B:
The other idea would require re-ordering the path through the DFA.
Rather than the current diagonal path, use a rectilinear spiral like:
(start in the center, then alphabetically a-z).
 utsrq
 vgfep
 whado
 xibcn
 yjklm

Now, if f is on board, and g is of board, it is guaranteed
that h,i, and j are also off board, so it's simple to warp
forward to k.  Two changes would be required in the DFA code:
 - DFA compiler: pre-calculate the jump from g to k, for
example, removing 3 states.
 - Inner DFA matchpat loop: When going off board, skip ahead
the appropriate number of guaranteed off board steps (the same
number that the compiler has conveniently removed ahead of time).


Thoughts?

-Trevor