[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

RE: [computer-go] Pattern Matcher

Hashing fixed-shape patterns is good when you only have a handful of
fixed shapes, and even better when those fixed shapes nest inside each
other. Space performance is O(# patterns) in both cases, and time
performance is O(total size of all unique shapes) or O(size of biggest
shape) depending on whether the patterns nest or not. But this is not
good general-purpose pattern matching -- it is only relatively fast
when there are many more patterns than there are unique pattern
shapes. (A pattern's shape is the set of intersections that the
pattern cares about.)

Mark rightly emphasizes using realistic test data. It's reasonable to
require the matcher to handle random board patterns, but it's not
reasonable to optimize the matcher for such input. If you have a
million patterns each consisting of a random value (white, black,
empty) assigned to each of 10 random intersections on the go board,
then terrible performance is guaranteed -- I can't give specifics, but
I would bet that no algorithm exists that will give "good" space and
time performance simultaneously for such random patterns, for any
reasonable definition of "good". But real-life tactics pattern sets
are hardly random, and it is reasonable to hope for better performance
on practical pattern sets than is theoretically possible for random
pattern sets.

Unsurprisingly, many people indicated that they use decision trees for
pattern matching. Each decision can be based on the value of a single
intersection -- for space-efficiency, it is often worthwhile to allow
many such tests to be collapsed into a single node, but that
implementation detail is beside the point. Incidentally, you can
abstract away intersections and stone colors, and consider
pattern-matching to be a matter of matching arbitrary variables
against arbitrary values. This abstraction makes it easier to
incorporate pattern-matching conditions that aren't just related to
the color of a single stone.

Which intersection should the decision tree test first? A reasonable
choice at any node is to test the value of the intersection that
appears most often in the set of patterns that match the selections
already made. So if all of our patterns require a specific value for
intersection (1,1), then we might as well test (1,1) first, and at the
root child node that corresponds to a white stone at (1,1), we would
test whichever other intersection appears most often among patterns
that already have a white (1,1) stone.

OK, that's enough of the obvious background. The difficult issue is
what to do about patterns that don't care about the value of the
intersection being tested. There are several choices:

1. Treat don't-care conditions in patterns like three separate do-care
conditions (one white, one black, one empty). Unfortunately, if
those patterns also don't care about any of the intersections
tested on the next level, then those 3 conditions become 9, then
27, et cetera. A single abberant pattern, that refuses to assign
values to the intersections most commonly tested, can cause the
size of the tree to double. Two mutant patterns can cause the tree
to become four times bigger; three, eight times; et cetera. This
approach guarantees pattern-matching times at most proportional to
the number of unique intersections specified in patterns, which is
no greater than the size of the board, but space performance may be
terrible. This brings us to

1a. Make the decision-making structure a directed acyclic graph (DAG)
instead of a tree, and make sure that you never create a new
subtree when it would work just as well to point to an existing
one. I don't think you can set any reasonable space bounds on
this technique either, but the only cost is a bit of extra
complication while creating the decision DAG, and in some cases,
it can reduce space usage drastically as compared to (1), so it's
probably worth doing.

2. Don't limit the decision tree to a single path. Instead of
creating one child per color appearing in at least one pattern,
create one child per subset of colors appearing in at least one
pattern. If there are patterns that require white, black, or no
stones at (1,1), but there are also patterns that require that
(1,1) be anything but white as well as patterns that allow any
color for (1,1), then then the (1,1) decision node is given five
children. If the actual board has a black stone at (1,1), then the
board is matched in succession against the {black}, {black, empty},
and {black, white, empty} (don't-care) subtrees of the (1,1)
decision node. This approach guarantees total space that is at
worst proportional to the total size of all patterns, but the upper
bound on matching time is terrible.

3. Mix and match. Sometimes method (1) is clearly better than (2);
sometimes, the reverse is true. You can decide on an ad-hoc basis
while creating the tree whether a given don't-care condition should
be treated as multiple do-care conditions, or it should be tested
separately. At a guess, it seems reasonable that the larger the
proportion of patterns that don't care about the intersection
value, the more likely it is that adding a separate subtree for
don't-care patterns is worthwhile, but correspondence is tenuous.
Does anybody know a better heuristic that can be implemented
without slowing down the decision-tree creation too much?

3. Mix and match. Sometimes method (1) is clearly better than (2);
sometimes, the reverse is true. You can decide on an ad-hoc basis
while creating the tree whether a given don't-care condition should
be treated as multiple do-care conditions, or it should be tested
separately. At a guess, it seems reasonable that the larger the
proportion of patterns that don't care about the intersection
value, the more likely it is that adding a separate subtree for
don't-care patterns is worthwhile, but the correspondence is
tenuous. Does anybody know a better heuristic that can be
implemented without slowing down the decision-tree creation too
much?

4. Other suggestions? Have I overlooked any critical improvements?

I if I recall correctly, many go programmers implied that (1) or (1a) was compact enough for them (is gnugo's DFA roughly isomorphic to one of these?), and for any reasonable number of plausible-looking hand-generated patterns, no doubt they are correct.

From: "Mark Boon" <tesuji@xxxxxxxxxxxxxxxxx>
Reply-To: computer-go <computer-go@xxxxxxxxxxxxxxxxx>
To: "computer-go" <computer-go@xxxxxxxxxxxxxxxxx>
Subject: [computer-go] Pattern Matcher
Date: Sat, 6 Nov 2004 14:27:02 -0200

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/

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