Re: [gnugo-devel] dfa_unsort_1_25.1

[Tanguy Urvoy]

Gunnar Farneback a écrit :
> 
> Tanguy wrote:
> > The most important to keep the incremental door open
> > is to keep a clear separation between the
> > pure pattern matching and the constrain evaluation.
> 
> This is a good idea in any case. Except for the fact that there is
> some complexity involved in storing callback data, I wouldn't mind if
> the pattern matcher, at least optionally, could return an array of
> callbacks, which the caller would be able to sort as it liked before
> processing them.

When i speak of "pure pattern matching" i mean
a process scanning the whole board and giving as answer a
list of 3-uplets (position, transformation, pattern index).

The actual version does not immediately calls the callbacks
because a goal filtering is performed before.
This is not good for the incremental scheme.


Under the assumption that a same goal is used many times,
an elegant way to deal with the goal is to precompute
a set of 3-uplets (p,t,i) satisfying its conditions.
Let's call this set "focus".

The main pattern matching loop would be

for (each (p,*,*) in focus)
   for (each (p,t,*) in focus
       dfa_scan(p,t)

for(each (p,t,i) found)
   if(p,t,i) in focus
       callback;

This "pattern focus" is compatible with the incremental matcher
an is more general than the goal.
It allow to reject immediately a lot of patterns before
falling in the deep search tree.
For example if you are sure that a stone is alive at a given position,
you can remove from the focus any 3-uplet that need an empty
intersection 
at this position.


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