# Rating system incorporating experience

I am looking to rank players on something and right now I am using a win-loss percentage to "rank" the players.

The issue is that I have some people who just beat out the 5 game threshold and have a win/loss ratio of say 5 wins, 1 loss for 83% and then I have someone who has 54 wins and 10 losses for ~82%. I want to "rank" the more experienced player higher than the other, but I have no idea how to include "experience" as part of the formula.

I know there are many many ways this can be done, I am just interested in a few of the most simplistic accurate and common approaches and perhaps links to rating theory discussion when only knowing the wins and losses.

-
If you only know the win/loss ratio, you can not separate the guy with 100 wins and 0 losses, from the guy with 1 win and no losses. –  utdiscant Aug 17 '12 at 3:54
@utdiscant I fixed. I misspoke... mistyped? –  ParoX Aug 17 '12 at 4:24
–  leonbloy Aug 20 '12 at 0:15
What about increasing the success rate by $\lfloor\log_5(\text{# of games won}),2\rfloor\%$ if # of won > 5? So, 5 win will get an extra 0.00% while 54 wins get an extra 2.48% win rate. This is a I-guess-common approach, though. –  FrenzY DT. Aug 20 '12 at 7:36

One option is to use something like the beta-binomial model.

The general idea is that players' true success rates (or winning frequency) come from an underlying distribution (e.g. a beta distribution). As a player plays more games and you get actual information on wins and losses, the prior information from the beta distribution is combined with the wins/losses information which is expected to follow a binomial distribution (based on the true success rate $p$), and a posterior estimate of the success rate made as $$\hat{p}=\frac{n_{\text{wins}}+\nu\rho}{n_{\text{games}}+\nu}$$ where the beta distribution essentially has the effect of a prior information equivalent to $\nu$ games with $\rho$ success rate.

The advantage of this method is that for playes with few games, the estimated success rate is shrinked towards the population mean; extreme success rates due to highly uncertain success rate estimates for playes with few games are avoided.

Due to the similarity with Bayesian methods, this type of approach is often referred to as empirical Bayes. However, the parameters $\nu$ and $\rho$ used to specify the beta distribution are estimated using traditional frequentist methods (moment or maximum likelihood estimates).

NB: I'm assuming, although it wasn't stated clearly, that these are solitaire games: i.e. one-player games. If they are two-player games, the strength of the opponents must be taken into account. A similar approach may still be used to provide a prior distribution for the strength of new players, but that would have to be a rather different model than the beta-binomial.

As requested in the comments, here are some more details on how this is done. I'll do it using the beta-binomial model, but the same principle applies to a number of similar models (e.g. see Wikipedia's article on Empirical Bayes).

Let's assume we have $N$ players, where player $k$ has played $n_k$ times and won $x_k$ of them. We assume that player $k$ has an underlying probability $p_k$ of winning each time (the game is still solitaire, so no opponents on which this could depend) and so the number of wins, $x_k$, should come from a binomial distribution $\text{Bin}(n_k,p_k)$.

We could, of course, estimate $p_k$ based on $x_k$ and $n_k$ alone: i.e. $\hat{p}_k=x_k/n_k$. However, if $n_k$ is small, this estimate would be very uncertain.

In order to reduce the uncertainty of the estimate, we assume that the winning probabilities, $p_k$, come from a beta distribution. Why a beta distribution, you might ask? Because it is conjugate to the binomial distribution, which makes the maths easier.

Note that the beta distribution is usually defined as $$\text{Beta}(\alpha,\beta) \sim \frac{x^{\alpha-1}(1-x)^{\beta-1}}{B(\alpha,\beta)} \mbox{ where } B(\alpha,\beta)=\frac{\Gamma(\alpha)\Gamma(\beta)}{\Gamma(\alpha+\beta)}.$$ Often parameters $\rho=\alpha/(\alpha+\beta)$ and $\nu=\alpha+\beta$ are used instead (which are the ones I used above), however I'll stick to $\alpha$ and $\beta$ here to reduce confusion.

If we assume the underlying (but unknown to us) winning probability, $p_k$, is drawn from a beta distribution with parameters $\alpha, \beta$, and then $x_k$ is drawn from $\text{Bin}(n_k,p_k)$, the posterior probability distribution is $\text{Beta}(\alpha+x_k,\beta+n_k-x_k)$. The expected values of $p_k$ given $x_k$ and $n_k$ is thus $$\text{E}[p_k|x_k,n_k]=\frac{\alpha+x_k}{\alpha+\beta+n_k}.$$

The tricky part is finding good estimates for $\alpha$ and $\beta$. Remember, these parameters govern how the underlying probabilities, $p_k$, are distributed: e.g. the expected value and the variance.

I believe the preferred method will often be maximum likelihood estimates: i.e. the values of $\alpha$ and $\beta$ that maximise $$\prod_{k=1}^N \Pr(x_k|\alpha,\beta,n_k) =\prod_{k=1}^N \int_0^1 \Pr(x_k|n_k,p_k)\cdot\Pr(p_k|\alpha,\beta)\, dp_k$$ where the right-hand side contains the probability functions for the binomial distribution (of $x_k$) times that of the beta distribution (for $p_k$).

Another alternative are moment estimates.

Here's a quick walk-through of the computations.

The unknown parameters, $\alpha$ and $\beta$ of the beta distribution, describe the distribution of success probabilities of players, $p_k$ for player $k$: $$\Pr(p_k|\alpha,\beta)=\frac{p_k^{\alpha-1}(1-p_k)^{\beta-1}}{B(\alpha,\beta)}$$ where $$B(\alpha,\beta)=\int_0^1 x^{\alpha-1}(1-x)^{\beta-1} =\frac{\Gamma(\alpha)\Gamma(\beta}{\Gamma(\alpha+\beta)}$$ and $\Gamma(x)$ is the gamma-function ($\Gamma(x)=(x-1)!$ for $x\in\mathbb{N}$).

Given the success probability $p_k$ of player $k$ and the number $n_k$ of games played, the probability of $x_k$ wins is $$\Pr(x_k|p_k,n_k)={n_k\choose x_k}p_k^{x_k}(1-p_k)^{n_k-x_k}.$$

The likelihood of $x_k$ wins given $\alpha$ and $\beta$, but treating $p_k$ as an unknown, is then given by $$\begin{split} \Pr(x_k|\alpha,\beta,n_k)=&\int_0^1 \Pr(x_k|p_k,n_k)\cdot\Pr(p_k|\alpha,\beta)\,dp_k\\ =&\int_0^1 {n_k\choose x_k} \frac{p_k^{\alpha+x_k-1}(1-p_k)^{\beta+n_k-x_k-1}}{B(\alpha,\beta)}\,dp_k\\ =&{n_k\choose x_k}\frac{B(\alpha+x_k,\beta+n_k-x_k)}{B(\alpha,\beta)}. \end{split}$$

If there are $N$ players, i.e. $x=(x_1,\ldots,x_N)$ and $n=(n_1,\ldots,n_N)$ are the number of wins and games played by each player, the likelihood function, i.e. the probability of $x$ given $\alpha$ and $\beta$ is $$L(x|\alpha,\beta) =\prod_{k=1}^N \Pr(x_k|\alpha,\beta,n_k) =\prod_{k=1}^N {n_k\choose x_k}\frac{B(\alpha+x_k,\beta+n_k-x_k)}{B(\alpha,\beta)}.$$

The maximum likelihood method basically consist of finding the parameters, $\alpha$ and $\beta$, that maximises the likelihood function: i.e. the parameters that make the data as likely as possible. In order to do this, it is easier to write out the log-likelihood, i.e. the logarithm of the likelihood function, entering the expression for $B$:

$$\begin{split} l(x|\alpha,\beta)=&\ln L(x|\alpha,\beta)\\ =&\sum_{k=1}^N \ln{n_k\choose x_k}+\ln B(\alpha+x_k,\beta+n_k-x_k)-\ln B(\alpha,\beta)\\ =&\sum_{k=1}^N \Big[\ln{n_k\choose x_k}\\ &\qquad+\gamma(\alpha+x_k)+\gamma(\beta+n_k-x_k)-\gamma(\alpha+\beta+n_k)\\ &\qquad-\gamma(\alpha)-\gamma(\beta)+\gamma(\alpha+\beta)\Big]\\ \end{split}$$ where $\gamma(x)=\ln\Gamma(x)$.

Finding the $\alpha, \beta$ that maximise $l(x|\alpha,\beta)$ is done numerically, e.g. using Newtons method which involves solving $\frac{\partial}{\partial\alpha}l(x|\alpha,\beta) =\frac{\partial}{\partial\beta}l(x|\alpha,\beta)=0$. Note that the binomials ${n_k\choose x_k}$ are constant with respect to $\alpha$ and $\beta$ and so can be ignored.

For the numerical solution, it is helpful to have to digamma function $\Psi(x)=\gamma'(x)=\Gamma'(x)/\Gamma(x)$ available since the derivatives of the log-likelihood is a sum of these. For large $x$ (not close to zero), $\Psi(x)\approx\ln(x-1/2)$; for small $x$, one may use $\Psi(x)=\Psi(x+k)-\sum_{j=0}^{k-1}\frac{1}{x+j}$, although I suppose there may be more efficient ways of computing it.

The estimated values of $\alpha$ and $\beta$, i.e. the values that maximise $l(x|\alpha,\beta)$, are usually denoted $\hat\alpha$ and $\hat\beta$ to distinguish them from the actual (but unknown) values. These estimated values are then plugged in to get an estimate for the success rate of player $k$: $$\hat{p}_k=\frac{x_k+\hat\alpha}{n_k+\hat\alpha+\hat\beta}.$$

-
Using en.wikipedia.org/wiki/Beta_distribution#Parameter_estimation it seem to be more clear that the first sample moment is just the sample mean, and the second sample moment is the variance. However in en.wikipedia.org/wiki/Beta_binomial the Maximum likelihood example they show things that are way different than the sample mean and variance to represent m1 and m2. –  ParoX Aug 18 '12 at 11:04
Can you please go into detail on how you would calculate each "sucess rates" in the examples I given. –  ParoX Aug 20 '12 at 0:11
Added some more details on the method, but don't remember the details for computing the maximum likelihood estimates. –  Einar Rødland Aug 20 '12 at 9:07

You should compute a combined score that considers both the win/loss ratio and the number of games played. The combination will need a parameter that weighs how important win/loss ratio (or the number of games played) in the overall ranking. For example, the score of player 1 will be $score(p_1) = \alpha \frac{\#wins}{\#games\_played} + (1-\alpha)\frac{\#games\_played}{\#max\_num\_of\_games}$. You should set the value of $\alpha$ according to your taste or any constraints the ranking has (if any).

-
This is a good technique, but I had already known of weighting possibilities, I was looking for something with more depth and isn't so subjective to opinion (what I think α should be) –  ParoX Aug 20 '12 at 0:14
Or rather, some ideas on how to calculate an accurate α would make this a better answer –  ParoX Aug 20 '12 at 0:28
If you have example ground-truth rankings, you can fit this model to those and obtain the best $\alpha$. Otherwise, I guess it has to be subjective. –  emrea Aug 20 '12 at 2:47

Do as Microsoft's TrueSkill does. When you estimate a player's skill, quantify too the uncertainty $\sigma$ of your estimate $\mu$. This uncertainty should decrease as players accrue more results. Then, rank players by a conservative lower bound $\mu - 2\sigma$. Thus, for the situation below you would rank Experienced Eric over N00b Natalia. Natalia can prove how good she is by playing more games, and Eric can never complain her rank is due to beginner's luck.

Another boon: you can scratch your threshold and rank players as soon as they have played one game.

Image taken from the fine introduction to TrueSkill at http://www.moserware.com/2010/03/computing-your-skill.html

-

Why not look at what others are doing? In chess, the Elo rating is used for this purpose, and seems to function rather well. There are variants, but you could do worse that starting to goole "elo".. Start with: http://en.wikipedia.org/wiki/Elo_rating_system

-
From the way the question was posed, i.e. not mentioning anything about opponents, I automatically assumed these were solitaire games. But, of course, if they are two-player games, something like ELO should be used which takes opponent strength into account. Will edit my own suggestion to make that abundantly clear. –  Einar Rødland Aug 17 '12 at 18:02
Einar is right, Elo rating was my first assumption but it not a player vs player game. –  ParoX Aug 18 '12 at 1:45

Ranking, for how I see it, should be a measure of how likely a player will win next game.

The formula proposed by EmreA assumes ranking proportionally increases with number of played games and with win/played ratio and that the two contribute independently .

If you are happy with that, than you can find $\alpha$ empirically:

Divide win/played ratios and number of played games in equally spaced intervals, and record how often players with win/played ratio in a given range will win a game and how often player with number of played games in a given range will win a game.

After you collected enough data, interpolate win probabilities for win/played ratios and for number of played games over the intervals and find 2 lines. The ratio of the slopes of the 2 lines is your $\alpha$.

See that in this case an accurate $\alpha$ can only be obtained empirically as it depends on the pariticular game and on how much players get better at the particular game trough playing experience.

-