ESTIMATING
DIFFERENCES in RATING

Browser engines vary somewhat in how they render MathML and I have been unable to compensate entirely. In particular, browsers that use Blink (such as Chromium) ignore ink when computing a box’s inline size, which causes spacing problems, and the vertical offsets of some subscripts are incorrect. Browsers that use WebKit (such as Safari) exhibit more serious problems, but I do not have access to a browser with the developer tools to effectively debug them.

I recommend reading this page with a browser that uses Gecko (such as Firefox) , which will render the page correctly.

Sections method i Game Pairs & the Likelihood Function Sequential Probability Ratio Testing method ii Matches & the Pentanomial Distribution The Posterior Distribution, Uniform Priors, & Use of the Posterior method iii Sequential Bayesian Testing foundation Outcome Models Appendix

§ Game Pairs & the Likelihood Function

When games are scored 1–0, ½ – ½, or 0–1, there are five outcomes for the score of a game pair: 2–0, 1½ – ½, ..., and 0–2. Let’s number these outcomes 1, 2, ..., 5 and write ${\mathrm{p}}_{\text{<span class="score">1</span>}}$, ${\mathrm{p}}_{\text{<span class="score">2</span>}}$, ..., ${\mathrm{p}}_{\text{<span class="score">5</span>}}$ for the expectations of each respectively. That is, the score of a game pair is a random variable X with a probability mass function $\mathrm{p}(\mathrm{i})={\mathrm{p}}_{\mathrm{i}}$ .

Given a particular outcome x and a model $\mathrm{m}(𝜗)=⟨{\mathrm{p}}_{\text{<span class="score">1</span>}}\text{,}\text{. . .}\text{,}{\mathrm{p}}_{\text{<span class="score">5</span>}}⟩$ of the score of a game pair as a function of rating difference $𝜗$, the likelihood function is

For example, if the outcome is 1½ – ½, then ${ℒ}_{\text{<span class="score">2</span>}}(𝜗)={\mathrm{p}}_{\text{<span class="score">2</span>}}$. Note that although $\mathrm{p}(\text{–})$ is a probability distribution, ${ℒ}_{\mathrm{x}}(\text{–})$ is not; in other words, $\sum {\mathrm{p}}_{\mathrm{i}}=\text{1}$ for $\mathrm{i}=\text{<span class="score">1</span>}\text{,}\text{. . .}\text{,}\text{<span class="score">5</span>}$ , whereas $\sum {ℒ}_{\mathrm{x}}(𝜗)$ from $𝜗=-\infty$ to $+\infty$ can be any nonnegative value.

§ Sequential Probability Ratio Testing

Given two particular hypotheses, ${\mathrm{H}}_0:𝜗={𝜗}_0$ and ${\mathrm{H}}_1:𝜗={𝜗}_1$, the likelihood ratio is

Commonly ${𝜗}_0=0$, so ${\mathrm{H}}_0$ is the null hypothesis: “the players have the same rating”.

For a sequence ${\mathrm{z}}_1$ , ${\mathrm{z}}_2$ , ... of outcomes, define the series S with ${\mathrm{S}}_0=0$ and

Then sprt is the following procedure:

Given two thresholds a and b (where $\mathrm{a}<0$ and $0<\mathrm{b}$), starting from time $\mathrm{t}=\text{1}$ , observe each outcome ${\mathrm{z}}_{\mathrm{t}}$ , calculate ${\mathrm{S}}_{\mathrm{t}}$ , and compare it to a and b.

• While $\mathrm{a}<{\mathrm{S}}_{\mathrm{t}}<\mathrm{b}$, continue observing.
• When ${\mathrm{S}}_{\mathrm{t}}\le \mathrm{a}$, reject ${\mathrm{H}}_1$ and accept ${\mathrm{H}}_0$.
• When $\mathrm{b}\le {\mathrm{S}}_{\mathrm{t}}$ , reject ${\mathrm{H}}_0$ and accept ${\mathrm{H}}_1$.

The thresholds a and b that correspond to the probability $\mathrm{\alpha }$ of a false positive and the probability $\mathrm{\beta }$ of a false negative are

When $\mathrm{\alpha }=$0 . 05 and $\mathrm{\beta }=$0 . 05 , their values are $\mathrm{a}=-$2 . 94 and $\mathrm{b}=+$2 . 94 .

