Building a Multiplayer Elo Rating System

Most games today, even well-funded and established games, have terrible ranking systems. For example, tennis’s ATP ranking system is based on “points”, which are awarded by participating in select tournaments in the previous 52 weeks. The system is needlessly complicated and somewhat arbitrary, and does not directly take strength of opposition into account. The upper echelons of Halo and Call of Duty online rankings are, according to a friend, often populated with mediocre players who just play a lot of games, a result of a system that rewards sheer quantity of play over quality of results¹. I played high school quizbowl, and the system for ranking the teams was subjective and fairly arbitrary. The top 20 or so teams were fairly accurate because people knew who the best teams were, but beyond that it was guesswork based on unreliable metrics². This is where Elo ratings come in handy.

The underlying premise of the Elo rating system, first invented to rank competitive chess players, is that the purpose of a rating is to be able to predict the outcome of future games. Philosophically, it was based on a big data approach before big data existed–the only thing that should determine the rating formula is the corpus of games played. With enough prior games, Elo contends, you should be able to calculate the probability of any player beating any other player. The Elo rating system is better than many other ranking systems for several reasons:

1. It rewards the quality and consistency of results over sheer frequency of playing. Three good results will gain more points than ten mediocre results.

2. It provides a way to accurately predict the probability of one player beating another. In a two player Elo system, a player rated 100 points higher than his or her opponent has a 64% probability of winning³.

3. The ratings directly account for the opposition strength. Beating strong opponents gains more points. Losing to weak opponents loses more points.

While chess now uses a modified version of Elo known as Glicko-2, the basic principles still hold.

Developing the Algorithm

My friends and I started getting into the board game Settlers of Catan towards the end of my senior year of high school. We played a few games every week and would get pretty competitive about it. We’d argue over who was the best but had no metric to determine that other than, “well, he seems to win all the time.” After our first semester of college, we all came back home for the break and resumed playing. Inspired by chess ratings, I sought to create a rating system to put an end to the debate once and for all. I spent a day thinking about the various algorithms to use and a night coding an app that I later called the “Game Rating Calculator.” The rest of this post explains the process I went through in creating a rating algorithm, and the results after nearly a year of using it.

When I was developing a rating algorithm for the Game Rating Calculator, I was inspired to create a system modeled after the Elo system. I couldn’t port the Elo formula exactly, since it was designed for only two player games. I looked at a few approaches before settling (pun intended) on the final formula.

There are many variations of the Elo formula⁴. For the sake of clarity, all references in this post will be to the following formula:

R_new= R_pre+ K(S-E)

Where R_new is the new rating, R_pre is the pregame rating, K is the “k factor”, an arbitrary multiplier (a higher k factor means higher rating volatility), S is the total score in a rated event, and E is the total expected score in a rated event, which is calculated by:

where R_opp  is the opponent’s rating.

Assumptions:

I took my base scenario to be a four player game of Settlers of Catan, where all players were of equal strength. Intuitively, each player’s probability of winning the game is 25%. Assume that A came in first, and, if it is possible to have a second, third, and fourth place, then B came in second, C came in third, and D came in fourth. To determine a player’s opposition strength, I take the average rating of all of the opponents. All calculations using an Elo formula are done with a K factor of 16.

Approach #1 – The Pairwise Approach

The pairwise approach tries to get around Elo’s inability to work for more than two players by treating multiplayer games with one winner as a series of pairwise matches. In a four player game with players A, B, C, and D, if A won the game, you would rate the game as the result of three individual matches: A vs B, A vs C, and A vs D. But that leaves us with a problem: A has “played” three games, while B, C, and D have played one. The official online Settlers of Catan website and ranking system attempts to rectify this by taking into account relative positions in the game. That is, the second place player (determined by the number of points at the end of the game) will have “played” three games, losing against the first place player and winning against the third and fourth place players, and so on.

There are several problems with this approach. In our hypothetical case of four equally rated players playing a game, each player should achieve each possible position (first, second, third, and fourth) 25% of the time. In this case, the winning player’s rating was calculated as if he won three games in a row. Since each of his opponents is equally rated, the probability of him winning any individual game is 50% and the probability of winning three games in a row is .5*.5*.5=.125=12.5%. This means the formula acts as if the winner has an accomplished a task that is twice as difficult as it really was, and therefore rewards too many points. Similarly, the last place player will lose too many points, because even though his odds of coming in last were 25%, his rating will be calculated as if he lost three games in a row, which only has a 12.5% chance of occurring.

