Re: [gnugo-devel] arend_1_24.5: dfa 1D conversion

[Tanguy URVOY]

Arend Bayer wrote:
> Yes, I realized this when I browsed through the DFA texinfo after I had
> submitted the patch. I removed it because I would have had to rewrite the
> code that generates reverse_spiral, and I don't like to add code that
> does not get used, too likely to introduce a bug somewhere.

You are right, no need to keep dead 2D code as soon as the principle is 
well understood.

> 
> Btw, as you seem to know the DFA best: It seems to me that one could both
> save some run time and decrease the size of the DFA by changing the spiral
> path such that it always goes parallel to the edges of the board.
> (This gives a shorter path for all patterns that are quadratic or close to
> quadratic, which is true for most patterns in owl*.db.)

I chosen the spiral because it was easy to compute :)

There is probably a good optimizations possible by computing
an optimal path for each database:
The idea is to use an optimization algorithm for that purpose,
the cost function being the size of the generated DFA 
(or a runtime benchmark of the matcher).
This would be of course very costly.

Maybe we could store the path in a separate file for each pattern
database and add a special option --optimize-path to mkpat allowing some
kind of
random path optimization:

load_old_path();
best = compute_dfa_size();
for(i=0; i!= MAX_TRIES; i++)
  { 
     modify_path_randomly();
     if(compute_dfa_size() > best)
       undo_modification();
  }
save_new_path();


> 
> Do you know off-hand any reason why this should be worse than the current
> diagonal spiral, or where there might be some problem that I am missing?
> If not, I will probably try this out.

I really don't know if a square will be more efficient.
The size of the DFA is hard to predict:
The actual spiral reaches early the "exterior" of the pattern:
for center pattern this is worst than the square but for border patterns
it will be better because it separate quickly patterns and thus reduce
the 
DFA size.

The pattern matcher should separate patterns in different classes:
1 - corner patterns
2 - border patterns
3 - center patterns
4 - 2 corners patterns
5 - 3 corners patterns
And use the best path for each.


But if you are looking for a really fast pattern matcher the real
solution is
certainly the incremental DFA matcher: only the neighbourhood of the
last moves
are scanned.


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