Elo rating system: Common link between Facemash and chess!

 

Remember the scene from the Facebook movie,  The Social Network where Mark Zuckerberg, while creating “Facemash” (the earlier version of Facebook), tells Eduardo Saverin, “I need the algorithm you used to rank chess players” who then writes an equation on the glass panel?

 

That equation is called the Elo rating or Elo rating system, named after its creator Arpad Elo. This rating system is used to rate the skills of the players in competitor-versus-competitor games like chess, football, baseball, and American football.

Elo believed in the following:

1. Performance of each player in a game is a normal distribution of random variables
2. The mean value of players irrespective of their performance in an individual game increases slowly.

Initially invented as a rating system for chess players, Elo is now used as a fundamental rating system in most video games, snooker, scrabble, etc.

Elo rating system explained –

This system is used to determine the output of a game by using a player’s Elo rating. It is all based on probability. Players with a higher Elo rating have a higher probability of winning a game than players with a lower Elo rating.

After the game, the winner takes points from the loser, thereby increasing his rating.

If a high-rated player wins, only a few points will be transferred from the lower rated player. However, if the lower rated player pulls off an upset win, then the number of points that are taken by the player with the lower rating is far greater. (Sounds unfair, doesn’t it?)

 

Elo rating system equation explanation –

Let’s take a look at the Elo rating equation. 

calc = (1.0 / (1.0 + pow(10, ((rating_2 – rating_1) / 400))));

In this equation, RA and RB stand for the current Elo ratings of a player.

In real-world competitive gaming, a player has a probability of winning, losing, and drawing a match. So when a player has a score of 0.64, the probability of winning, losing, and drawing is 64%, 26%, and 0%, respectively.

After the match, if a player’s match score exceeds his predicted score, then the player’s Elo rating is updated. Similarly, when a player’s match score falls short of the expected score, then the player’s rating is adjusted downward.

Assume that a player is required to score EA during a tournament but scores SA, then the player’s rating is updated by using the following formula:

calc = (rating + kfactor * (actual – expected));

K is known as “K factor”. It is a measure of how strongly a match will influence a player rating. If  K is of a lower value, then the rating is changed by a small fraction but if  K is of a higher value, then the changes in the rating are significant. Different organizations use different K factors; there is no universal value defined for it.

Pseudo code for the Elo rating system

import math;
class elo_core:
def getExpectation(rating_1, rating_2):
calc = (1.0 / (1.0 + pow(10, ((rating_2 – rating_1) / 400))));
return calc;
def modifyRating(rating, expected, actual, kfactor):
calc = (rating + kfactor * (actual – expected));
return calc;

Elo rating system example – 

Assume that Garry Kasparov has a rating of 2500 and Vishwanathan Anand has a rating of 2200.

Their expected scores are:

• If Garry Kasparov (wins) = 1/1+10 to the power (2200 ? 2500)/400 = 0.849
• If Vishwanathan Anand (wins) = 1/1 +10 to the power (2500 ? 2200)/400 = 0.151

Now believe that the Federation has decided that the value of K is 24.

The new ratings of the players are as follows:

If Garry Kasparov wins

• Garry Kasparov = 2500 + 24 (1 ? 0.849) = 2503
• Vishwanathan Anand = 2200 + 24 (0 ? 0.151) = 2196

If Vishwanathan Anand wins

• Garry Kasparov = 2500 + 24 (0 ? 0.849) = 2479
• Vishwanathan Anand = 2200 + 24 (1+ 0.151) = 2220

Since Garry Kasparov (with a better rating) is the favorite,  his win did not change the rating drastically. However, if the underdog, who in this case is Vishwanathan Anand wins, the ratings change drastically.

This is why in a cricket series between India and Zimbabwe, when Zimbabwe (with a lower rating) beats India, its rating changes quickly and it moves up the table. However, if India wins there is hardly any change in its ranking (Though ICC uses a modified version of Elo rating with some minor changes, the basic algorithm remains the same). 

Using the same Algorithm, Facemash assigned a specific rating to each individual. This rating increased with each favored click. 

Every girl on the Facemash database was assigned a specific base point.

When a user rated one girl based on her attractiveness in comparison to another, the rating of the selected girl increased while that of the other girl decreased. The number of users that rated a certain girl as attractive, the higher her ranking. Better the ranking, higher the possibility of being the most attractive girl on campus.

The Elo rating algorithm for a rating is used in almost every sports event either in its basic format or with some modifications. Now you know the algorithm which rates football players like Messi and Ronaldo in comparison to others, or how a player in a video game like Mortal Kombat or Tekken can get a higher rating than others.

It’s time you create your own Facemash or a rating-based video game. Practice your coding skills by solving HackerEarth’s challenges, which use the Elo algorithm.

If you want to read about more such amazing algorithms subscribe to our blog.