How well does it scale?
(e.g. what is the average lookup time to find all patterns in a position
with 50 stones on the goban, when you have a pattern database of say 10
million patterns).
I have done some experiments with such patterns as you have (which have to
match exactly instead of "neural network" type patterns and there are 3
important aspects:
In order to get a high "pro prediction" (relevancy) with an "exact matching"
pattern-based approach, you need millions of patterns at minumum. I have
experimented with up to 150 million patterns but found that when you include
the "best" patterns, about 10 million gives not so much lower performance.
But your matcher needs to be able to match the entire board in a reasonable
time (mine takes a millisecond with a pattern database of 8,388,608 patterns
for a board worst-case but it also considers chain stone counts and liberty
counts).
Another thing I found was that small pattern like 4x4 are of limited use.
5x5 is better, but only when you include info on # liberties & stones.
What is also important is a method of classifying a pattern's importance,
relevancy or "value".
A screenshot of such "pattern-learning" in-progress:
The graph shows which pattern sizes contribute to how many % of
pro-prediction.
(Pattern 0 is a 5x5 diamond and pattern 1 is a 5x5 square, patterns get
subsequently larger and finally, pattern 7 is the entire board - there are
about a quarter of a million of pattern 7 in the database, so it gives a
pretty good Fuseki. As you see, pattern 7 is responsible for a 2.5%
"pro-prediction", meaning that on average, for every pro game with on
average 250 moves, 6.25 moves are predicted "correctly" just by pattern 7
alone.
To sum it up, when working with patterns you ideally need:
- a lot of them
- which means automatic harvesting/extraction
- several sizes/shapes
- fast matching
- a method of ordering them into "importance"
A well-designed pattern system can yield high pro-prediction (over 20%) but
a system based on 4x4 patterns is IMO doomed to failure, except when it
takes liberties and chain sizes into account. In that case, my experiments
show that a pro-prediction of around 6% is possible.
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx http://www.computer-go.org/mailman/listinfo/computer-go/