The Applied Games Group Blog

New stuff directly from Microsoft Research.

TrueSkill Through Time

TrueSkill Through Time

  • Comments 11
  • Likes

In December 2007, we published a paper about the application of TrueSkill to all recorded data of professional and semi-professional Chess play from 1850 to 2006. The dataset can be obtained from ChessBase. We are very happy to be able to release the F# source code that performed all these massive computations. A few things to bear in mind when running this code:

  • The full factor graph has ~30,000,000 factors and ~25,000,000 variables. At this size, the analysis is among the largest applications of (approximate) Bayesian inference to date. Nevertheless, the full message passing schedule allocates no more than 11 GB of memory and is run in under 20 minutes on an Intel Pentium 4 processor. These numbers hold for the adaptive draw margin model run on 3.5 million games.
  • Due to the huge amount of results (>1,200,000 skills of all players in all their active years) we use SQL server to store the result set. Please let us know if you think a purely text based result output is needed and we will add it.
  • There is a very interesting, related paper by Prof. Mark Glickman which analyses subset of this data (88 top players of all time).

The attached ZIP file contains the entire source code which should compile without problems with F# 1.9.3.14. You can either load the solution in Visual Studio 2008 or simply run build.bat form the command line - in either case you will end up with a chessanalysis.exe program or an analysis.exe program. If you want to try out the application, we included the first 1,000 lines of match outcomes (this is part of the first 5 years of data we have).

As for running the code, here are the parameter switches of the command line application:

        -no-safe                          Does not save results predictions (default: off)
        -q                                    Verbosity level off; only works on single runs (default: on)
        -N <int>                           First N games only (default: ALL)
        -delta <float>                  Maximum deviation in any marginal for convergence (default: 0.01)
        -muS <float>                   Mean of prior skill belief (default: 1200)
        -sigmaS <float>              Standard deviation of prior skill belief (default: 400)
        -muD <float>                   Mean of prior draw margin belief (default: 300)
        -sigmaD <float>              Standard deviation of prior draw margin belief (default: 100)
        -beta <float>                   Standard deviation of performance distr. (default: 600)
        -tauS <float>                   Standard deviation of skill dynamics distr. (default: 40)
        -tauD <float>                   Standard deviation of draw margin dynamics distr. (default: 10)
        -server <string>               SQL server name for output (default: 'camresapga01')
        -prefix <string>                Table name prefix for output (default: 'Result')
        -db <string>                     Name of the database for output (default: 'ChessBase')
        -mf                                   Fixed draw margin (default)
        -mf2                                 Fixed draw margin with two factors for draw
        -maf                                 Fixed draw margin with ADF (iterate per year)
        -maf2                               Fixed draw margin with pure ADF
        -mv                                  Variable draw margin
        -as                                   Single run (default)
        -am                                  Model selection

So, a good first test is analysis.exe -no-safe SmallChessBase.csv.

We are very interested to hear your feedback - both on the model, our paper and the F# code.

Update: Following the release of the F# September 2008 CTP we have updated the source code to work with F# 1.9.6.2. Also, we added one of the new features of F#, namely units-of-measure. Note that one can no longer accidentally pass the variance instead of the standard deviation beceause the former being of type float<ELOPoints^2>. We have also added full debug support so simply press F5 to experiment with the -no-safe SmallChessBase.csv option mentioned above.

Update: We removed a reduant schedule creation in the function FixedDrawMarginADFAnalyse. Thanks to Henry (Xinhua) Zhang for pointing out this mistake!

Ralf Herbrich & Thore Graepel

Attachment: ChessAnalysis - CTP.zip
Comments
  • PingBack from http://www.mundositio.com/2008/05/31/trueskill-through-time/

  • I have been researching rating systems (first Elo, then Glicko) and found out about your TrueSkill method. I do not know F# but can I use your code to  analyze a CSV file with the same format as the one you have? Thanks

  • Hello again. I compiled the code and tested a subset of the data. My question is it possible to change the parameters to replicate the the TrueSkill calculator does? It seems the code is only to test paired teams. I am looking into ranking players on a 8-player team with no possibility of a draw. I can run the calculator for each game but that is too tedious. I was very excited that there is a system to rank teams now and was hoping there is an automated way to do that (e.g., your console app). Also, before I knew about this system, I was using Elo to rank players on a 8-player team and I had to split it up to heads-up matched (e.g., 1-2, 1-3...., 1-8) to get a ranking. I thought this was OK since 1 beat 2 - 8, etc. But your research paper said that Elo was only for heads-up ranking. How come my method is no good? Thanks again.

  • Following the publication of the F# source code for the TrueSkill Through Time paper, we have used the

  • There is a problem with your F# code for the latest F# release. VS 2010.

    Your problem lies in the Microsoft.FSharp.Reflection.Value namespace, which is not available on the newer releases of FSharp. I researched all FSharp libraries to find out where the types like GetSumTagConverters, GetSumTagReader and IsOptionType has gone to, but all of them seem to have disappeared from the radar.

  • This code breaks with recent releases (May 2009 CTP and VS 2010) of F#. The reason for the break is the absence of the namespace Microsoft.FSharp.Reflection.Value, which contained functions like IsOptionType, GetSumTagReader and GetSumTagConverters. These functions have since disappeared from the radar and the original page on Microsoft.com explaining this has also disappeared (supposed to be: http://research.microsoft.com/fsharp/manual/FSharp.Core/Microsoft.FSharp.Reflection.Value.html), leaving me at a loss to how to change your code, now knowing what the original functions were supposed to do.

    Is it possible for you to update the code to compile on the recent CTP releases of F# or to give a hint how to resolve these errors?

    Thanks,

    -- Abel --

  • @Daren: looks like my text on Experts-Exchange ;-). Sorry, didn't see your post before I posted mine.

  • FYI, I used this approach to get 2nd place in the Kaggle Chess rating competition. More information here: kaggle.com/.../topic-186-2nd-place-trueskill-through-time . Many thanks to the Applied Games Group for their great paper and code!

  • What license is this code released under? I've been asked to release my chess rating competition code, but without a license I can't do so (since it incorporates the code linked on this page).

  • Does anyone have a solution to compile this with newer versions of F#? Or alternately, would anyone be able to send me the compiled executable?

  • When I run this I get the error "Process is terminated due to StackOverflowException." by I'm not sure why?

Your comment has been posted.   Close
Thank you, your comment requires moderation so it may take a while to appear.   Close
Leave a Comment