[computer-go] Pattern Matcher

["Mark Boon" <tesuji@xxxxxxxxx>]

I translated the pattern-matcher I had from C++ to Java. This took me a bit
longer than expected. It's a fairly complex piece of code and although I
designed the original, it was implemented and refined by someone working for
me at the time. So it took me a while to understand all the details enough
again to make a proper Java translation.

Quite some work needs to be done still before this is ready to go public,
but I hope to get a little feedback here to make sure this is going in the
right direction.

The pattern-matcher currently handles patterns of Black, White, Empty or
NoCare points. Conditions are not implemented yet, but it's set up such that
these can be added later independently. As discussed before, this area tends
to be very application-specific anyway. I've also removed the requirement
that a pattern has to start at a stone, as it seems as an unnecessary
restriction to some applications of it.

It doesn't handle the 'Black-or-Empty' case, but I think it would actually
only need adding a few lines of code to make it do that if desired. Same for
'not-Empty'. I'm going to leave that for later.

The 'Pattern' class implementation is rather arbitrary, and it's stored
directly in a database using the Hibernate library. There's also a
persistent PatternGroup class to organize the patterns in groups. Storing
the pattern-data as XML is maybe more flexible, but it means I would need to
make something to parse the XML to create the Pattern instances again. Also
I wouldn't have the handy possibility of retrieving subsets using a SQL
where-clause. But in the long-run it would probably make more sense and be
more flexible when the majority of the data was in XML.

The editor is very, very rudimentary. Basically it can edit, add and remove
PatternGroups and select a group for which it will show the patterns in a
3x3 window. It allows very simple navigation through the list of patterns
and editing of a selected pattern. I will improve it on a 'as needed' basis,
but if there are people here willing to make something really nice I could
certainly use the help, as I think my spare time for the foreseeable future
will be mostly consumed by getting the matching part in shape.

At the moment it still has code in there to allow either to store the
patterns 8 times, or to match them in 8 different orientations. This is
because memory was still important at the time. Removing the last option and
always store the patterns 8 ways will simplify the code considerably and
probably make it a little faster. Since it was originally C++, some
Java-specific optimizations may still be possible, although the profiler
didn't spot anything really conspicuous.

I've done some simple tests to see how the performance would be. I took a
set of 356 patterns. They're all relatively small, 5x5 at the maximum, and
have at least one point in them for which all four neighbours are defined.
Playing through a test-set of 4500 moves and match patterns at each point of
the board (all 361) takes about 4 seconds on my 900Mhz AMD laptop. Give or
take 10% (it seems I get different results every time I run it). That makes
about 400K matches per second, which is slower than I expected considering
the relatively small set of data. Increasing the number of patterns to
several thousands or ten-thousands will probably slow it down a few times.
Adding patterns that are mostly made up of a large empty area slows it down
again, this is because the decision-graph takes many steps to find out that
a large empty area on the board does or doesn't match an almost empty
pattern. In general, bigger patterns slow it down only marginally though, as
long as they have a good 'discriminating' part in them. There's no real
restriction in size, except that it's currently set at 256 points in any
rectangle. But that's only related to how they're currently stored, it's not
a limitation of the algorithm.

The reason I focused on this particular test-set has to do with how I see
it's going to be used best. Tactical or life-and-death searches can benefit
from these kind of small patterns, and then the speed is essential. Bigger
patterns, with large empty areas are slower to match, but I think in those
cases speed is less important as they'll be used more for high-level
decision making.

The big question is if it's fast enough. There's no magic in there, so maybe
someone has something clever that works much faster. Franks pattern-matcher
appears to be faster, but it doesn't allow NoCare points, which doesn't work
for me. There's little point in putting in a lot of work to get this to a
level I'm comfortable with to publish if there are already known methods
that work much faster. Is there any comparable data available? I wouldn't
mind putting out a $1,000 reward for anyone who can show or make something
that's an order of magnitude faster. I know it's not a lot, but then again
I'm not keeping it for myself, and maybe it's enough to stimulate some
clever minds to come forward with something cool.

    Mark Boon






_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/