An implementation of Whole History Rating (WHR)

[yoyoma]

Fellow ratings math nerds! I made an implementation of Whole History Rating (WHR) in python, you can find it here: https://bitbucket.org/KillerDucky/misc (see the whr directory).

I also updated the senseis page with a few examples of how it acts in certain cases:
http://senseis.xmp.net/?WholeHistoryRating In particular it is much less prone to having your rating get stuck from having many games in your past history.

I couldn't get Newton's method as described in Remi's paper to work, so I had to use a much slower bisection method instead.

[HermanHiddema]

[daniel_the_smith]

Nice!

And you get extra points for using hg/bitbucket

Edit: Ok, I was going to take a stab at getting Newton to work, but I'm a little confused-- I don't see it computing terms of the Weiner prior or the Hessian matrix.

Edit 2: Optimization wise, you binary search the entire rating space for every player every main loop-- it seems like you could decrease the space you binary search with each loop. For example, take the maximum change from the last loop, and search a space twice that big instead of going from MAX_RATING all the way to MIN_RATING. This ought to speed up later iterations a fair amount without changing the result. I bet you could also vary CLOSE_ENOUGH, start at (say) 5 or 10 on the first iteration and decrease it logarithmically every iteration until it gets down to .1-- that ought to decrease time spent in the inner loop in early iterations.

[yoyoma]

Edit: Ok, I was going to take a stab at getting Newton to work, but I'm a little confused-- I don't see it computing terms of the Weiner prior or the Hessian matrix.

Ok I added newtons_whr.py. Remove the exception at the top of the file and run it. The example shows a player named yoyoma going on a winning streak. By the time you reach 'day=100 wins=13' you can see Newton's method starts to oscillate. By 'day=100 wins=24' it starts to get really out of hand.

I'm not really much of a mathematician, so I was blindly following Remi's example. But from my limited understanding, the Hessian matrix is just used to execute Newton's method, so when I switched to bisection I ditched it. Similarly the Weiner prior is implemented by making virtual draws between a players previous/next vpds.

Edit 2: Optimization wise, you binary search the entire rating space for every player every main loop-- it seems like you could decrease the space you binary search with each loop. For example, take the maximum change from the last loop, and search a space twice that big instead of going from MAX_RATING all the way to MIN_RATING. This ought to speed up later iterations a fair amount without changing the result. I bet you could also vary CLOSE_ENOUGH, start at (say) 5 or 10 on the first iteration and decrease it logarithmically every iteration until it gets down to .1-- that ought to decrease time spent in the inner loop in early iterations.

Yes I didn't do much to try to optimize it. For now it runs fast enough for my experiments.

[pwaldron]

I'm not really much of a mathematician, so I was blindly following Remi's example. But from my limited understanding, the Hessian matrix is just used to execute Newton's method, so when I switched to bisection I ditched it. Similarly the Weiner prior is implemented by making virtual draws between a players previous/next vpds.

Where is the sigma parameter buried in the program? I don't see it, and you need a value even if you're only doing a bisection method.

I got as far as implementing a test version in C++ some time ago. If you want to cross-check test data, feel free to drop me a line.

[daniel_the_smith]

This is fascinating to me, I wish I didn't have bugs of my own to fix so I could play with it more...

[yoyoma]

I'm not really much of a mathematician, so I was blindly following Remi's example. But from my limited understanding, the Hessian matrix is just used to execute Newton's method, so when I switched to bisection I ditched it. Similarly the Weiner prior is implemented by making virtual draws between a players previous/next vpds.

Where is the sigma parameter buried in the program? I don't see it, and you need a value even if you're only doing a bisection method.

I got as far as implementing a test version in C++ some time ago. If you want to cross-check test data, feel free to drop me a line.

sigma? To me that implies an algorithm that takes a player's previous rating, has an uncertainty value (this is sigma), and then adds in new game results. This algorithm recalculates using all results so you don't really have the concept of the old rating.

There is something close to that though in the PRIOR_WEIGHT and PRIOR_ANCHOR stuff, where all players have two fake games, a win and a loss, against the PRIOR_ANCHOR. The rating of the PRIOR_ANCHOR is hidden in the whr_test.py file, I should refactor that into the main whr.py file. Also for the tests I was doing in whr_test.py, all games are played by a test player against anchors who have their rating fixed, just to make simple idealist test scenarios.

On the subject of key constants, the other important one is LINK_STRENGTH, which controls the strength of the connection between player days. Or in other words how fast player's ratings can change over time.

[pwaldron]

sigma? To me that implies an algorithm that takes a player's previous rating, has an uncertainty value (this is sigma), and then adds in new game results. This algorithm recalculates using all results so you don't really have the concept of the old rating.

My bad. What I was looking for was the value of the w parameter, which determines how much ratings are allowed to drift over time. I was thinking it was originally labelled sigma, but it wasn't.

[yoyoma]

I got some data for Starcraft2 and ran WHR on it. See results here:

http://www.teamliquid.net/forum/viewmes ... _id=261080