to·do The generalized sequential probability ratio test deserves a section.

Sprt requires two hypotheses to compare, but we may only care that a player is rated higher at all, not that a player is rated higher by a particular amount (more likely to be rated higher by that amount than being rated equal, anyway). It is also agnostic to any prior beliefs about the rating difference, assuming implicitly that one hypothesis is (initially) just as plausible as the other.

As far as I am aware, this first concern is not significant; sprt is perfectly sufficient, although the results of testing may be difficult to interpret. The second concern is rare, as our knowledge prior to testing may be relatively weak. However, when we do want results that are more directly interpretable or we do have some significant bias, we can use another method.

§ Matches & the Pentanomial Distribution

For any random variable with five possible outcomes, where ${\mathrm{p}}_{\mathrm{i}}$ is the probability of outcome i, the pentanomial distribution gives the prob­ability of sampling the vari­able n times and observing each of the outcomes ${\mathrm{x}}_{\mathrm{i}}$ times:

Instead of representing the score of a single game pair, X now represents the score of a match, and an outcome x is now a collection $⟨{\mathrm{x}}_{\text{<span class="score">1</span>}}\text{,}\text{. . .}\text{,}{\mathrm{x}}_{\text{<span class="score">5</span>}}⟩$. For example, ${\mathrm{x}}_{\text{<span class="score">1</span>}}$ is the number of game pairs where the outcome was 2–0.

Given a particular match outcome x and a model $\mathrm{m}(𝜗)=⟨{\mathrm{p}}_{\text{<span class="score">1</span>}}\text{,}\text{. . .}\text{,}{\mathrm{p}}_{\text{<span class="score">5</span>}}⟩$ of the score of a game pair as a function of rating difference $𝜗$,

§ The Posterior Distribution

Given a particular match outcome x, we can find the probability

or more explicitly,

where

leaving only the prior $\mathrm{P}(𝜗)$ to be determined.

$\mathrm{P}(𝜗|\mathrm{x})$ is the probability that the diff­er­ence in rating is $𝜗$ given the observed match outcome. Unlike ${ℒ}_{\mathrm{x}}(\text{–})=\mathrm{P}(\mathrm{x}|\text{–})$, the function $\mathrm{P}(\text{–}|\mathrm{x})$ is a distribution.

§ Uniform Priors

We can use as a prior a uniform distribution

over some interval $[\mathrm{a}\text{,}\mathrm{b}]$, and in particular, we can set $\mathrm{a}=-\mathrm{L}/2$ and $\mathrm{b}=+\mathrm{L}/2$ for some L so that $\mathrm{P}(𝜗)=1/(\mathrm{L}+1)=\mathrm{\lambda }$ over the support.

Then

and $\mathrm{\lambda }$ cancels, giving us

which is simply $\mathrm{P}(\mathrm{x}|𝜗)$ normalized to have unit area over the support.

We can then consider the limit

This converges for the outcome models given below, so ${\text{lim}}_{\mathrm{L}\to \infty }\mathrm{P}(𝜗|\mathrm{x})$ exists. And in this sense, then, it is reasonable to talk about having a “uniform prior over all the integers”.

to·do Conditions for convergence and a proof of convergence deserve an appendix.

It is, of course, not necessary to use a uniform prior, but in the absence of any reason to assume a different prior it is perhaps the best default.

§ Use of the Posterior

Perhaps more useful than $\mathrm{P}(𝜗|\mathrm{x})$ is its cumulative distribution function,

As an alternative to sprt, one might stop a test when the probability that the rating difference is negative, $\mathrm{C}(0)$, is less than some threshold (say, 5% to accept a change) or greater than some threshold (say, 95% to reject a change).

to-do This section needs further elaboration.

to-do A better stopping condition might be when the dispersion is low enough (say, the variance, or the width ${𝜗}_{\mathrm{hi}}-{𝜗}_{\mathrm{lo}}$ of the hdi where $\mathrm{P}({𝜗}_{\mathrm{lo}})=\mathrm{P}({𝜗}_{\mathrm{hi}})=0.05$, or the width ${𝜗}_{\mathrm{hi}}-{𝜗}_{\mathrm{lo}}$ where $\mathrm{C}({𝜗}_{\mathrm{lo}})=0.05$ and $\mathrm{C}({𝜗}_{\mathrm{hi}})=0.95$).

