[computer-go] State of the art of pattern matching

[Mark Boon]

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