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

[Gunnar Farnebäck]

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.

I tried this with GNU Go and got about 40-80 usec on 9x9 for a database 
of 500 patterns with in some cases lots of wildcards (black or empty, 
white or empty, black or white or empty (but not off board)). This was 
on a 2.2 GHz AMD64.

/Gunnar