7

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).

If necessary, new games can affect the scores of all people, and calculations might need a computer.

What scoring systems fulfil this?

6
  • 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, 2013 at 17:31
  • The event I have in mind will probably score a dozen to a hundred players. May 20, 2013 at 17:35
  • After reading up on ELO I don’t think it fulfills either of my two desired properties. May 20, 2013 at 17:40
  • Did the tournament take place? What system did you end up using?
    – Stef
    May 23 at 11:01
  • This sounds like Almost-topological sort of a graph. Build a directed graph with one node per player and one arc from A to B with positive weight a-b if A and B have played together a+b times, with A winning a times and B winning b times, and a > b. Then solve the Feedback Arc Set problem for this weighted directed graph.
    – Stef
    May 23 at 11:03

2 Answers 2

6

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.

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

ELO

ELO is the simplest ranking system, but it does not that fulfill your requirements since order of games do matter. in ELO, Each player has a fitness rating that is updated after each game. Winning a player with higher rating than you largely increases your rating, winning a player with lower rating than you slightly increase your rating.

see Understanding the Elo Rating System

2

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .