We’ve been playing in a boardgame league and it’s been awesome. This has led to the natural question: who is the best player? This is an inherently statistical question but like most statistical questions the answer is going to be complicated.

The Standard Approaches

Long Term Win Rate

The easiest approach would be to just measure long-term performance. The intuition being that luck eventually balances out (you win some, you lose some) and thus your performance converges proportionally with your underlying skill.

We can indeed see that this is true: setting up a ladder of skills we correctly identify the best player relatively easily. Note that early on the results are fairly noisy with the “Good” player appearing better than the “Elite” player due to a lucky start.

This doesn’t take into account your competition however! If I win roughly half of my chess games and Magnus Carlsen also wins roughly half of his we shouldn’t conclude that we’re equally skilled. Instead he’s playing against a much higher calibre of player than I am.

Let’s modify our simulation to include two groups: elites and normals. Notice that when each group plays amongst themselves similar patterns emerge. But once you look at a mixed group: it’s clear that the top players in the normal group are no match at all for the elites.

Elo

We can account for competition strength with something like Elo which shows up in chess, football, and even eSports. This system assigns ratings to each player with higher ratings corresponding to better players.

The specific mechanics are as follows:

  • Everybody starts with an initial rating of 1200 (this is an arbitrary number as are the others in this setup)
  • Before each game you can predict each player’s probability of success \(Pr(A \text{ beats } B) = \frac{1}{1 + 10^{(R_{B} - R_{A}) / 400}}\)
  • After each game you update your score: the winner adds \(K \cdot (1 - Pr(\text{Winner beats Loser}))\) to their rating and the loser drops a corresponding amount, where \(K\) is a fixed step size (usually 32).

Elo was originally developed for head-to-head competition like chess. The most common adaptation to multiplayer is to treat the winner as having beaten all losers in simultaneous pseudo-head-to-head games. We’ll take that approach here, though the right generalization will become clearer in the next section.

Let’s consider the same data from the previous section just ordered by time now. So first the average players play against each other then the elites play against each other, and finally a mixed group plays together.

Elo starts to separate the groups within each phase, but on similar scales. Once the mixed phase begins the elites start to skyrocket above the average players.

But notice something odd: once the mixed group starts playing, the players who aren’t continuing to play have ratings that stay perfectly frozen. Elo only updates on a match, so the holdout average players stay artificially high and the holdout elite players stay artificially low. If you run hot early, this incentivises quitting while you’re ahead. To fix this we need a method that updates everyone’s rating after every game, not just the participants.

Bradley Terry

Often when you are trying to extend a method you’re best served by recharacterizing the method as a special case of a more general method (which will be easier to extend). Let’s restart our derivation of Elo with just the probability of A beating B (and remove some of the weird magic numbers)

\[ Pr(A \text{ beats } B) = \frac{1}{1 + 10^{(R_{B} - R_{A})/400}} = \frac{\exp(w_{A})}{\exp(w_{A}) + \exp(w_{B})} \]

where \(w_{i} = R_{i} \cdot \frac{\log 10}{400}\). This is a Bradley-Terry Model: everyone has a base rate of skill and the probability of winning is proportional to their skill. As promised, we see that this suggests the natural generalization to multiplayer games. It’s called the Plackett-Luce model but it’s really just moving from the Bernoulli to a Multinomial for the outcome [I’ll still present the math as a 2 person game going forward just for conciseness].

Now let’s calculate the log-probability of observing A winning a game against B:

\[ \ell = \log Pr(A \text{ beats } B) = w_A - \log\!\left(\exp(w_A) + \exp(w_B)\right) \]

Taking gradients: \(\frac{\partial \ell}{\partial w_A} = 1 - Pr(A \text{ beats } B)\) and \(\frac{\partial \ell}{\partial w_B} = -Pr(A \text{ beats } B)\). One step of gradient ascent has the winner \(A\) gain \(K(1 - Pr(A))\) and loser \(B\) drop \(K \cdot Pr(A)\) — exactly the Elo update rule. We can view the Elo update just one-pass gradient ascent on the log-likelihood! So Elo is just doing maximum likelihood on the Bradley-Terry model with a simple optimizer (that hasn’t necessarily converged).

Thus if we use a different optimizer that actually achieves convergence we’ll (1) get a more stable estimator and (2) fix the inactivity problem.

Now we see the correct results from our mixed play: holdout averages tank and holdout elites soar along with their participating brethren. This also emphasizes the arbitrariness of these scores: it really only makes sense for the population you’re comparing against.

Estimating Uncertainty

The Bradley Terry model has an additional benefit: we can formulate a Bayesian version to accurately track our uncertainty. Elo is just a number and you can use it to do very dumb things. In particular our disjoint groups are a problem for naive Elo. If each play within their own bubble we’ll ostensibly have the same Elo rating. We need some way of accounting for the fact that there should be uncertainty between the two groups.

Let’s show this for our recurring average and elite example where we use the Bayesian posterior instead of the point estimates. For simplicity I’ll just track three values: the probability that the best average player beats the worst elite, the probability that the best average player beats the second best average player, the probability that the worst elite beats the second worst elite. Rather than the point estimates we’ll plot the posterior standard deviation of each win probability to reflect our uncertainty.

We can see from the figure that our uncertainty within the two groups shrinks substantially as we get more data but the uncertainty between the two groups remains high. In fact it’s not just high it’s almost maximally high: it more or less shows that we’re putting almost all of mass at either 0 or 1. This due to our wide prior which when pushed through the logistic ends up at the end: the average player either almost surely beats the elite or almost surely loses and because there’s no data connecting them we can’t tell which.

Conclusion

These ranking models are having a bit of a heyday lately due to LLMs. Chatbot Arena uses Bradley-Terry to generate their scores (but still calls it Elo on their plots). So it’s fun to see AI folks rediscovering these methods. Not that it’s that quiet of a literature to begin with: there’s a vast array of interesting problems in this space especially considering sports such as:

  • What if you assign players to teams and only get outcomes on the team level? This shows up a lot in sports and you get things like Adjusted Plus Minus. It’s particularly hard when you have stable teams without a lot of changes in composition. In those cases you need to do something a little more clever.
  • What if we assume that players’ ratings aren’t static by increase over time as they train and develop or (more pessimistically) lose their edge and decline. This gets to analyses of aging-curves
  • What happens if we don’t have a clear hierarchy in our ratings. With linear ratings there’s no space for intransitivity: A usually beats B, B usually beats C, but C also usually beats A. This usually shows up as strategic concerns: it’s basically the entire dynamic of rock-paper-scissors. I very much love the illustration in this paper which introduces a latent space to express intransitivity. I explore this more in my next post on Non-Transitive Bradley-Terry Models.
  • Can we use our ratings to assess players on related but still distinct tasks? For instance we’d probably expect someone good at regular chess to also be better at speed chess. So can we learn some generalized “skill” that we can use to generalize? This is particularly interesting the board game space since it’s not so much fun to play the same game obsessively but you still might want to know who’s better at particular games. This is very close to network models in item response theory.
  • What if you have some side-information about players: could you use that to rate them even if you’ve never seen them play before? This is of particular interest for scouting in sports. I explore this in yet another post on Neural Bradley-Terry Models.