[computer-go] ELO Ratings of move pattern

[Rémi Coulom]

Lars wrote:
> I have some questions concernig this paper of Remi:
> http://remi.coulom.free.fr/Amsterdam2007/MMGoPatterns.pdf
>
> 1. Which sense make the prior (Section 3.3 in the paper and where is the
> application?
> I understand it the way that you put 2 more competitions to each pattern
> in the minorization-maximization formula. But how does this produce a
> probability distribution with mean 0 and standard deviation 302??
>   

This probability distribution is in the scale of Elo ratings. The 
formula is Elo = 400*log10(gamma). The probability distribution of 
getting one win and one loss against one player of rating zero has 
standard deviation 302 (and mean zero).

> Is the prior only necessary to make sure that every pattern have at
> least one win?
>   

It also has a regularization effect that avoids overfitting. That is to 
say, even if a pattern has, say, one win and ten losses against a player 
of rating zero, the prior will make it two wins and eleven losses, thus 
moving the strength of the pattern a little bit towards zero. It avoids 
high ratings for patterns that have been seen rarely.

> 2. I had run the algorithm on 400 games (including handicap-games) from
> the same game-records source Remi used (Section 3.2), but i used an
> other month. I concidered only 3x3 shape-patterns and simple non-shape
> pattern including dist-to-boarder, dist-to-prevMove, atari, capture,
> extension..
> After 1 iterations of the algorithm, I got strenght-parameter values
> completely different to the results of the paper (Table 1). Most of my
> parameters (including all the dist-to-boarder parameters!) have values
> less than 1.0. Does anyone have some explanations on this? 
> After 5 iteration it is even worse. Most of the low values (less than
> 1.0) gets even lower, the high values even higher. 
>   

This sounds like a bug. The number of iterations depends on features. I 
do not remember exactly how many iterations it took for mine. In general 
2-3 iterations are enough to get very reasonable values, a dozen to have 
good convergence.

Note that the values of some features are relative and not absolute. For 
instance, distance to the previous move: if you multiply all of them by 
a constant value, it will not change the likelihood. Nevertheless, if 
you have no bug in your implementation, you should get values that look 
like mine.

My suggestion would be to test your code with very small amounts of 
artificial data. For instance, start by two players A and B, and, say A 
beats B twice and B beats A once. Gammas should converge to gamma_A = 2 
* gamma_B. You can make up similar tests with teams.

Rémi