[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [computer-go] 9x9 Ratings

Antti Huima wrote:

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.

Another very powerful technique to find the maximum likelihood is Minorization-Maximization. Implementation is very simple, and performance is tremendously better than gradient descent. I implemented this technique in an Elo-rating tool. You can find out more on that page:
http://remi.coulom.free.fr/Bayesian-Elo/
The links at the bottom of the page point to discussions and explanations of the algorithms.

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.

I don't understand either.
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?


I agree.
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...


That makes sense, but it looks a little complicated. Without going into such a complex scheme, I believe it is possible to do much better than assigning a fixed arbitrary rating value to one stone, or one point of komi. Based on a big database of games, it should be possible to estimate with precision how much rating a n-stone handicap is worth. The scale would probably not be linear. It would also be possible to estimate the maximum-likelihood value of the k factor used in the KGS formula.

It is my plan to improve my elo-rating program so that it can handle go games, with handicap and komi. I'll tell you if I get interesting results.

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