We can use the binomial theorem to calculate the implied odds for the second and third place players. The probability of winning two out of three games against an equally rated opponent (second place) is 3C2(.5)²(.5)¹ = 3*.125= .375 =37.5%. Similarly, for winning one out of three games against an equally rated opponent: 3C1(.5)¹(.5)²= 3*.125= .375 =37.5%⁵.

We can summarize the results in the following table:

We can determine the results using a standard elo calculator with a k factor of 32. Let all four players be rated 1000. Their new ratings would be as follows:

First place 1000 → 1048

Second place 1000 → 1016

Third place 1000 → 984

Fourth Place 1000 → 952

One could argue that even though the implied expected scores are off, since the players are all equal in strength, things should “balance out”. That is, in this example, the last place player is expected to come in first as many times as he comes in last, so things should even out. And if he doesn’t then he really deserves the lower rating.

The problem is that this really messes with the predictability with elo ratings. In that one example, there is now a 96 point difference between the first place player and last place player, which is so big that, after just one game, A’s predicted probability of beating D head-to-head had jumped from 50% to 63.5%. Even with a lowered K factor dampening the rating chance, the probability would still be overly optimistic for A. And since Elo uses the predicted probability (expected score) for calculating rating changes, this can mess with subsequent rating changes. And even if all the kinks could be worked out, it seems sloppy to use incorrect probabilities.

From a practical standpoint, this system also has two major problems.

1. In a game where there is only a winner and multiple losers, this system wouldn’t work. In Settlers of Catan, the player with the second most points at the end of the game is not necessarily the second most likely to win. Games where a player in third or even fourth “leapfrogs” to first and wins the game are not uncommon.

2. Having ratings dependent on positioning is ripe for manipulation. For instance, if you were were in dead last in a game of Settlers, you could offer to throw the game in favor of another player in exchange for help in moving up from last to place to third. This kind of manipulation is incentivized under this system.

Approach #2 – The Proportional Rating Approach

Elo operates on differences between actual performance and expected performance. As I studied potential solutions to a multiplayer Elo algorithm, I realized that if I could develop a way to determine expected performance in a multiplayer game, I could just plug it into the two player Elo formula. One way of doing this would be to give each player an expected performance equal to the proportion of their rating to the sum of the total ratings. If there were four players with ratings R1, R2, R3, R4, each player’s individual expected performance would be their rating divided by (R1+R2+R3+R4). In the case of our hypothetical example, each player’s expected score would be 1000/4000=.25, which is what our intuition expects.

The one issue with this approach it implies fairly slow improvement. Winning five games in a row is a pretty big deal (after all, in 4 person games the odds of that happening are .25⁵= .09%), but the rating gain would only be 65 points, which means that in a sixth game against 1000 rated opponents the expected probability of winning would only be 1065/4065= 26.2%,when it clearly should be higher.

As for evaluating its accuracy, there was really no way to test if the expected score was reasonable other than to eyeball it for completely inaccurate values. In a four player game with players rated 2000, 1000, 1000, and 1000, the first player has a 40% chance of winning, which seems reasonable for a player who is twice as good as each of his individual opponents. The only problem is that it would have taken so many wins to get to 2000 that the player is almost certainly underrated to begin with.

Approach #3 – The Modified Expected Score Approach

There was one final approach to examine, and this was the simplest of them all. Take our base scenario of four players, each rated 1000. The expected score of each player is .25, while the expected score in a one game, pairwise comparison is .5. In a five player game, the expected score is .20, while the pairwise comparison score is .5. In a six player game, the expected score is .17, while the pairwise comparison score is .5. The expected score for a game of N equally rated players can be generalized as:

2E_p/N

where E_p is the expected score in a pairwise comparison. The key question was, could I expand this formula for the expected score beyond the case of all players being equally rated? I added this multiplier to the Elo formula and tried it out with a few hypothetical games, and the rating adjustments seemed to make sense. But the only true way to establish this was to actually use the system in production. After all, Elo was revised over 40 years of real world usage (though others have found better algorithms). There were two things I really liked about this formula:

1. It’s point neutral among established players (not counting rounding errors)⁶ .

2. It gives a reasonable point adjustment for different size games.

This seemed to be the most promising approach and the algorithm I ended up using. The only issue that might arise is how the ratings would operate in the case of a player rated far above the rest. In a four player game, the theoretical maximum expected score is .5, which means that even if a player were rated one million points higher than each of his opponents, he’d still gain a sizable 16 points from winning. This issue only came up in such unrealistic scenarios, so I wasn’t too worried about it.

Provisional Ratings

