owl pattern matching speedup (was: [gnugo-devel] GnuGo 3.2 port option)

[Arend Bayer]

On Fri, 30 Aug 2002, Evan Berggren Daniel wrote:

> My understanding is that the DFA mechanism used is significantly faster
> and probably smaller if well implemented than just about anything else.
> The basic problem is that there are a *lot* of patterns, and they simply
> take a lot of space.  The best option is probably careful pruning of the
> database.  Then again, I'm not terribly familiar with it.
>
> Oh, if people think it would be feasible I might take a stab at
> hand-assembling the DFA.  I'd have to take a look at the code and find
> docs for the relevant architectures, but it shouldn't be too hard.
> Whether I can beat gcc is an open question.  How much would a speed
> improvement help, anyway?

Speed improvements are always useful. I have heard a lot of complaints
about GNU Go being too slow; so I don't think we want to slow the engine
down for a while, on the other hand we want to add features like the
experimental connection code that will need more time.

I think there is a better way to substantially speed up the owl pattern
matching: we should use matchpat_goal_anchor (introduced by Trevor for
his experimental pattern based reading code) also for the owl databases.
This would enormously reduce both the time spent in scan_for_patterns
and in check_pattern_light (both need about 4-5% of total run time,
IIRC).

(It works as follows: At the moment we try to match each pattern at each
intersection of the board, and check afterwards whether a stone of the
goal dragon is contained in the matched area. matchpat_goal_anchor
instead only starts the DFA spiral at each stone of the goal dragon.)

The work that has to be done is the following: A lot of patterns contain
two worms of the color to be attacked. However, matchpat_goal_anchor requires
that the _anchor_ is part of the goal dragon. To reproduce current
behaviour, we would have to enter these patterns twice into the pattern
database: E.g. out of D108 in owl_defendpats.db we would have to make
the two patterns (Q marking the anchor, having color O):


Pattern D108a

?..x         pull back
.X.O
XQ*.
....
....
----

:8,-,value(80)

Pattern D108b

?..x         pull back
.X.Q
XO*.
....
....
----

:8,-,value(80)


On the other hand, of some patterns we might indeed intentionally drop
one of the versions:


Pattern D119
# This is usually better than D213 when both match.

OOX??           hane to expand
..Q*.
.....
.....
-----

:8,-,value(81)

If the two worms are not connected, then * may be completely nonsense as
a saving move for the left dragon.
(There may also be many patterns where the duplication will be simply
unnecessary, because the O worms are clearly connected.)

Hence, doing this sensibly could improve both speed and correctness
of owl.

Opinions?

There would be two ways of doing the duplications of patterns as D108:
Either having it done automatically by mkpat.c (and manually adding
a 'Q' element to patterns where we don't want it). Or writing a script
that patches owl_defendpats.db (i.e., it would have to understand
connectedness of 'O' stones in the patterns); then we could afterwards
manually delete the patterns where we don't want the duplication.


Arend