Re: [computer-go] 9x9 Ratings

[Antti Huima <antti.huima@xxxxxxxxxxxxx>]

William M. Shubert wrote:

>What you have here is something that is pretty a maximum likelyhood
>system, but with the probability equation set to say that the stronger
>player has a 100% chance of winning and the weaker player has a 0%
>chance of winning.
>
>Since you have come so close and all you need to do is plug in a "real"
>probability of win equation, why not just take one and do so? You can
>take the one from KGS if you want (see it at
>http://kgs.kiseido.com/en_US/help/math.html) or you can dig up mlrate,
>which NNGS uses, which uses a slightly different equation.
>  
>
I just read the "Details of the KGS Rank System", and would like to
share a few comments.

The background is that I once implemented a (hugely succesful!) ranking
server for the pool game Eight Ball within a company with a pool table,
based on the method of maximum likelihood as Mr. Shubert suggested.

A real implementation should use probably addition instead of
multiplication, because you can take use the logarithms of the
probabilities. I did this and it worked fine.

Regarding the explanation of the iteration algorithm, what you
ultimately want is to find a local or global maximum of the likelihood
of the observed series of results. There are standard methods for this
kind of optimization, the easiest one being maybe the standard gradient
descent. I used standard gradient descent for my implementation if I
recall correctly.

I'm also a bit puzzled by the "weight of each game is multiplied by the
condifence we have in the opponent's rank". I believe it is a good think
to weight games at least according to their age. But this second-order
derivative thing I don't understand.

At a solution to the maximum likelihood equation, the first-order
derivatives dP/dR (P=joint probability, R=particular player's rank) are
all zero. If the solution is a maximal solution, second-order
derivatives d2P/dR2 must be negative (when rank increases, first-order
derivative becomes negative). If this is used as a measure of
confidence, then higher absolute value of the second-order derivative
corresponds to higher confidence. But I'm quite sure this effect is
already built in the maximum likelihood approach. Namely, if all games
weight the same, the ranks of the players with more games affect the
likelihood more, and therefore will have higher absolute values of the
2nd-order derivative in the first place. Maybe Mr. Shubert could comment
on the actual structure of this 2nd-order derivative idea?

Regarding handicap stones, I believe its somehow known that the nature
of Go changes radically when moving from even games to high handicap
games. I would like to propose the following approach: instead of
considering a single rank for every player, consider a set of twenty
distinct ranks, these ranks corresponding to the twenty different games:
black with komi, black without komi, black H2, black H3, ..., black H9,
white with komi, white without komi, white H2, white H3, ..., white H9.
For every single game, use the corresponding ranks from the rank set of
the two opposing players. Employing maximum likelihood, every player
gets 20 distinct ranks (some of them can be based on no played games at
all). Then create a probabilistic model that binds these ranks together:
settle on a probability distribution that maps a difference in two of
these 20 player-specific ranks to a probability, and take the resulting
probability into the maximum likelihood equation. (This kind of forces
the 20 ranks to approach each other). Finally, use the "black with komi"
rank as the reported one...

-- 
Antti Huima (Mr.)
Director, Conformiq Tools
mobile: +358 40 528 8667
email: antti.huima@xxxxxxxxxxxxxxxxx

Conformiq Software Ltd.
Stella Terra, Lars Sonckin kaari 16
FIN-02600 Espoo, Finland
tel: +358 10 286 6300
fax: +358 10 286 6309 
http://www.conformiq.com/

_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/