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

[Trevor Morris]

Yes, I believe you've got it right.  They are very similar.
A major difference is that the tree implementation doesn't use 
a fixed path.

Another noticable difference is that the db files are processed
very quickly.  However, the c code it generates compensates by 
compiling extremely slowly.

At the bottom of the message, I show in some detail the
read_attack tree.


>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.
This is a very interesting idea.  I agree that it might provide a
very nice speed increase.  It might very well blow away this tree
algorithm, as it's complexity o(size of pattern) seems to be much
better than with the tree algorithm.  I'm not certain of this, though.

>(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.)
This is just what the tree implementation does.



There are always exactly 2 base nodes in the tree.
These correspond to the struct graph_node elements.  
Here is human-readable output of the graph_nodes up to depth 3 
(where there are already a lot of patterns matched).

Below:
  GN[att=*, x=*, y=*] refers to a struct graph_node.
  P[PatName, orientation] indicates that this pattern matches.
  matches[*] is the offset into the matches array - not too interesting
     for this discussion.

When walking the tree, first, does board[m+0][n+0] == ATT_X?
If so, recursively walk all of the child nodes (from {X,0,0},
there are 6 such nodes), check if board[m+GN.x][n+GN.y] == GN.att
Any time there is a matches[] list of matched patterns, if the
graph_node matches, the pattern has matched, and the callback is
immediately called.

After walking the graph, all patterns in all orientations have
been matched.

GN[att=X, x=0, y=0]
  GN[att=., x=1, y=0, matches[1]: P[RA000a, 1]P[RA302, 3]P[RA302, 4]]
    GN[att=O, x=0, y=1]
    GN[att=O, x=0, y=-1]
    GN[att=X, x=0, y=1]
    GN[att=X, x=0, y=-1]
    GN[att=., x=1, y=-1, matches[29]: P[RA998, 1]]
    GN[att=X, x=1, y=-1]
    GN[att=O, x=2, y=0]
    GN[att=X, x=1, y=1]
    GN[att=., x=2, y=0, matches[67]: P[RA997, 1]]
    GN[att=., x=1, y=1, matches[69]: P[RA998, 6]]
  GN[att=., x=0, y=-1, matches[73]: P[RA000a, 2]P[RA302, 0]P[RA302, 5]]
    GN[att=O, x=1, y=0]
    GN[att=O, x=-1, y=0]
    GN[att=X, x=1, y=0]
    GN[att=X, x=-1, y=0]
    GN[att=., x=-1, y=-1, matches[101]: P[RA998, 2]]
    GN[att=X, x=-1, y=-1]
    GN[att=O, x=0, y=-2]
    GN[att=X, x=1, y=-1]
    GN[att=., x=0, y=-2, matches[139]: P[RA997, 2]]
    GN[att=., x=1, y=-1, matches[141]: P[RA998, 7]]
  GN[att=., x=-1, y=0, matches[145]: P[RA000a, 3]P[RA302, 1]P[RA302, 6]]
    GN[att=O, x=0, y=-1]
    GN[att=O, x=0, y=1]
    GN[att=X, x=0, y=-1]
    GN[att=X, x=0, y=1]
    GN[att=., x=-1, y=1, matches[173]: P[RA998, 3]]
    GN[att=X, x=-1, y=1]
    GN[att=O, x=-2, y=0]
    GN[att=X, x=-1, y=-1]
    GN[att=., x=-2, y=0, matches[211]: P[RA997, 3]]
    GN[att=., x=-1, y=-1, matches[213]: P[RA998, 4]]
  GN[att=., x=0, y=1, matches[217]: P[RA000a, 0]P[RA302, 2]P[RA302, 7]]
    GN[att=O, x=-1, y=0]
    GN[att=O, x=1, y=0]
    GN[att=X, x=-1, y=0]
    GN[att=X, x=1, y=0]
    GN[att=., x=1, y=1, matches[245]: P[RA998, 0]]
    GN[att=X, x=1, y=1]
    GN[att=O, x=0, y=2]
    GN[att=X, x=-1, y=1]
    GN[att=., x=0, y=2, matches[283]: P[RA997, 0]]
    GN[att=., x=-1, y=1, matches[285]: P[RA998, 5]]
  GN[att=O, x=1, y=0]
    GN[att=O, x=0, y=1]
    GN[att=O, x=0, y=-1]
  GN[att=O, x=-1, y=0]
    GN[att=O, x=0, y=-1]
    GN[att=O, x=0, y=1]
GN[att=O, x=0, y=0]
  GN[att=X, x=0, y=-1]
    GN[att=., x=1, y=-1, matches[317]: P[RA101, 0]P[RA202a, 7]]
    GN[att=., x=-1, y=-1, matches[320]: P[RA101, 5]P[RA202a, 2]]
    GN[att=., x=0, y=-2, matches[323]: P[RA101a, 0]P[RA101a, 5]P[RA202, 
2]P[RA205a, 0]P[RA205a, 5]]
  GN[att=X, x=-1, y=0]
    GN[att=., x=-1, y=-1, matches[329]: P[RA101, 1]P[RA202a, 4]]
    GN[att=., x=-1, y=1, matches[332]: P[RA101, 6]P[RA202a, 3]]
    GN[att=., x=-2, y=0, matches[335]: P[RA101a, 1]P[RA101a, 6]P[RA202, 
3]P[RA205a, 1]P[RA205a, 6]]
  GN[att=X, x=0, y=1]
    GN[att=., x=-1, y=1, matches[341]: P[RA101, 2]P[RA202a, 5]]
    GN[att=., x=1, y=1, matches[344]: P[RA101, 7]P[RA202a, 0]]
    GN[att=., x=0, y=2, matches[347]: P[RA101a, 2]P[RA101a, 7]P[RA202, 
0]P[RA205a, 2]P[RA205a, 7]]
  GN[att=X, x=1, y=0]
    GN[att=., x=1, y=1, matches[353]: P[RA101, 3]P[RA202a, 6]]
    GN[att=., x=1, y=-1, matches[356]: P[RA101, 4]P[RA202a, 1]]
    GN[att=., x=2, y=0, matches[359]: P[RA101a, 3]P[RA101a, 4]P[RA202, 
1]P[RA205a, 3]P[RA205a, 4]]
  GN[att=., x=0, y=1, matches[365]: P[RA102, 0]]
    GN[att=X, x=1, y=0]
    GN[att=X, x=-1, y=0]
  GN[att=., x=1, y=0, matches[377]: P[RA102, 1]]
    GN[att=X, x=0, y=-1]
    GN[att=X, x=0, y=1]
  GN[att=., x=0, y=-1, matches[389]: P[RA102, 2]]
    GN[att=X, x=-1, y=0]
    GN[att=X, x=1, y=0]
  GN[att=., x=-1, y=0, matches[401]: P[RA102, 3]]
    GN[att=X, x=0, y=1]
    GN[att=X, x=0, y=-1]