Re: [gnugo-devel] DFA rewrite

[Tanguy URVOY]

Evan Berggren Daniel wrote:
> 
> OK, I haven't looked at code more than a tiny bit, but all this discussion
> about DFA speeds got me to wondering.  I think the DFA pattern matcher can
> be implemented more effectively than it currently is.


Hello,

Yes, the DFA matcher can be implemented more effectively with a 
global scan !!
It was more easy to implement an "anchor based" DFA pattern matcher
to keep some compabibility with the old pattern matcher.
Implementing the global DFA matcher is lot of work
but i am sure it can be done
(And i would be happy to help you as much as possible).


Interface:
----------
The DFA matcher should be more separated from the rest of gnugo
let me propose you an interface:
A "match" is a 3-uplet (pattern_id, position, transformation).
The main objet manipulated is a "match set" whih is a set of such
3-uplets.

The matcher is a function
match_set_t dfa_matcher(dfal_t dfa_list, match_set_t goal, board_t
board)
which takes as argument a dfa list, a subset goal and a board position 
and return the set of matches that are in goal.

Any other work like constraints solving should be
considered separately.
The old goal system should be precomputed by filtering
the pattern sets BEFORE reading.
The use of match sets allows us to implement
incremental pattern matching.


Size consideration:
-------------------
1) The actual version use a special symbol for "OUT BOARD" and loose
a lot of memory (and time) in scanning the OUT BOARD positions.
A global scanner would not need that.

2) The size of the stucture may be controlled by using
a list of DFAs and a constant MAX_DFA_SIZE to control the size of each
DFA.

If DFA_MAX_SIZE is big then only one huge dfa will be produced,
if DFA_MAX_SIZE is very small then one small DFA will be built for each
pattern.



The principle:
--------------

1) in mkpat: Build one DFA for each possible match of each pattern.


+-------------+
|+++......+++.|
|++++.....++++|
|++.......++..|
|...+........+|
|.............|
|........++...|
|.......+++...|
|........++...|
|......+......|
|.............|
     ...

2) use synchronized product to combine this DFAs into bigger ones.
We may combine DFA's by pattern_id, position or transformation.
The easier is by pattern_id but position is also a good criterion.



> So, my suggestion is to build the DFA to match against the entire board,
> using a much larger state table but a potential speed increase of a factor
> of ~30 (the number of squares in the largest pattern).  I think this trade
> off is worth it.
> 

There are a lot of patterns with board constraint this reduce
the number of possible matches for a given pattern.


> The only worry would be that state generation would be slow, but this is
> not a problem.  For testing compiles (eg pattern database tuning), the old
> DFA could be used, and for release compiles long compile times are ok.

Incremental DFA compilation is also a solution:
store the dfas into binary files and only rebuild
at need.

> 
> I would like to undertake this if it seems like a useful and workable
> idea.  I can describe my scheme for generating a compact state table in
> more detail if needed.

Ok give your description :)


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