Re: [gnugo-devel] DFA should be "best" NFA

[Tanguy URVOY]

Hello,

> > The best we can do is to touch memory
> > one time for each test of the board.
>
> I'd have thought that it is really only the first touch of
> each line that matters. Once it's in the cache, it's fast.

Yes, that a reason why an implementation of
a deterministic NFA should be as fast as
the actual DFA encoding.


> Localising memory accesses is a good thing. Matching in rows
> would be better than spiralling, though of course that doesn't
> work for the rotations.

My aim is more more ambicious, what i call
NFA is in fact a decision diagram
which generalize NFA.
At each state is associated the position of the
board to be read.


                X                                 O
[i,j]-------------------------> [i+1,j] ----------------------->
  |
  |
  |           X
   --------------------------> [i,j+2] ...


If you impose [i,j] to follow a unique scan path then this is an NFA,
otherwise this is a decision diagram.
Compute the optimal decision diagram is NP-complete if we dont add
any constraint but it is better to consider the problem from the most
general point of view.


> Would it be useful to revisit the approach of generating
> a transform of the whole board, and then doing the matching
> on the transformed board, rather than doing the transform
> in the spiral order array ?

Maybe we should add all 8 pattern transformations in the database to
enhance the database reduction by invariant stones (*) but this need to 
be experimented.

(*) see previous Email.


> I've been wondering on and off about how to arrange things
> to prefetch cache-lines to ensure that they are in memory
> when we come to use them.

It would be fun to use informations about the cache while builing the
NFA like in http://www.fftw.org/
(The Fastest Fourier Transform of the West).


The actual DFA algorithm has already good cache properties:
I tryied to test the it with a loop generating
a random board each time and it was worst than brute algorithm !
It became immediatly faster when I only changed 1 stone each time:
the used states tend to stay in the cache when the game goes on.


Tanguy


--
---------------------------------------
Tanguy Urvoy http://www.irisa.fr/galion
---------------------------------------