Comment estimer la force relative de deux joueurs ? Le classement Elo

La lecture de cette page nécessite des connaissances du niveau Première ou Terminale Spécialité Mathématiques.

Lorsque deux joueurs d'échecs, qui ont déjà joué de nombreuses parties, s'affrontent pour la première fois, on aimerait savoir quelle est la probabilité de victoire de l'un sur l'autre. Autrement dit, on aimerait classer des joueurs d'échecs en fonction de leur niveau de telle sorte que, même sans qu'ils ne se soient jamais rencontrés, on puisse estimer leur force relative. Le physicien et joueur d'échec américain (d'origine hongroise) Arpard Elo a développé au XX^è siècle un système de classement qui répond à ce problème. Dans cette page, nous allons vous expliquer comment ce système fonctionne. Pour le moment, on va utiliser un modèle simplifié, pour lequel il n'y a pas de match nul.

L'idée d'Elo est assez simple. Il veut attribuer une note à chaque joueur, son classement Elo. La différence de note entre deux joueurs caractérise leur force relative : si la différence entre le classement Elo de $A$ et de $B$ vaut $100$ points, et si la différence entre le classement Elo de $B$ et $C$ vaut $100$ points, il y a le même écart de force relative entre $A$ et $B$ qu'entre $B$ et $C$. Par exemple, si $A$ est deux fois plus fort que $B,$ alors $B$ sera deux fois plus fort que $C$.

Que signifie $A$ est deux fois plus fort que $B$ ? Ceci signifie que si $A$ et $B$ jouent un grand nombre de parties l'un contre l'autre, alors $A$ en remportera deux fois plus que $B.$ On est alors amené à introduire les quantités suivantes :

Ces deux quantités sont liées : il suffit de faire un petit calcul pour observer que $$P(A/B)=\frac{f(A/B)}{1+f(A/B)}.$$

