[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [gnugo-devel] DFA should be "best" NFA
From: |
Tanguy URVOY |
Subject: |
Re: [gnugo-devel] DFA should be "best" NFA |
Date: |
Mon, 27 Jan 2003 18:16:40 +0100 |
User-agent: |
Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.0.2) Gecko/20021120 Netscape/7.01 |
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
---------------------------------------
- [gnugo-devel] yet another one speed optimization, Paul Pogonyshev, 2003/01/26
- Re: [gnugo-devel] yet another one speed optimization, Arend Bayer, 2003/01/27
- [gnugo-devel] DFA should be "best" NFA, Tanguy URVOY, 2003/01/27
- Re: [gnugo-devel] DFA should be "best" NFA, Heikki Levanto, 2003/01/27
- Re: [gnugo-devel] DFA should be "best" NFA, Gunnar Farneback, 2003/01/27
- Re: [gnugo-devel] DFA should be "best" NFA, Heikki Levanto, 2003/01/27
- Re: [gnugo-devel] DFA should be "best" NFA, Tanguy URVOY, 2003/01/28
Re: [gnugo-devel] yet another one speed optimization, Paul Pogonyshev, 2003/01/27