Re: [gnugo-devel] pattern-based reading spinoffs (27.7)

[Arend Bayer]

> Here's an extract of the comments from the tree-based pattern
> matcher.  For owl, it's about as fast as the DFA, though I've tested
> it very very little outside of the reading-based pattern code,
> where it gives a 20% improvement:
>  * Conceptually, each node of the tree corresponds to either
>  * ATT_dot, ATT_X, or ATT_O, with an x and y coordinate relative
>  * to the anchor.  When the pattern matcher is run, if 
>  * board[POS(node.x, node.y)] == node.att, then proceed to the
>  * next node.  If you find a node with a match_node pointer,
>  * then a pattern has matched (with a given orientation).

Maybe I don't understand this. This sounds to me exactly like a different
description of the DFA. Can you explain the difference more clearly?

Also note that it is very easy to improve the speed of the DFA drastically
at the cost of using more memory. If you add all 8 different orientations
(for a completeley symmetric pattern, less for a pattern with symmetries) to
the DFA, you can avoid to have to run the DFA 8 times (as it currently does).
This will probably give too huge DFAs for the owl_*.db files (and that's why
Tanguy didn't implement this I assume), but for read_attack.db it should be
no problem.

(The change should be quite straightforward. Just use all 8 precomputed
spirals when entering the pattern into the DFA (do symmetry check here!),
store the orientation, but call scan_for_patterns only with l=0.)

I would not expect an improvement of factor 8 here, but anything between
2 and 5-6 would seem possible.

Arend