On se trouve confronté maintenant au problème suivant : on a deux joueurs $A$ et $B$ de classement respectif $\textrm{Elo}(A)$ et $\textrm{Elo}(B)$. Comment déterminer la probabilité que $A$ gagne si $A$ et $B$ s'affrontent ? On va commencer par essayer d'exprimer la force relative $f(A/B)$ de $A$ par rapport à $B.$ Rappelons que cette force relative ne doit dépendre que de la différence $\textrm{Elo}(A)-\textrm{Elo}(B)$. On cherche donc une fonction $H$ telle que $$f(A/B)=H(\textrm{Elo}(A)-\textrm{Elo}(B)).$$ Cette fonction $H$ doit vérifier une propriété bien particulière. En effet, il est légitime de penser que si $A$ est deux fois plus fort que $B$, et que si $B$ est deux fois plus fort que $C,$ alors $A$ est quatre fois plus fort que $C.$ Autrement dit, on a $$f(A/C)=f(A/B)\times f(B/C).$$ Pour la fonction $H,$ cela signifie $$H(\textrm{Elo}(A)-\textrm{Elo}(C))=H(\textrm{Elo}(A)-\textrm{Elo}(B))\times H(\textrm{Elo}(B)-\textrm{Elo}(C)).$$ Si on note $D=\textrm{Elo}(A)-\textrm{Elo}(B)$ et $D'=\textrm{Elo}(B)-\textrm{Elo}(C),$ alors on doit avoir $$H(D+D')=H(D)\times H(D').$$ On reconnait ici une propriété vérifiée par les fonctions du type $x\mapsto \exp(cx),$ et pour peu que l'on suppose que $H$ est continue, on peut même prouver que ce sont les seules fonctions de ce type. Ainsi, on doit avoir $$f(A/B)=\exp(c D)$$ où $D$ est la différence $\textrm{Elo}(A)-\textrm{Elo}(B).$ En utilisant la formule donnée ci-dessus, on a $$P(A/B)=\frac{\exp(cD)}{1+\exp(cD)}=\frac{1}{1+\exp(-cD)}.$$ Dans la pratique, pour les échecs, la constance $c$ choisie est $c=\ln(10)/400,$ qui donne la formule plus jolie $$P(A/B)=\frac{1}{1+10^{-\frac{D}{400}}}$$ (si vous êtes choqué par la notation $10^x,$ elle ne signifie rien d'autre que $\exp(x\ln(10))).$

Ainsi, on a rempli la première partie du contrat. On a une fonction qui nous permet, étant donnée la différence de classement entre deux joueurs, d'estimer la probabilité qu'un joueur a de l'emporter sur un autre. Le tableau suivant donne la conversion, en donnant la probabilité $P(A/B)$ en fonction de quelques différences de classement Elo.

Si l'on se contente de ce que l'on a fait jusqu'à présent, on n'a pas complètement résolu le problème initial. On sait donner la probabilité de gain d'un joueur sur un autre connaissant la différence de classement Elo, mais on ne sait pas comment calculer le classement Elo d'un joueur ...

Arpad Elo a proposé la méthode suivante. On affecte initialement à un joueur un classement Elo arbitraire, par exemple $0.$ On notera $\textrm{Elo}(n)$ son classement après $n$ parties. On suppose qu'au cours de sa $n$-ème partie, notre joueur affronte un joueur $B$ et que la différence de classement Elo entre les deux joueurs vaut $D.$ La probabilité que $A$ gagne vaut $P(D),$ donnée par la formule précédente. On note $R$ le résultat du match : il vaut $1$ si $A$ gagne, et $0$ si $A$ perd. Alors on a $$\textrm{Elo}(n+1)=\textrm{Elo}(n)+K(R-P(D))$$ où $K$ est une constante appelée coefficient de développement.

Réfléchissons un peu à cette formule : si $A$ gagne, il est normal que son classement augmente, d'autant plus si sa probabilité de gagner était faible. Si $A$ perd, il est normal que son classement diminue, d'autant plus si sa probabilité de gagner était forte. La formule ci-dessus exprime exactement cette idée. La constante $K$ rend le classement plus ou moins volatile. Plus $K$ est élevé, plus le classement va changer après une partie. Cela peut être intéressant pour les premières parties jouées, pour évaluer plus rapidement la force d'un joueur. En revanche, quand le classement est déjà bien établi, on peut faire choisir $K$ plus petit, pour qu'une seule partie n'ait pas une influence trop forte. Aux échecs, $K=40$ pour les $30$ premières parties, puis $K$ redescend à $20$ et même à $10$ pour les joueurs forts (dont le classement est supérieur à $2400$ Elo).

Voyons un exemple : $A$ est classé $2000$ Elo et joue contre $B$ qui est classé $1900$ Elo, soit une différence de $100$ points. La probabilité que $A$ gagne vaut $$P(A/B)=\frac{1}{1+10^{-100/400}}\simeq 0,\!64.$$

Remarquons qu'une défaite de $A$ contre un joueur plus faible impacte plus fortement son classement qu'une victoire contre le même joueur.

On va maintenant vérifier que la formule permettant de mettre à jour le classement Elo fonctionne. Pour cela, on considère deux joueurs $A$ et $B$ auxquels on attribue le classement initial de $1000$ points. Puis on fait jouer $n$ fois les deux joueurs l'un contre l'autre $3$ parties, avec le résultat suivant : $A$ gagne la première et la troisième partie, $B$ gagne la deuxième partie. Ainsi, $A$ gagne deux fois sur trois et est donc deux fois plus fort que $B$. On s'attend donc, si $n$ devient très grand, à ce que la différence de classement entre les deux joueurs donne $P(A/B)\simeq 0,\!66.$

Pour vérifier cela, on peut utiliser le petit programme suivant sous Python :

Comme vous pouvez le constater, il y a environ 121 points d'écart de classement Elo entre les deux joueurs. Cela donne une probabilité théorique de gain pour $A$ valant $$P(A/B)=\frac{1}{1+10^{-121/400}}\simeq 0,\!667.$$ C'est très proche de $2/3,$ et donc cette méthode fonctionne bien !

On peut adapter la méthode précédente si on s'autorise maintenant à ce qu'une partie puisse se terminer par un match nul. On attribue cette fois un gain à chaque partie, qui vaut $1$ si $A$ gagne, $0,\!5$ s'il y a match nul et $0$ si $B$ gagne. Si $A$ et $B$ s'affrontent au cours de $N$ parties, on note $N_A$ le gain total de $A$ et $N_B$ le gain total de $B$. La force relative de $A$ par rapport à $B$ est toujours $$f(A/B)=\frac{N_A}{N_B}$$ et le gain moyen de $A$ est $P(A/B)=\frac{N_A}{N}.$ On a toujours la formule $$P(A/B)=\frac{f(A/B)}{1+f(A/B)}$$ qui nous amène, par le même développement, à la formule $$P(A/B)=\frac{1}{1+\exp(-cD)}.$$ Pour mettre à jour le classement Elo, on utilise la même formule $$\textrm{Elo}(n+1)=\textrm{Elo}(n)+K(R-P(D))$$ mais cette fois le résultat $R$ peut également valoir $0,\!5$ s'il y a match nul.

La photographie d'Arpad Elo est tirée du site : http://www.chessbase.com/newsprint.asp?newsid=4326.