elo.md

   1 # Elo
   2
   3 The Elo system (named after Arpad Elo, NOT an [acronym](acronym.md)) is a mathematical system for rating the relative strength of players of a certain game, most notably and widely used in [chess](chess.md) but also elsewhere (video games, table tennis, ...). Based on number of wins, losses and draws against other Elo rated opponents, the system computes a number (rating) for each player that highly [correlates](correlation.md) with that player's current strength/skill; as games are played, ratings of players are constantly being updated to reflect changes in their strength. The numeric rating can then be used to predict the probability of a win, loss or draw of any two players in the system, as well as e.g. for constructing ladders of current top players and matchmaking players of similar strength in online games. For example if player A has an Elo rating of 1700 and player B 1400, player A is expected to win in a game with player B with the [probability](probability.md) of 85%. Besides Elo there exist alternative and improved systems, notably e.g. the [Glicko](glicko.md) system (which further adds e.g. confidence intervals).
   4
   5 The Elo system was created specifically for chess (even though it can be applied to other games as well, it doesn't rely on any chess specific rules) and described by Arpad Elo in his 1978 book called *The Rating of Chessplayers, Past and Present*, by which time it was already in use by FIDE. It replaced older rating systems, most notably the [Harkness](harkness.md) system. Despite more "advanced" systems being around nowadays, Elo remains the most widely used one.
   6
   7 **Elo rates only RELATIVE performance**, not absolute, i.e. the rating number of a player says nothing in itself, it is only the DIFFERENCE in rating points between two players that matters, so  in an extreme case two players rated 300 and 1000 in one rating pool may in another one be rated 10300 and 11000 (the difference of 700 is the only thing that stays the same, mean value can change freely). This may be influenced by initial conditions and things such as **rating inflation** (or deflation) -- if for example a [chess](chess.md) website assigns some start rating to new users which tends to overestimate an average newcomer's abilities, newcomers will come to the site, play a few games which they will lose, then they [ragequit](ragequit.md) but they've already fed their points to the good players, causing the average rating of a good player to grow over time.
   8
   9 **Keep in mind Elo is a big simplification of reality**, as is any attempt at capturing skill with a single number -- even though it is a very good predictor of something akin a "skill" and outcomes of games, trying to capture a "skill" with a single number is similar to e.g. trying to capture such a multidimensional thing as intelligence with a single dimensional [IQ](iq.md) number. For example due to many different areas of a game to be mastered and different playstyles [transitivity](transitivity.md) may be broken in reality: it may happen that player A mostly beats player B, player B mostly beats player C and player C mostly beats player A, which Elo won't capture.
  10
  11 ## How It Works
  12
  13 Initial rating of players is not specified by Elo, each rating organization applies its own method (e.g. assign an arbitrary value of let's say 1000 or letting the player play a few unrated games to estimate his skill).
  14
  15 Suppose we have two players, player 1 with rating *A* and player 2 with rating *B*. In a game between them player 1 can either win, i.e. score 1 point, lose, i.e. score 0 points, or draw, i.e. score 0.5 points.
  16
  17 The expected score *E* of a game between the two players is computed using a [sigmoid function](sigmoid.md) (400 is just a [magic constant](magic_constant.md) that's usually used, it makes it so that a positive difference of 400 points makes a player 10 times more likely to win):
  18
  19 *E = 1 / (1 + 10^((B - A)/400))*
  20
  21 For example if we set the ratings *A = 1700* and *B = 1400*, we get a result *E ~= 0.85*, i.e in a series of many games player 1 will get an average of about *0.85* points per game, which can mean that out of 100 games he wins 85 times and loses 16 times (but it can also mean that out of 100 games he e.g. wins 70 times and draws 30). Computing the same formula from the player 2 perspective gives *E ~= 0.15* which makes sense as the number of points expected to gain by the players have to add up to 1 (the formula says in what ratio the two players split the 1 point of the game).
  22
  23 After playing a game the ratings of the two players are adjusted depending on the actual outcome of the game. The winning player takes some amount of rating points from the loser (i.e. the loser loses the same amount of point the winner gains which means the total number of points in the system doesn't change as a result of games being played). The new rating of player 1, *A2*, is computed as:
  24
  25 *A2 = A + K * (R - E)*
  26
  27 where *R* is the outcome of the game (for player 1, i.e. 1 for a win, 0 for loss, 0.5 for a draw) and *K* is the change rate which affects how quickly the ratings will change (can be set to e.g. 30 but may be different e.g. for new or low rated players). So with e.g. *K = 25* if for our two players the game ends up being a draw, player 2 takes 9 points from player 1 (*A2 = 1691*, *B2 = 1409*,  note that drawing a weaker player is below the expected result).
  28
  29 **How to compute Elo difference from a number of games?** This is useful e.g. if we have a chess engine X with Elo EX and a new engine Y whose Elo we don't know: we may let these two engines play 1000 games, note the average result *E* and then compute the Elo difference of the new engine against the first engine from this formula (derived from the above formula by solving for Elo difference *B - A*):
  30
  31 *B - A = log10(1 / E - 1) * 400*
  32
  33 ## Some Code
  34
  35 Here is a [C](c.md) code that simulates players of different skills playing games and being rated with Elo. Keep in mind the example is simple, it uses the potentially imperfect `rand` function etc., but it shows the principle quite well. At the beginning each player is assigned an Elo of 1000 and a random skill which is [normally distrubuted](normal_distribution.md), a game between two players consists of each player drawing a random number in range from from 1 to his skill number, the player that draws a bigger number wins (i.e. a player with higher skill is more likely to win).
  36
  37 ```
  38 #include <stdio.h>
  39 #include <stdlib.h>
  40 #include <math.h>
  41
  42 #define PLAYERS 101
  43 #define GAMES 10000
  44 #define K 25          // Elo K factor
  45
  46 typedef struct
  47 {
  48   unsigned int skill;
  49   unsigned int elo;
  50 } Player;
  51
  52 Player players[PLAYERS];
  53
  54 double eloExpectedScore(unsigned int elo1, unsigned int elo2)
  55 {
  56   return 1.0 / (1.0 + pow(10.0,((((double) elo2) - ((double) elo1)) / 400.0)));
  57 }
  58
  59 int eloPointGain(double expectedResult, double result)
  60 {
  61   return K * (result - expectedResult);
  62 }
  63
  64 int main(void)
  65 {
  66   srand(100);
  67
  68   for (int i = 0; i < PLAYERS; ++i)
  69   {
  70     players[i].elo = 1000; // give everyone initial Elo of 1000
  71
  72     // normally distributed skill in range 0-99:
  73     players[i].skill = 0;
  74
  75     for (int j = 0; j < 8; ++j)
  76       players[i].skill += rand() % 100;
  77
  78     players[i].skill /= 8;
  79   }
  80
  81   for (int i = 0; i < GAMES; ++i) // play games
  82   {
  83     unsigned int player1 = rand() % PLAYERS,
  84                  player2 = rand() % PLAYERS;
  85
  86     // let players draw numbers, bigger number wins
  87     unsigned int number1 = rand() % (players[player1].skill + 1),
  88                  number2 = rand() % (players[player2].skill + 1);
  89
  90     double gameResult = 0.5;
  91
  92     if (number1 > number2)
  93       gameResult = 1.0;
  94     else if (number2 > number1)
  95       gameResult = 0.0;
  96
  97     int pointGain = eloPointGain(eloExpectedScore(
  98       players[player1].elo,
  99       players[player2].elo),gameResult);
 100
 101     players[player1].elo += pointGain;
 102     players[player2].elo -= pointGain;
 103   }
 104
 105   for (int i = PLAYERS - 2; i >= 0; --i) // bubble-sort by Elo
 106     for (int j = 0; j <= i; ++j)
 107       if (players[j].elo < players[j + 1].elo)
 108       {
 109         Player tmp = players[j];
 110         players[j] = players[j + 1];
 111         players[j + 1] = tmp;
 112       }
 113
 114   for (int i = 0; i < PLAYERS; i += 5) // print
 115     printf("#%d: Elo: %d (skill: %d\%)\n",i,players[i].elo,players[i].skill);
 116
 117   return 0;
 118 }
 119 ```
 120
 121 The code may output e.g.:
 122
 123 ```
 124 #0: Elo: 1134 (skill: 62%)
 125 #5: Elo: 1117 (skill: 63%)
 126 #10: Elo: 1102 (skill: 59%)
 127 #15: Elo: 1082 (skill: 54%)
 128 #20: Elo: 1069 (skill: 58%)
 129 #25: Elo: 1054 (skill: 54%)
 130 #30: Elo: 1039 (skill: 52%)
 131 #35: Elo: 1026 (skill: 52%)
 132 #40: Elo: 1017 (skill: 56%)
 133 #45: Elo: 1016 (skill: 50%)
 134 #50: Elo: 1006 (skill: 40%)
 135 #55: Elo: 983 (skill: 50%)
 136 #60: Elo: 974 (skill: 42%)
 137 #65: Elo: 970 (skill: 41%)
 138 #70: Elo: 954 (skill: 44%)
 139 #75: Elo: 947 (skill: 47%)
 140 #80: Elo: 936 (skill: 40%)
 141 #85: Elo: 927 (skill: 48%)
 142 #90: Elo: 912 (skill: 52%)
 143 #95: Elo: 896 (skill: 35%)
 144 #100: Elo: 788 (skill: 22%)
 145 ```
 146
 147 We can see that Elo quite nicely correlates with the player's real skill.