§ Sequential Bayesian Testing

to-do Sequential Bayesian analysis.

§ Outcome Models

For a game between two players, a and b, let’s write w for the expectation of a win for player a, and d for the expectation of a draw, and l for the expectation of a loss for player a, so that $\mathrm{w}+\mathrm{d}+\mathrm{l}=1$. The expected composite score for player a is $\mathrm{s}=\mathrm{w}+\mathrm{½}\mathrm{d}$.

For our purposes, a rating system is a map from

• a rating difference $𝜗$
• zero or more parameters that characterize the conditions of a game

to an expected composite score s.

A game model is a map from

• a rating difference $𝜗$
• zero or more parameters that characterize the conditions of a game

to a distribution $⟨\mathrm{w}\text{,}\mathrm{d}\text{,}\mathrm{l}⟩$.

A game model can induce a rating system because s is determined by w and d, but the reverse does not hold; w and d cannot be teased apart from s alone. But in any case, we usually think of rating systems as existing independently of game models.

In the Elo rating system, the expected composite score of a player rated $𝜗$ points higher than their opponent is $1/(1+{10}^{-𝜗/400})$ . This ignores, for example, the drawishness of an opening, any advantage conferred by an opening, and the effect of time control; an Elo rating therefore indicates a player’s performance averaged over some particular gamut of conditions.

For a rating system, this simplicity is perfectly alright so long as we are aware of the conditions for which a rating is applicable. A game model, however, is greatly improved by additional parameters, because they allow us to account for variation within the gamut to estimate a player’s rating more quickly.

The logistic function $\mathrm{ſ}(\mathrm{x})=1/(1+{10}^{-\mathrm{x}/400})$ happens to be the only component of the Elo rating system, ${\mathrm{s}}_{\mathrm{e}}(𝜗)=\mathrm{ſ}(𝜗)$, but it also appears in the models presented in the following sections, for which $\mathrm{s}(𝜗)\ne \mathrm{ſ}(𝜗)$, and thus it is given a separate name.

Conventionally, an evaluation of +100 centipawn (where “centipawn” is an engine unit) corresponds to an expectation of a composite score of ¾ , implying that a 100 centipawn advantage ought to be equiv­alent to a difference of about 191 Elo points:

In fact, we might simply define the metric for opening advantage to be identical to rating difference, but scaled so that 1 unit of advantage is equivalent to 1.91 rating points, and also name this unit a “centipawn”.

This allows us to account for opening advantage when using a rating system or game model that does not otherwise consider it. For example, from the Elo rating system ${\mathrm{s}}_{\mathrm{e}}(𝜗)$ we could construct a rating system ${\mathrm{s}}_{\mathrm{e}\text{+}}(𝜗\text{,}𝜉)$ where the expected com­posite score is

when the opening advantage is $𝜉$ centipawn as just defined.

Rather than taking this perspective, however, let’s continue to use ${\mathrm{s}}_{\mathrm{e}}(\text{–})$ and instead fold the opening advantage into the rating difference, and let’s refer to $𝜗+1.91\times 𝜉$ as the effective rating difference, ${𝜗}^{\star }$.

A better rating system might depend upon $𝜉$ in a more complicated way. We defined the metric for opening advantage as we did for expediency, but it would probably be much preferable for $\mathrm{s}(0\text{,}𝜉)$ to closely follow the relationship between an engine’s evaluation and expected composite score, because querying an engine is the most straightforward way to estimate the advantage of an opening position. The metric we are adopting here, however, may only agree with an engine at $\mathrm{s}(0\text{,}+100)=\text{¾}$ .

Models for Individual Games

The following models have two parameters, ${\mathrm{d}}_0$ and q .

• The parameter ${\mathrm{d}}_0$ is the expectation of a draw when the effective rating difference is zero, so $\mathrm{d}(0)={\mathrm{d}}_0$.
• The parameter q is the effective rating difference for which the expectation of a win is ½, so $\mathrm{w}(\mathrm{q})=\mathrm{½}$ .

