Rankings and cutoff based on mu

[fourmidable]

I believe the fairest way to proceed with the ranking and the cutoff of the bots is to use mu instead of skill.

Let me explain why this makes sense. First I'd like to recap a little on the TrueSkill algorithm for those who are unfamiliar with it. I got a pretty good look at how it works as part of Kaggle's Deloitte/FIDE Chess Rating Challenge. TrueSkill is essentially a Bayesian estimator of a player strength. TrueSkill is superior to other simpler ratings system like ELO in two ways: first there is provision for teams and multi-player games, and it converge faster than ELO. A large part of the advantage of TrueSkill is that it tracks both strength (mu) and uncertainty (sigma) of each participant. The player strength is modeled as a Gaussian (normal) distribution of mean mu and standard distribution sigma.

In Ants, mu is initialized to 50 and sigma to 50/3 ~= 16.67. From a Bayesian perspective, this is the prior distribution. After each game, TrueSkill compares the outcome of the game with the expected results and computes a new distribution mu/sigma that maximizes the probability of the strength for each player. The research paper reports that good convergence occurs within 20 games typically.

Now, ants leaderboard is not sorted by program strength estimate (mu), but instead by a metric called 'skill' defined as mu-3*sigma. Notice how a new submission gets a skill of zero. As gamed are played, the uncertainty in strength decreases, reducing sigma, and thus the 'skill' typically increases (unless mu drops precipitously) . Skill is nice to maintain a leaderboard so that rough initial mu estimates don't suddenly appear on top, and force the program to slowly raise through the ranks over time. However, for the final, this property is undesirable.

The pairing algorithm favors adding players with low sigma in other player's games. As more games are played, sigma becomes lower and even more game are played, improving 'skill' but not 'mu' as much. It would be unfair to compare 'skill' between players that have played different number of games, but comparing 'mu' is the best comparison. Remember 'mu' is really the statistically most probable measure of the strength of the player, and much less sensitive to the number of game played. There is still a small bias introduce by the priors, negative for top players and positive for bottom players, but this effect should be small once 10 games are played. Skill is an artificial measure designed to lower new submission, that essentially says there is 99.85% chance the player strength is actually above this value (3 sigma).

For these reason a suggest switching on a 'mu' based ranking for the finals.

[BenJackson]

I agree. I was/am hoping the sigmas will converge in the final-finals to the point where it won't matter. However when the "cutoff" starts any bot that gets ejected past the cutoff will have a hard time getting back in because outside the cutoff your sigma is frozen.

[tictac]

i agree too.
I am worried about convergence if the final stop thrusday as advertised: the top 100 start at least to have the good bots in it but its far far from converged imho. Quite some bots rank are probably of my more than 10 rank (mine for example is above its true rank probably because it has a lot of games and thus a low sigma) and the number of game is very different across bots. So to have a fair sigma you want to equalize the number of games but even that is not totally fair because a bot who had a lot of its matches early probably had a much more random set of encounters than bots that will have their missing games later (unless the sigma diminution takes into account the sigma of other players ?). In addition luck plays more of a factor in ants than in games like chess so this inherently increases the sigma of all bots.

[tmc]

Completely agree; I wanted to make exactly the same argument, so thanks for sparing me the trouble :)

[McLeopold]

[amstan]

From what I talked to janzert.
Sigma is not exactly the same as game count. Game count does matter, but we hope we can converge them. Sigma offers a more important metric which is consistency. If 2 players are racing for a rank and they have the same mu, you would want the more consistent bot the take the lead than the one who might lose once in a while.

Related to convergence, this is the range of sigmas that we have so far:
http://pastebin.com/hmEaVUtq

[Parasprites]

Are the finals really going to end in two days? Because I doubt they will have converged completely by then. Admittedly, if all you want to know is 1st place, you could stop it now, but the rankings of everyone below Xathis are still highly variable.

[analyst74]

If my super-unscientific observation stands, don't all players' sigma converges to 1.30 at some point after 50~100 games?

[amstan]