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

[Mark Boon]

Thanks for the pointer Don, that might be worth looking into at some  
point.

When you say 'amazing accuracy despite this speed and simplicity' I  
still have to ask: "how fast?". I think 10usec is actually pretty  
fast. But when talking about using it during MC playouts for example,  
it's still rather slow. This is due to the pile-up of numbers. A  
(relatively) big area to look for, and a large number of occasions to  
do the lookup.

The patterns don't necessarily need to be hand-crafted. But throwing  
a million generated patterns at it also has its price in terms of  
performance.

Mark


On 26-mrt-08, at 16:17, Don Dailey wrote:

> Mark,
>
> I am doing some experimentation with something similar to  
> patterns,  but
> based  on Naive Bayes classifiers.   The idea is to use  Naive Bayes
> classifiers to generalize patterns.     The classifiers would still be
> focused on some constrained area of the board, such as the 5x5  
> matrix or
> something,  but they would be extremely compact compared to  
> patterns and
> very good at generalizing.  I'm convinced they would have to be  
> enhanced
> with additional attributes concerning the points being considered,   
> but
> one of their strengths is that you can pile on huge numbers of
> attributes without killing the speed or memory consumption very
> significantly.
>
> Recently there has been a huge surge of interest in Naive Bayes
> Classifiers due to their simplicity and speed, and yet amazing  
> accuracy
> despite this speed and simplicity.    Nothing has been found that
> improves all that much on Naive Bayes for many applications,  and some
> simple improvements to Naive Bayes has put it in the same league as
> other far more complex and computationally expensive methods such as
> neural networks and decision trees.
>
> I have no idea whether I'm barking up the wrong tree - but I think  
> it's
> definitely worth taking a look at.     I don't think GO programs  
> can be
> improved much more by simply adding more hand crafted patterns - we  
> need
> to find ways to generalize knowledge in powerful ways.
>
> Naive Bayes is trained by example and it's trivial, basically a single
> pass statistics gathering.   So you must basically show it a gazillion
> sample patterns with "known" classifications.    You could build these
> from games of strong players for instance.
>
> - Don
>
>
>
>
> 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 at computer-go.org
>> http://www.computer-go.org/mailman/listinfo/computer-go/
>>
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/