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@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/
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