The United States Chess Federation has a concept of provisional ratings. For the first 25 rated games, players’ ratings are more volatile⁷. The idea behind this is that it will more quickly get players to their “true rating”. It also takes into account that moving from casual chess to tournament chess is a disruptive process that has a learning curve, and that a player’s strength will be more volatile as he moves up that curve.

I didn’t include such a system in the rating calculator for a few reasons. First, it is easy to play such a large number of chess games, which makes reaching 25 fairly simple. In a game like Settlers of Catan, where you need to gather at least three (usually more) people for 90+ minutes, this isn’t practical. In the rating pool I set up, only five people had played 25 or more games after 11 months.

There is also a real risk of rating deflation, depending on the number of provisional games. For example, let’s say a provisional rating is twice as volatile as a non-provisional rating. That is, you will gain or lose twice as many points if you are provisionally rated. If there was just one provisional rated game and an average game of Settlers had four players, 75% of the players would have their ratings deflated, since 75% would lose their first game. That 75% would get only half the points they would have otherwise gotten when they win later.

The idea is to tailor the number of provisional games to the point where players are equally likely to get their wins and losses in that set of provisional games as they are to win and lose in general.

The provisional period is five games in my rating pool. At the time, the average game seemed to be around five players. We’ve played many more games since then, and the average has dropped to four players per game. In the first four games, an average player is expected to win one game. But in the fifth game, 75% of the players will lose. In this case, 75% of the incoming players have a deflated rating. Unfortunately, due to a desire for consistency in the rating system, I can’t dynamically adjust the number of provisional players each time. I may retroactively recalculate the ratings based on an average game size of four, since that has held stable for a while.

 Results

It was time to put this rating algorithm into production, and see how it held up. As of this writing, 80 rated games have been played, and a total of 28 players have played at least one rated game. Below are all the results for the players who’ve played enough games to not be provisionally rated (6+).

Average: 980.2

Median: 980.5

Average game size of all games played: 3.93

* The Expected Winning Percentage is based on the average game size, assuming all other opponents were equally rated

** The Net Difference may not match Winning Percentage- Expected Winning Percentage due to rounding

At first, I arbitrarily started off all players at 1000. Once there was a decent sized pool, I started off all new players at the median rating of non-provisional players. The median rating has dropped over time, probably because of the deflationary effects of the provisional ratings I mentioned earlier.

Overall, the results look pretty good. The ratings intuitively correspond with how I feel most people should be rated. Importantly, the ratings fit one of the main criteria I wanted in a rating algorithm: it awards the quality and consistency of results, and not just the sheer quantity of games. For instance, W.A. and I are rated exactly the same. He has a much better net winning percentage than I do, but that is compensated by the fact that I’ve maintained a decent percentage for far more games. His strong results are balanced by my consistency. There is one obvious outlier here, and that is A.S. A.S. used to be much lower rated (below 900) but has recently surged with a lot of strong results. One possible explanation for his high ratting and low winning percentage is that he played a lot of games with high rated players. I haven’t calculated each player’s average opponent’s rating, so I can’t say for sure.

I’ll eventually put this all in a SQL database to automate some of the data gathering. But the best way to improve the rating system would be to run data analysis algorithms on the results. How accurately do the ratings predict results? Unfortunately there is still not enough data. Heuristically, I’d think there would have to be a rating pool on the order of at least 25 people who have played at least 25 games to accurately assess the system.

But for now, this algorithm will do. If you’re interested in learning more about the Elo rating system in order to develop your own, check out the book by Elo himself, The Rating of Chess Players: Past and Present.

Tl;dr: Download the desktop version and Android version of the app.

1 But then again, that’s what the game makers want. These days games usually have some sort of in-game store or revenue steam, so more play usually means more money.

2 There have been some attempts to institute a chess style elo rating for quizbowl, but the ratings aren’t very accurate since data is sporadic.

3 Assuming you are using the Elo formula mentioned in this post.

4 If you’re interested in learning more about the Elo formula, here is a good treatise about it by Mark Glicko, the chief statistician in charge of the United States Chess Federation implementation of the Elo formula.

5 You could have also intuitively determined this result by noting that the probability distribution for the four possible outcomes were symmetrical, and since winning three in a row and losing three in a row are each .125, the other two possibilities must add to .75, hence .375.

6 It’s interesting to note that Elo system used by the United States Chess Federation and FIDE (the world chess federation) are not point neutral, because they have a K factor that declines as rating goes up. This was apparently used a way to stop rating inflation at the top of the rating pool. Not all chess organizations agree with this—the Internet Chess Club, the premier online chess server, does not use variable K factors outside of provisional games.

7 The volatility decreases within the set of 25 games.

If you’d like to receive my future posts in your inbox, enter your email below: