[computer-go] K-nearest patterns

[Chrilly]

Indigo uses for automatic learning the K-nearest approach. The method is 
used in pattern matching to adjust automatically the window/basis size for 
sampling. See. e.g. C.M. Bishop, Neural Networks for Pattern Recognition, 
p.55-57. Usually one assumes n>>K.
In the case of the Indigio pattern learning the best result is for K=15 and 
the patterns are only used in the first few moves. But for the first 15 
moves this setting means, that the whole board is the sampling window. Or 
with other words, one just builds a chess-like opening book. I think thats 
what the Indigio team has exactly done. Only in the most complicated way. 
The Bayesion rules boil down to the simple rule, that an opening line must 
have a given frequency before it is played. And if there are in a certain 
position n moves, only the most frequent are taken. E.g. even if 1) b2-b4 is 
over the frequency threshold, it is not considered, because the alternatives 
1)e2- e4 1) d2-d4... are much more frequent.
The results of the Indigo-team mean: It improves a weak-programm slightly if 
it uses a chess-like opening book.

In chess such a "Bayesian-pattern-matcher" can be build by every user of 
Fritz/ChessBase. Its a feature of the GUI and nobody has thaught so far that 
this is big science. Actually the CB-book feature is more sophisticated, 
because one can consider winning probabilities, Elo ratings of players. This 
was not done in the Indigo-papern.
In academic-Go it is obviously big science (or at least worth a paper), one 
has just "to carry the church around the cross" (Austrian expression for 
making something simple very complicated).

Beside this curiosity, I think mixing the fixed size approach with a 
K-nearest seems to be reasonable (once the programms reach a level, where 
they can use the information in a reasonable way. At the moment they are too 
stupid to learn from Top-Dan-Games). Maybe they could learn from low-Kyu 
players, because the knowledge gap is in this case not so large. At least 
humans learn best by playing against slightly better players. A very 
stronger player can only give instructions, but one learns nothing in a 
9-stone handicap or a chess simultan (besides that one has no idea of the 
game).

Another interesting approach is to consider the last K-moves. An anagram 
approach. An recent article about this approach is mentionend on the 
literature list of M.Enzersberger. But the article is in Japanese and I can 
(unfortunately) not read Japanese (as far as I know it is even for Japanese 
people difficult to learn the 2000 signs which are necessary to read 
Japanese text).

The knowledge-gap is with this approach of course not solved. E.g. on 
top-level sequences are often not played out, either because the players 
know the result (but a weak player like myself just wonders whats going on) 
or because the want to keep the tension (e.g. Ko threats) for a later stage 
of the game. The programm would learn such jumps to other areas, but would 
not have the slightest idea about the motif.

Chrilly