[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [gnugo-devel] DFA rewrite
From: |
Tanguy URVOY |
Subject: |
Re: [gnugo-devel] DFA rewrite |
Date: |
Mon, 02 Sep 2002 15:22:54 +0200 |
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
-------------------------------------
Re: [gnugo-devel] DFA rewrite, Tanguy URVOY, 2002/09/02