Assume I want to run a game tournament with 1-on-1 games (think chess) that have (for simplicity) just win or lose as the outcome and I need a way to rank the players. Formally speaking, I want a function that takes a list of (player1, player2, who_won) triples and returns a ranking of players, e.g. by attributing each of them a number (list of (player, score)).

Because the tournament is going to be informal and unorganized, I cannot in any way influence who plays against whom when. The scoring system I am looking for should have these properties:

  • The order of games should not matter.
  • If two (or more) players keep playing against each other over and over, with the same winning probabilities, the scores should not change (or not change much, e.g. converge).

It may be a system where one new games can affect the scores of all people, if necessary, and it might need a computer to be calculated.

What scoring systems fulfil this?

  • 1
    How many games do you expect to have in the "tournament"? Sounds like you just need basic ELO ranking, but I don't think it's going to work so well on such a small sample size.
    – bwarner
    May 20 '13 at 17:31
  • The event I have in mind will probably score a dozen to a hundred players. May 20 '13 at 17:35
  • After reading up on ELO I don’t think it fulfills either of my two desired properties. May 20 '13 at 17:40

Try this, it's a system called Whole-History Rating. From the abstract:

Whole-History Rating (WHR) is a new method to estimate the time-varying strengths of players involved in paired comparisons. Like many variations of the Elo rating system, the whole-history approach is based on the dynamic Bradley-Terry model. But, instead of using incremental approximations, WHR directly computes the exact maximum a posteriori over the whole rating history of all players. This additional accuracy comes at a higher computational cost than traditional methods, but computation is still fast enough to be easily applied in real time to large-scale game servers (a new game is added in less than 0.001 second). Experiments demonstrate that, in comparison to Elo, Glicko, TrueSkill, and decayed-history algorithms, WHR produces better predictions.

It's been used rather successfully by a game I play called Arimaa. For a tournament score, rather than a player skill rating, you will probably want to treat all games as being played simultaneously, as opposed to allowing the ratio to fluctuate over time.

If it's source code you're after, you may find this pure Ruby implementation helpful. It can support any two player game, as long as the outcome is a simple win/loss.

  • That link is reported as very unsafe; do you know why? May 21 '13 at 2:16
  • 1
    @PieterGeerkens No idea, none of my browsers are giving me that message. Can anyone else corroborate?
    – Sconibulus
    May 21 '13 at 2:42
  • @Pieter Geerkens - The link looks fine to me. It's a very simple standard academic webpage that doesn't even use Javascript. May 21 '13 at 15:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.