[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


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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]