[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [gnugo-devel] DFA suggestions

From: Dave Denholm
Subject: Re: [gnugo-devel] DFA suggestions
Date: 23 Sep 2002 11:22:54 +0100

Trevor Morris <address@hidden> 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.
> 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.
> 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?

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.

The skip could also be used to make the DFA report more than one
pattern at a time.

Eg  Having matched string 'X..O.X', report a hit against pattern 42, then
advance -1 steps in the spiral and try the next node.

B could also allow '?' pattern elements to be skipped.

One other thing I've been mulling over : combine board values
of the points neighbouring (m,n) into some hash function. Then
use that as a starting point in the DFA (or to choose which
DFA to scan)


reply via email to

[Prev in Thread] Current Thread [Next in Thread]