Re: [gnugo-devel] DFA suggestions

[Arend Bayer]

Dave wrote:

> Trevor writes:
>
> > 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.

One would then have to hope that these 55 DFAs would be a lot smaller.
That might be reasonable to expect.

> > 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).

I once tried a rectangular path, and got a slowdown. Tanguy explained
he had chosen the diagonal path so that patterns with edge condition can
be excluded as fast as possible, and that seemed to be a very plausible
explanation to me. Of course it may be that you can make up for this
with your suggested speedup.

> I had been contemplating something along the lines of B.
>
> Given a speedup by reducing items in the DFA from int to short, I was
> wondering whether there would be an additional benefit from spending
> a little more effort at each node (using extra data already in the cache)
> in order to be able to skip some nodes.
Hmm, how many bytes are typically in a cache line for x86? 32? If that
is right, then this would be exactly enough to fit 16 short ints into
it, i.e. just enough to make two steps (i.e. reading two board
intersections) at once -- if there wasn't the "attribute".

Arend