Useless Math Information #4.5: Designing the Perfect Rating System part 2

part 2 to farm contribution ahahahahahahaha

Mathematical definition of Elo

Elo is intended to measure skill. Formally, skill is how likely you are to win a game (we're still focusing on two-player for now). If a player with a high rating plays against a player with a low rating, we would expect the higher rated player to win more, on average.

Now let's define what rating is. If player A has rating $$$a$$$ and player B has rating $$$b$$$, then player A should have a $$$\sigma(\frac{a-b}{\beta})$$$, where $$$\beta = \frac{400}{\ln 10} = 173.7178$$$, and $$$\sigma()$$$ is the sigmoid function $$$\sigma(z) = \frac{1}{1+e^{-z}}$$$.

This formula looks scary, but it's just a formal way of writing the one you might be familiar with. This formula expands/simplifies to:

$$$\frac{1}{1 + e^{-\frac{a-b}{400 / \ln 10}}}$$$ $$$= \frac{1}{1 + 10^{\frac{b-a}{400}}}.$$$

You're probably more familiar with the last equation above. If you are 400 points weaker, you'd have a 1 to 10 ($$$\frac{1}{11}$$$) chance of winning; if you are 800 points weaker, you'd have a 1 to 100 ($$$\frac{1}{101}$$$) chance of winning.

Elo sucks

A good rating system should have good success at prediction on a dataset. Elo is... not good at that. It only maintains a single rating value for each player. A GM who starts at 1500 may have to win many games to get their rating up to the 2000s, and a bad player may have to slog through like 15 full games of getting destroyed by strong opponents before they finally find their rating.

Heuristically, new players' ratings should probably change faster, and they shouldn't change their opponents' ratings as much (since we are not very confident about their true skill).

"Confident"... yes, this is a job for statistics :yayy:

Modeling ratings as priors and posteriors

We have an initial belief about a player's skill level. Our first improvement will be as follows: instead of having only the rating, we will have the rating and rating deviation (RD). Essentially, we are regarding a player's true rating as an unknown variable, but we have an estimate for it in the form of a normal distribution with mean equal to the rating and standard deviation equal to the RD.

Now, we will use Bayesian likelihood estimation to update our old distribution into a new distribution (new rating and RD) with the information from the result of a game.

Get ready for some math!

We want to update our (we will update one player at a time for now) rating. Assume we start with rating $$$0$$$ for simplicity (just subtract $$$a$$$ from both sides), and our opponent has rating $$$\mu_y$$$ ($$$\mu_y=b-a$$$). Our RD is $$$\sigma_x$$$ and their RD is $$$\sigma_y$$$. Suppose we win the game.

Likelihood

What is the likelihood we win? Suppose we knew with certainty that our rating was exactly $$$x$$$ ($$$x$$$ does not have to be zero), and our opponent's rating is exactly $$$y$$$.

Then the chance that we win this game is just $$$\sigma\left(\frac{x-y}{\beta}\right)$$$.

Now let's assume that we know with certainty that our rating is exactly $$$x$$$. However, we don't know $$$y$$$, only that it's drawn from the normal distribution $$$\mu_y, \sigma_y$$$.

So we need to calculate the expectation of the likelihood $$$\sigma\left(\frac{x-y}{\beta}\right)$$$ integrated over all $$$y$$$.

This is given by

$$$L(x) = \mathbb{E}_y\left[ \sigma\left(\frac{x-y}{\beta}\right) \right] = \displaystyle\int_{-\infty}^{+\infty} \operatorname{normalpdf}(y) \cdot \sigma\left(\frac{x-y}{\beta}\right) \space dy.$$$

This integral has no solution, but can be approximated very well by:

$$$g = \sqrt{ \beta^2 + \frac{\pi}{8} \sigma_y^2 },$$$ $$$L(x) = \sigma\left(\frac{x-\mu_y}{g}\right).$$$

Here is a link to a derivation of this. I don't understand it though lol

You can play around and see how good the approximation is on this Desmos graph

Posterior distribution

Now let's use our formula

$$$\text{Posterior} = \text{Likelihood} \cdot \text{Prior},$$$ $$$P(x) = \sigma\left(\frac{x-\mu_y}{g}\right) \cdot \operatorname{npdf}\left(\frac{x}{\sigma_x}\right),$$$

where $$$\operatorname{npdf}(z)$$$ is the standard normal PDF (the probability density when you are $$$z$$$ standard deviations from the mean). The prior distribution for $$$x$$$ is centered at mean 0 with standard deviation $$$\sigma_x$$$ and thus has PDF given by $$$\operatorname{npdf}\left(\frac{x}{\sigma_x}\right)$$$.

Note that $$$P(x)$$$ is technically not a valid PDF until we normalize it and make its integral equal to 1, but that's not super important to us here.

Laplace approximation

This PDF is not normal, but it turns out it is close enough (ish) in practice that we can perform a Laplace approximation. Given a PDF, this lets us approximate it as a normal distribution by:

Mean

The estimated mean is the mode of the PDF. To find the mode of the PDF, we do derivative optimization to find the maximum of the PDF. Specifically, let's optimize $$$\ln P(x)$$$ instead.

$$$\displaystyle \ln P(x) = \ln \sigma\left(\frac{x-\mu_y}{g}\right) + \ln \operatorname{npdf}\left(\frac{x}{\sigma_x}\right),$$$ $$$\displaystyle \ln P(x) = \ln \sigma\left(\frac{x-\mu_y}{g}\right) - \frac{x^2}{2\sigma_x^2} + \ln\left(\frac{1}{\sqrt{2\pi}}\right),$$$ $$$\displaystyle \left(\ln P(x)\right)' = 0 = \frac{1 - \sigma\left(\frac{x-\mu_y}{g}\right)}{g} - \frac{x}{\sigma_x^2},$$$ $$$\displaystyle \frac{1 - \sigma\left(\frac{x-\mu_y}{g}\right)}{g} = \frac{x}{\sigma_x^2}.$$$

In order to solve this for for $$$x$$$, we can either

use a linear approximation for $$$\sigma()$$$ and then solve analytically, or
for better accuracy, use a higher degree polynomial approximation, or use numerical methods like Newton's method or binary/ternary search.

For now, I'll show you the linear approximation (technically quadratic, since the coefficient for the squared term is zero) method $$$\sigma(z) \approx \frac{1}{2} + \frac{1}{4}z$$$, but be aware that it does start giving questionable results when the difference in ratings of the two players is very large.

$$$\displaystyle 1 - \left( \frac{1}{2} + \frac{x-\mu_y}{4g} \right) = \frac{xg}{\sigma_x^2},$$$ $$$\displaystyle \overline{x} = \frac{ \frac{1}{2} + \frac{\mu_y}{4g} }{ \frac{g}{\sigma_x^2} + \frac{1}{4g} }.$$$

Variance/standard deviation

Let's calculate the precision, which is equal to the negative second derivative of the log PDF evaluated at our new estimate $$$\overline{x}$$$.

$$$p = -(\ln P(x))' '$$$ $$$\displaystyle p = -\left[ \frac{ - \sigma\left(\frac{\overline x}{g}\right) \left(1 - \sigma\left(\frac{\overline x}{g}\right)\right) }{g^2} - \frac{1}{\sigma_x^2} \right],$$$ $$$\displaystyle p = \frac{ \sigma\left(\frac{\overline x}{g}\right) \left(1 - \sigma\left(\frac{\overline x}{g}\right)\right) }{g^2} + \frac{1}{\sigma_x^2}.$$$

Then the new standard deviation is $$$p^{-1/2}$$$.

$$$\displaystyle \sigma_{new} = \left[ \frac{ \sigma\left(\frac{\overline x}{g}\right) \left(1 - \sigma\left(\frac{\overline x}{g}\right)\right) }{g^2} + \frac{1}{\sigma_x^2} \right]^{-\frac{1}{2}}.$$$

Conclusion

And there you have it! That is how to update the rating and RD of a player. Remember that $$$\overline x$$$ is the new rating if the old rating was $$$0$$$, so it's actually the rating delta in this case. You'd repeat the same thing for the opponent who lost. It turns out that when you lose, the formulas are just the same, you just subtract $$$\overline x$$$ instead of adding it for the winning player.

You can see a visualization of how good the Laplace approximation is compared to the actual PDF in this Desmos calculator. You'll see that the approximation is very strong when $$$\mu_y$$$ is small, and also when $$$\sigma_x$$$ is small — but when $$$\sigma_x$$$ is large the approximation only drifts off a little bit, but when $$$\mu_y$$$ is very negative you might lose rating from winning a game...

However, if you try using a constant approximation:

$$$\displaystyle \sigma\left(\frac{x-\mu_y}{g}\right) \approx \sigma\left(-\frac{\mu_y}{g}\right),$$$

you get the update formula

$$$\displaystyle x = \frac{\sigma_x^2}{g} \cdot \left(1 - \sigma\left(-\frac{\mu_y}{g}\right)\right),$$$

which does work much better for very negative $$$\mu_y$$$, but is slightly worse everywhere else. Probably the best approach is a hybrid approach: use a linear approximation, but use a Taylor polynomial centered at $$$-\frac{\mu_y}{g}$$$ instead of always centering it at zero. But that gets deep into notation hell and I'm lazy.

Otherwise, this is a rating system derived entirely from statistics! If you read Mark Glickman's Glicko paper, you may notice a lot of similarities with mine, since they're both based on similar ideas (each player is modeled by a normal distribution, Elo-style sigmoid likelihood). If you have any questions, please ask! (or tell me if I made a mistake lol)

I have used this system on my minecraft server to great success :)