New ranking algorithm.

[snorri]

Version 5 posted, which is the same as version, except it has 2500 runs, instead of 750. Major difference seems to be a radical decrease in older generation players.

So are you trying to prove that the KGS algorithm is good or that it is ridiculous and unstable?

Can you at least include confidence intervals or something?

[Ootakamoku]

So are you trying to prove that the KGS algorithm is good or that it is ridiculous and unstable?

Its not really unstable, just saying that it needs sufficient iterations, but that takes time to calculate. Effects of the wins and losses didn't have enough time to propagate far enough with few iterations. Hence I posted an early version with fewer iterations, and later updated it with another with more iterations.

Can you at least include confidence intervals or something?

CI is +-0.2 from sample size, assuming its measured in days, not in games. In general you can probably add in another +-0.05 stone to the CI from rank change during time window. And finally some cascade effects for maybe another +-0.1 CI. Ill update it so that it actually calculates the correct CI (as far as possible).

[Ootakamoku]

Had my computer calculating all time KGS strongest players for 2 days, managing 2900 iterations on the over 100k games. Updated the results to first post. Used the data available at http://www.u-go.net/gamerecords/. These are good preliminary results I think, but there are quite a few improvements I still need to make.

One problem I could use some help with is. Should I apply the distribution of player strength (each stone stronger is 2.22.. time more unlikely, proven to be quite reliably estimate, looking at any number of sources) during each phase of the iterations, or only when the final rank is calculated? Any opinions?

Another is I need to find a formula for calculating standard deviation in rank for time difference. For example, how much does a players rank change in a year, on average. I could then use that information to calculate the time frame I should use for each player so as to minimize the resulting standard deviation. Instead of the current 85 games, regardless in what time frame those 85 games were played.

Also, I need a better algorithm for finding the most likely rank at any given time, when I have decided upon the weights for games. Currently I just so somewhat random sampling in the search space (rank) to find the most likely rank, but very unefficient method of finding it, not to mention time consuming. Problem is if I try to optimize it too much I risk getting the result stuck in local maximum.

Regardless of the randomness involved in the whole process. The results seem to be remarkably consistent between runs (given same number of iterations), with only a few players changing order.

[Ootakamoku]

Updated to version 6 (in first post), finally have confidence intervals for players ranks. As it stands here is how the algorithm works.

Assumptions :
- 6.5 is a fair komi.
- Probability of weaker player winning is 0.5*(0.2383^strength_difference)
- Standard deviation in a players rank is 0.08 stones after 1 year.
- Standard deviation of all ranks is 1.12 stones.
- Each stone in strength is only 40% as likely as the previous.

When determining the rank for one player, at a specific game, all his game results are used. Each game result is given a weight, based upon a bell curve over time. The "width" of the bell curve is chosen such as to minimize the standard deviation. Too wide and we include games so far away in time that the players rank may have changed. Too narrow and we wont get enough samples. Then the most likely rank explaining all the game results, with given weights is chosen as the players rank at the specified game. We then perform this process for both players at every game. Since opponents ranks have changed, we need to recalculate everything, over and over again. Slowly approaching a balance (nash equalibrium), where we have a rank for each player at each of their games, that best explains all their game results.

Im tempted to dynamically try to set many of the assumptions, but afraid of the potential feedback loops.

[Ootakamoku]

Another big update. The GoGoD result should be accurate now. Included the most active players, that did not make it into the top 25, to both lists.

[Ootakamoku]

Two more major bugs crushed. Maybe, just maybe, its finally starting to give proper results. Updated first post results for GoGoD, and also added section for who are currently the strongest.

[Mef]

Two more major bugs crushed. Maybe, just maybe, its finally starting to give proper results. Updated first post results for GoGoD, and also added section for who are currently the strongest.

5. kitahama (2004.6) : 2.42 ± 0.56

kitahama had the highest rating graph I've ever seen on KGS, it was something like 25d+. The only way to follow it was to make a mental note as to what month it knocked the "9d" marker off of the bottom of the graph and reference everything to that.

[SmoothOper]

So do you think this algorithm is good enough to beat a spread wager?