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

[Tanguy URVOY]

Hi,

I still not finished to write my phd :(
But soon I will be free to help you again :)
I have (too?) many ideas to speedup pattern matching.


> Yes this is bad, and the problem will increase as processor speeds go up
> (as scan_for_patterns is mostly memory latency bound, whereas the rest
> of the code is mostly CPU bound). On what processor/RAM is this?

The best we can do is to touch memory
one time for each test of the board.
This is what would do a global DFA...
But a global DFA is too large to fit in memory :(


The actual algorithm use a generic DFA for each
position of the board to save memory.
But I still believe that the pattern matching problem
is global.


What about a global "at best" NFA ?

An NFA is a non deterministic Finite state automaton:
we may have twice the same output for the same state.

               X
[1]----------------------->[2]
 |
 |         X
  --------------------> [3]


To simulate an NFA when we read X on the board from
state [1] we have to launch one scan for
each X output.

An NFA with only one output transition for each letter is a DFA.
A global NFA for which each state except the first is deterministic
correspond to the actual (local) DFA algorithm.
The brute force algorithm is similar to an NFA
linking one DFA for each pattern of the database.



Let me propose you a solution
(maybe the fastest Go pattern matcher of the West ?)

1) use global pattern matches instead of generic patterns.
2) rebuild a "this game dedicated" pattern matcher at runtime.


This rebuild could be implemented with
many optimizations parameters :

- the size of the board
- the stones that (as we know) will never be removed.
- the moves that will never be played.


These parameters allows us to remove
many tests (and many patterns matches) from the database before
building the NFA.
We can do "the best we can" to build
the NFA respecting a given memory constraint.
This NFA may become fully deterministic
for some local reading.


This (probably costly) rebuild can be done at different stages
of the game or while the opponent is thinking.


Tanguy


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