Re: [gnugo-devel] DFA rewrite

[Tanguy URVOY]

Tanguy URVOY wrote:
> This should be tried.

However, some patologic cases may induce
an horrible state explosion.

For example the pattern

.
X

matched everywhere on a 19x19 board
requires a 2^20 state DFA.


We need a good compression algorithm !
Using one DFA by intersection 
is a possible compression.
Without optimization we get a worst case
(19^2*(19^2-1))/2 complexity.
Incremental optimization
(only scaning around the last move)
should reduce this complexity to
almost nothing.

The first step to any modification is to write a clean 
interface with the engine.


-- 
-------------------------------------
Tanguy Urvoy http://www.turvoy.fr.st
-------------------------------------