Note that q is not the effective rating difference for which the expected composite score $\mathrm{s}=\mathrm{w}+\mathrm{½}\mathrm{d}$ is ¾ . For any particular value of ${\mathrm{d}}_0$, however, the parameter q can be adjusted so that, for example, an effective rating difference of +191 does map exactly to an expected composite score of ¾ .

In the formulas for these two models, instead of writing “${𝜗}^{\star }$” like we ought, let’s write “$𝜗$” to make things easier to read.

Rao-Kupper Model

Davidson Model

You can compare and interact with these models on Desmos.

Models for Pairs of Games

to-do This section needs to be finished.

For any game model, there is a game pair model.

For a game pair where the players alternate (playing once as white/sente and once as black/gote), let’s write $⟨{\mathrm{w}}_1\text{,}{\mathrm{d}}_1\text{,}{\mathrm{l}}_1⟩$ for when a is the first player and $⟨{\mathrm{w}}_2\text{,}{\mathrm{d}}_2\text{,}{\mathrm{l}}_2⟩$ for when a is the second player.

Then the expectation of each outcome of the game pair is

${\mathrm{p}}_{\text{<span class="score">1</span>}}$$={\mathrm{w}}_1{\mathrm{w}}_2$ ${\mathrm{p}}_{\text{<span class="score">2</span>}}$$={\mathrm{w}}_1{\mathrm{d}}_2+{\mathrm{d}}_1{\mathrm{w}}_2$ ${\mathrm{p}}_{\text{<span class="score">3</span>}}$$={\mathrm{w}}_1{\mathrm{l}}_2+{\mathrm{d}}_1{\mathrm{d}}_2+{\mathrm{l}}_1{\mathrm{w}}_2$ ${\mathrm{p}}_{\text{<span class="score">4</span>}}$$={\mathrm{d}}_1{\mathrm{l}}_2+{\mathrm{l}}_1{\mathrm{d}}_2$ ${\mathrm{p}}_{\text{<span class="score">5</span>}}$$={\mathrm{l}}_1{\mathrm{l}}_2\text{.}$

Given a constant $𝜉$ , this is model $\mathrm{m}(𝜗)=⟨{\mathrm{p}}_{\text{<span class="score">1</span>}}\text{,}\text{. . .}\text{,}{\mathrm{p}}_{\text{<span class="score">5</span>}}⟩$ in the first and second sections.

This is a little weird, b/c it’s unlikely every opening in the book has the same advantage, but we approximate by taking the average advantage.

§ Appendix

The pentanomial distribution is difficult to compute exactly when n is large because the factorials grow very quickly.

Instead, we can rewrite this expression as

and then approximate factorial as

so that

We can then write a subroutine like the following:

define multinomial(x : Array(u64), p : Array(f64))
  mutable log-power : f64
  mutable int-coeff : u64
  mutable tau-coeff : u64
  mutable log-sqrt  : f64

  n = sum(x)
  if n > 20
    ※ n! is large so we approximate
    log-power = n as f64 × log(n as f64)
    int-coeff = −n
    tau-coeff = 1
    log-sqrt  = log(n as f64 + 1/6)
  else
    ※ n! is less than 2⁶⁴
    log-power = log(factorial(n) as f64)
    int-coeff = 0
    tau-coeff = 0
    log-sqrt  = 0
  end

  for i in 0, ..., length(x) − 1
    if x[i] > 20
      log-power <- log-power − x[i] as f64 × log(x[i] as f64)
      int-coeff <- int-coeff + x[i]
      tau-coeff <- tau-coeff − 1
      log-sqrt  <- log-sqrt  − log(x[i] as f64 + 1/6)
    else
      log-power <- log-power − log(factorial(x[i]) as f64)
    end
    log-power <- log-power + x[i] as f64 × log(p[i])
  end

  terms = log-power
        + int-coeff
        + tau-coeff × 1/2 × log(tau)
        + 1/2 × log-sqrt

  return exp(terms)
end

§ Further Reading

Statistical Methods and Algorithms in Fishtest
Stockfish Testing Framework sprt Calculator
Generalized Sequential Probability Ratio Test
Normalized Elo
Comments on Normalized Elo
From the Draw Ratio to Normalized Elo
The Accounting Identity
Bayesian Elo Rating
The Match Score as a Statistic for Comparing Engines
Modeling Game Outcomes in Chess
The Stockfish wdl Model