Re: [gnugo-devel] DFA suggestions

[Tanguy URVOY]

Heikki Levanto wrote:
> 
> On Mon, Sep 23, 2002 at 11:22:54AM +0100, Dave Denholm wrote:
> > Eg  Having matched string 'X..O.X', report a hit against pattern 42, then
> > advance -1 steps in the spiral and try the next node.
> 
> I haven't studied the DFA thing at all, but I have been thinking that the
> pattern matching could possibly be more effective.
> 
> For the first, the DFA follows always the same path. It ought to be possible
> to choose (at compile time) the most effective point to test, so as to
> eliminate the most patterns if the test fails. If these tests can also be
> off-board tests, we should be able to quickly skip patterns that can not be
> at a given point at all.
> 
> Unfortunately I do not have the time to code this, nor enough experience in
> pattern matching to say if this is likely to give real-life benefits.
> Comments?

One of the most important features of DFAs is their
determinism: alway use the same path is necessary to preserve 
this determinism.
A good solution is to use one different DFA for each intersection 
and one path for each DFA but we may also decide to use partially
deterministic 
automaton to save memory.
There is a lot to do in pattern matching, 
when my phd will be written maybe...

Tanguy


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