Skip to content
Tutorials Center
My learning

Topics

Lesson 48 of 63 ยท Real-World Projects

Project: An Elo-Style Rating Calculator

Build an Elo-style rating calculator: win probability from rating gaps, rating changes from contest standings with ties, a zero-sum check and a simulation that recovers true skill.

Every competitive-programming site shows a number next to your name. That number is a rating, and it is the answer to a statistical question: given the results so far, how strong is this person? Ratings let sites seed contests, show progress and pick problems of the right difficulty. The classic model behind many of them is the Elo system, invented for chess and later adapted for contests with many participants. Codeforces and AtCoder use more refined versions, but the core ideas are the same, and they fit in about thirty lines of Python.

In this project you build the calculator step by step. First comes the expected score: how likely is player A to beat player B, given their ratings? Then the update rule: after a contest, move each rating up if the player did better than expected and down if worse. We extend the rule from two players to a full standings table with ties, verify a conservation property with a test, and finally simulate dozens of contests to see whether the ratings recover the players' true strengths. The checking habit is the same as in stress testing, and the probability behind the formula is related to probability and expected value.

flowchart LR
  R["Ratings before<br/>the contest"] --> E["Expected score<br/>from rating gaps"]
  S["Standings<br/>(places, ties)"] --> A["Actual score<br/>from places"]
  E --> D["Delta = K x (actual - expected)"]
  A --> D
  D --> N["New ratings"]

Each rating moves by how much the real result differs from the expected one.

Step 1: expected score

Elo models a match between players with ratings ra and rb. The probability that A wins is

E(A, B) = 1 / (1 + 10 ^ ((rb - ra) / 400))

The constant 400 is a scale: a 400-point advantage means roughly a 91% chance of winning, because 10^1 = 10 gives odds of 10 to 1. Equal ratings give exactly 0.5. The two players' expectations always add up to 1, since one of them must win (ties are handled by counting half a win each).

Python Expected score for different rating gaps

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The numbers show the S-shape of the curve: the first 100 points of advantage matter a lot (0.5 to 0.64), while the step from 400 to 800 changes the probability only from 0.91 to 0.99. The 1700-versus-1500 pair gives 0.76 and 0.24, which add up to 1.

Step 2: from one match to a standings table

A contest has n participants and one standings table. We treat it as a round-robin: every pair of participants plays an imaginary match, decided by who placed higher. Then for participant a:

  • Expected score = the sum of E(a, b) over all other participants b.
  • Actual score = the number of participants placed below a, plus 0.5 for each participant with the same place (a tie).
  • Rating change = K * (actual - expected) / (n - 1).

K is the sensitivity: how many points a result can move you. Dividing by n - 1 keeps the change on the same scale for a 5-person and a 5,000-person contest. In chess, K is often 10 to 40. A larger K reacts faster but is noisier.

This system has a beautiful invariant. Over all pairs, each match gives one point to the winner (or half a point to each in a tie), so the actual scores add up to n(n-1)/2. And since E(a, b) + E(b, a) = 1, the expected scores add up to the same total. Therefore all rating changes sum to exactly zero: points move between players but are never created. Writing a test for this is a good way to catch bugs, and the contest-level version of the idea is why a strong player who wins loses points only when others overperform.

Python Rating updates for a four-person contest, with a zero-sum check

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the first contest everyone starts equal, so the winner gains the most and the last place loses the most by the same amount. The second is more instructive: the lowest-rated player (ann, 1200) wins and gains the most, the highest-rated one (cy, 1800) places last and loses the same amount, and the two tied players (bob, dee) both have a change of 0.00, because sharing a place with an equal-rated player is exactly what the formula expected of them. The zero-sum check prints 0.0 in both cases.

Real sites add details this project leaves out: provisional ratings for new accounts (larger K at first), rating floors, a volatility estimate, and using expected rank instead of pairwise comparisons so the cost is O(n log n) rather than O(n^2) for thousands of participants. The pairwise version is easy to read and fine for small contests.

Step 3: simulate many contests

How do we know the updates make sense? Run an experiment where we know the truth. Create ten players with hidden true skills from 1000 to 1900. For each contest, give every player a performance equal to their skill plus random noise (a Gaussian with standard deviation 250), sort by performance to get the standings, and apply update. If the system works, the ratings should drift into the order of the true skills, even though every player starts at 1500 and every contest is noisy. We use a seeded random.Random, so the run is reproducible.

Python Simulate 40 contests and recover the players' true order

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

After the first contest the ratings are still close together and 5 of the 45 pairs are in the wrong order. As contests accumulate, the spread widens (the weakest players sink, the strongest rise) and the number of wrongly ordered pairs falls to 0 by contest 20. It then rises to 3 at contest 40: one unlucky contest can swap neighbors, and that noise never fully disappears. The sum of all ratings stays at 15,000 forever because every update is zero-sum, which is the invariant from earlier, now confirmed over 40 rounds.

Step 4: the effect of K

The sensitivity K is a trade-off. A small value moves ratings slowly (stable, but slow to find the truth); a large one adapts quickly and also overreacts to a single lucky or unlucky contest. Run the same experiment with different values and count the misordered pairs:

Python Compare K = 8, 32 and 96 over the same 40 contests

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With 40 contests and the same random stream, larger K stretches the ratings further apart (the weakest sinks to 1153 at K = 96 but only to 1408 at K = 8). In this particular run the smallest K also ordered all pairs correctly, while the largest misordered 2, because big steps follow noisy results more closely. A small K is slower at the start, though; real sites therefore use a bigger K for newcomers and a smaller one for veterans. Change sigma in play_contest to see the effect of noise: with noisier contests, ratings need more rounds to settle.

Ideas to extend it

  • Provisional period. Use K = 64 for a player's first five contests and K = 24 afterward.
  • Performance rating. Find the rating at which a player's expected score equals their actual score, using binary search (the technique from binary search on answer for contests); the expected score is increasing in the rating, so the search works.
  • Faster standings. Replace the O(n^2) loops by sorting, or by an expected-rank formulation, for large contests.
  • Rating history. Store each contest's change per player and print a progress report, similar to the tracker project later in the track.
  • Prediction check. Measure how often the higher-rated player wins a simulated head-to-head to check that the model matches the formula.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Two players have equal ratings. What is the expected probability that the first wins?

    With rb equal to ra the exponent is 0, so the formula gives 1 / (1 + 1) = 0.5.
  2. 2. Why do the rating changes of a whole contest add up to zero in our system?

    Each pairwise match hands out exactly one point in total, and E(a,b) + E(b,a) = 1, so total actual and total expected scores are equal.
  3. 3. What happens to a high-rated player who is placed last in a contest of equal-rated opponents?

    Their actual score is 0 while their expected score is high, so actual minus expected is strongly negative.
  4. 4. What does a larger K do?

    K scales every update. A bigger K reacts faster to results, including lucky or unlucky ones.
  5. 5. How are ties handled in the actual score?

    A tie splits the point, which also keeps the total actual score at n(n-1)/2.

Summary

  • The Elo expected score 1 / (1 + 10^((rb - ra) / 400)) turns a rating gap into a win probability, with 0.5 at equal ratings.
  • A contest standings table is treated as a round-robin: actual score counts the players placed below you, with half a point per tie.
  • The rating change is K * (actual - expected) / (n - 1), and all changes in one contest add up to zero.
  • Simulating contests with known hidden skills is a reliable way to test whether a rating system works.
  • K trades speed of adaptation against noise; real systems use a larger value for new accounts.
  • Verify invariants such as the zero sum with code, the same way you check solutions with a brute force.

Next: Project: An ICPC Scoreboard