Our pattern matching work is just now starting to run.
We will post details when we have done more testing.
Cheers,
David
On 26, Mar 2008, at 11:08 AM, Mark Boon wrote:
Lately I have been putting some effort into pattern-matching.
Although I have made progress, the result was not as good as what I
had hoped for by about an order of magnitude. This makes me wonder
what is currently actually the state of the art of pattern matching
in Go.
Of course it's a bit of a vague question, as there are many
possible forms of pattern-matching. Fixed-size patterns are the
easiest since a hash-code can be used. Nothing is going to beat
that in terms of speed, but its use is limited to some special
occasions. Joseki is one and apparently 3x3 patterns are used in
Monte-Carlo programs.
But I think the most generally useful form is one that can do
pattern-matching for variable shapes. (Or which can have don't-care
points if you like.) I thought I had a solution that would be
pretty close to the theoretical best performance. Formally proving
that would probably be a dissertation in itself, most important for
me is in itself it works and with modest memory requirements. That
is the good part. The bad part is, if I'm right this is the best it
can get I'm a bit disappointed it isn't faster. I'd rather be
proven wrong here. It's written in Java so making it in C would
possibly give a two-fold speedup, but that's all I can think of.
What I have now takes 10-15 microseconds on a 2Ghz Intel computer
to find all the patterns on a board (on average for 9x9, for 19x19
it's more like 15-20 usec) and it also gives me the 'new' patterns
i.e. patterns that match now but didn't match the previous move (I
believe that's a useful feature, but it's a detail). The set of
patterns is under a thousand patterns. Somehow smaller sets don't
go much faster, but larger sets do slow down, every ten-fold
increase in number of patterns seems to double the time.
So I was wondering if others cared to share the performance of
their pattern-matcher. I just want to find out if I'm chasing a
unicorn or not by trying to make something faster.
Mark
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
