Comparer et classer

Force relative des joueurs

Quand une partie se termine on s’intéresse surtout au premier mais certains se battent pour la seconde place. C’est que le classement a son importance dans l’esprit des compétiteurs. A l’issue d’une partie on comptabilise généralement les points de victoire et ça permet de classer les joueurs ayant participé à la partie.

Ce qui nous intéresse aujourd’hui est très différent, il s’agit de classement. Si on considère un jeu opposant deux joueurs. Dans une première partie le joueur A l’emporte sur le joueur B. Dans une seconde partie B l’emporte sur C. On a envie d’établir le classement suivant A > B > C. Mais une partie ne suffit pas à déterminer si un joueur est plus fort qu’un autre. Il faudrait pour ça un grand nombre de parties.

Imaginons que les trois joueurs aient disputé un très grand nombre de parties et qu’on connaisse le pourcentage p de victoires du joueur A contre le joueur B. On peut considérer que la probabilité que A gagne contre B est égale à p, faute de mieux.

Si sur 40 parties opposant A et B le joueur A en a gagné 30 alors on peut supposer que la probabilité de victoire de A contre B est \dfrac{30}{40}=0,75 ou encore 75~\%. On le notera P(A/B)=0,75 et on le lira

« La probabilité de victoire du joueur A sur le joueur B est de 0,75 »

Du point de vue du joueur B on obtient d’ailleurs P(B/A)=1-P(A/B)=0,25. En effet, leurs pourcentages de victoires se complètent pour redonner 100~\%. On obtient le même résultat en passant par la fraction \dfrac{10}{40}=0,25=25~\%.

Si on considère que cette probabilité mesure la force d’un joueur relativement à un autre on peut maintenant dire que A est trois fois plus fort que B. En effet A a gagné 30 parties alors que B n’en a gagné que 10. On obtient le même résultat en faisant le rapport de leur force \dfrac{P(A/B)}{P(B/A)}=\dfrac{0,75}{0,25}=3.

On est donc maintenant près à transférer cette notion de force entre nos trois joueurs de tout à l’heure. Supposons qu’on connaisse les pourcentages de victoire de différents duels P(A/B)=a et P(B/C)=b.

On peut maintenant estimer que la force de A contre B est \dfrac{P(A/B)}{P(B/A)}=\dfrac{a}{1-a} et de la même manière que la force de B contre C est \dfrac{b}{1-b}.

Si on note f la fonction x\longmapsto\dfrac{x}{1-x} alors la force de A contre B sera f(a) et la force de B contre C f(b).

Si on cherche maintenant la force de A contre C il suffit de multiplier entre elles les forces relatives des joueurs.

f(c)=f(a)\times f(b).

En effet, si A est 3 fois plus fort que B et que B est 2 fois plus fort que C alors A sera 3\times 2=6 fois plus fort que C.

Enfin comme f(c)=\dfrac{c}{1-c} on en déduit que

f(c)\times (1-c)=c

f(c)\times 1-f(c)\times c=c

f(c)=f(c)\times c+c

c\times (1+f(c))=f(c)

Et finalement

c=\dfrac{f(c)}{1+f(c)}.

On vient d’établir ce qu’on peut appeler des forces relatives entre joueurs et avec la multiplication on vient d’estimer ces forces entre deux joueurs qui ne se sont pas affrontés. De cette manière on peut obtenir un classement entre un grand nombre de joueurs sans qu’ils ne se soient tous affrontés.

On peut maintenant regarder un petit exemple.

Imaginons que a=P(A/B)=70~\% et que b=P(B/C)=60~\%. En termes plus clair le joueur A a gagné 70~\% de ses duels contre B. De son côté B a gagné 60~\% des siens contre C.

On peut donc estimer le pourcentage c de victoire de A contre le joueur C.

f(c)=f(a)\times f(b)=\dfrac{0,7}{1-0,7}\times\dfrac{0,6}{1-0,6}=\dfrac{70}{30}\dfrac{60}{40}=\dfrac{70\times 60}{30\times 40}=\dfrac{4200}{1200}=\dfrac{42}{12}=\dfrac{6\times 7}{6\times 2}=\dfrac{7}{2}=3,5.

J’ai un exagéré sur les calculs fractionnaires mais finalement A sera estimé 3,5 fois plus fort que C. C’est à dire que

c=\dfrac{f(c)}{1+f(c)}=\dfrac{3,5}{1+3,5}=\dfrac{3,5}{4,5}=\dfrac{7}{9}\approx 77,7~\%.

Dit autrement on estime que le joueur A devrait gagner environ 78~\% des parties contre C.

Ecarts de points

Maintenant qu’on dispose d’une estimation de la force relative entre deux joueurs, on souhaite établir un véritable système de classement.

Pour commencer, on va remplacer le produit des forces par une somme, beaucoup plus simple à mettre en œuvre. C’est ce que permet la fonction logarithmique.

Par définition, si a et b sont deux nombres strictement positifs, on a \log(a\times b)=\log(a)+\log(b).

Revenons à nos deux joueurs A et B et notons à nouveau a la force relative de A contre B. Si a=3, c’est à dire si A gagne trois fois plus souvent que B, on obtient f(a)=\dfrac{3}{1+3}=\dfrac{3}{4}=0,75=75~\%. Ce qui correspond bien à une situation où quand B gagne 1 partie, A en gagne 3 pour un total de 3+1=4 parties jouées.

Avec un système additionnel de point, et à l’aide de la fonction logarithme, l’écart de points entre A et B serait

\log(3)\approx 0,477 points d’écart en faveur de A.

S’il y a 0,477 points d’écart entre un joueur et un autre trois fois moins fort, on imagine mal ce qui va séparer deux joueurs de niveaux plus proches. On va donc appliquer un facteur multiplicatif à notre fonction qui calculera les écarts entre joueurs pour étaler les différences de points sur une plus grande plage de valeurs.

Dans le cas du classement ELO (utilisé pour les échecs) il a été choisi un facteur 400. Je vais faire le même choix pour la suite, c’est ce classement qui m’intéresse car c’est aussi celui qui a été choisi sur le site de jeu Boardgamearena.com pour classer les joueurs avant une refonte du système de classement.

On peut maintenant établir notre fonction d’écart

D(a)=400\times\log(f(a))=400\times\log\left(\dfrac{a}{1-a}\right).

Maintenant D(3)=400\times \log(3)\approx 190,848 qu’on arrondi à 191 points d’écart. Avec ce système de classement un joueur trois fois plus fort qu’un autre aura 191 points de plus.

De la même manière je vous laisse vérifier qu’un joueur deux fois plus fort qu’un autre a 120 points de plus que lui au classement.

Enfin si A est trois fois plus fort que B il a 191 points de plus au classement. Si B est deux fois plus fort que C il a 120 points de plus que C. Et on peut vérifier qu’entre A et C il y a bien 191+120=311 points d’écart avec

D(3\times2)=D(6)=4\times \log(6)\approx 311,261.

Comme dirait Hannibal, j’aime bien qu’un plan se déroule sans accrocs.

Le classement

Pour établir notre classement il reste à définir une valeur par défaut pour un joueur entrant et un mode d’attribution des points après une partie entre deux joueurs.

A ce stade on peut faire ce qu’on veut. Par exemple attribuer un classement de 1000 points à un joueur entrant dans le classement. C’est arbitraire mais on doit passer par là pour le lancement. On parle d’initialisation du classement.

Chaque nouveau joueur qui rejoindra le classement plus tard pourra lui aussi se voir attribuer 1000 points comme les autres.

Il peut aussi être intéressant de « booster » les points gagnés par un nouvel entrant pour qu’il se stabilise rapidement à son niveau sans attendre de devoir jouer contre un grand nombre de joueur. Rien de plus décourageant pour un très bon joueur que de peiner à monter à son niveau, partie après partie, quand rien d’autre que le temps de jeu ne le sépare des premiers au classement d’un niveau équivalent au sien.

Petit retour sur la formule D(a)=400\times\log\left(\dfrac{a}{1-a}\right) qui donne l’écart D de points au classement entre deux joueurs A et B pour une force relative a du joueur A sur le joueur B. Je vous épargne les étapes, mais on peut renverser les rôles et obtenir la force relative a en fonction de l’écart D entre les joueurs. Ce qui s’écrit

a(D)=\dfrac{1}{1+10^{-\dfrac{D}{400}}}

Cette formule exprime la probabilité de victoire de A contre B connaissant l’écart de points entre ces deux joueurs.

Par exemple s’il y a 100 points d’écart entre les deux joueurs on obtient

a(100)=\dfrac{1}{1+10^{-\dfrac{100}{400}}}\approx 0,64 soit 64~\% environ.

Au passage, si on prend le point de vue du joueur B l’écart de points avec A est -100 et on obtient

a(-100)=\dfrac{1}{1+10^{-\dfrac{-100}{400}}}\approx 0,36 soit 36~\% environ.

On est proche d’une situation où A est deux fois plus fort que B comme tout à l’heure.

Pour finaliser le système de classement il reste à attribuer les points entre deux joueurs en fonction de leur classement.

Si A gagne il a réalisé 100~\% de victoire sur une partie qui lui était donnée gagnante à 64~\%. Il a dépassé de 100-64=36~\% l’estimation de gain. Si c’est le joueur B qui gagne il aura déjoué les pronostics de 100-36=64~\%.

D’une certaine manière, le joueur B était supposé deux fois moins fort environ que le joueur A donc s’il gagne il aura un gain deux fois plus important.

On opère là aussi un facteur multiplicatif à l’écart entre l’estimation de la victoire et le résultat de la rencontre sous la forme

K\times (W-a(D))

W représente le résultat de la rencontre (0 en cas de défaite de A, \dfrac{1}{2}=0,5 en cas de match nul et 1 en cas de victoire). On utilise W pour Win.

Ce facteur K sert à attribuer une certaine valeur de points selon le résultat du match.

Si K est très faible, un match gagné ou perdu fera perdre ou gagné peu de points. Au contraire, s’il est trop grand il chamboulera fortement le classement.

Je parlais tout à l’heure de booster les joueurs entrants. On peut jouer sur la valeur de K selon le classement des joueurs.

Dans le classement ELO K=40 pour les trente premières parties. Puis K=20 pour un classement inférieur à 2400. Et au-delà K=10.

Cas pratiques

Un joueur A a 1000 points, il débute dans le classement. Il joue sa toute première partie contre un joueur B classé 1300 et gagne. Calculons les points qu’il gagne.

Comme le joueur A a joué moins de 30 parties on a K=40, W=1 car il a gagné et D=-300 car il a 300 points de moins au classement que son adversaire.

40\times(1-a(-300))\approx 34 points gagnés. Il passe donc à 1000+34=1034 points au classement.

Si maintenant il avait perdu contre cet adversaire il aurait obtenu

40\times(0-a(-300))\approx -6 points. Et serait donc passé à 1000-6=994 points au classement.

Autre situation. J’ai 1500 points au classement et j’ai plus de trente parties à mon actif. Je lance un défi à un joueur classé 1650. Je gagne les trois parties d’affilée. Quel sera mon classement après ces trois parties ?

1500+20\times(1-a(-150))\approx 1514 pour la première partie.

Attention, maintenant le perdant a maintenant un classement de 1650-14=1636 donc ils sont à 122 points d’écart.

1514+20\times(1-a(-122))\approx 1527 pour la seconde partie. Et un classement de 1623 pour le perdant. La seconde partie a rapporté légèrement moins de points.

1527+20\times(1-a(-96))\approx 1540 pour la troisième et dernière partie. Et un classement de 1610 pour le perdant.

Les classements des deux joueurs se rapprochent de moins en moins vite car leur force relative tendent l’une vers l’autre. Jusqu’à la situation d’un match nul entre deux joueurs de même force qui donne exactement 10 points au gagnant.

On peut considérer K comme le montant de points en jeu. On l’a vu dans le premier exemple, l’écart de points dans la situation où le joueur A gagne (+34) ou perd (-6) donne justement ces 40 points. Le classement des deux joueurs est en quelque sorte une manière de placer un curseur à l’intérieur de cette mise de 40 points. Si nous sommes de force égale le curseur est au milieu. Si je suis plus faible que mon adversaire le curseur est plus proche de lui et j’aurai plus de points en cas de victoire. Etc.

Vous pouvez maintenant adapter ce principe de classement à votre cercle de joueurs ou votre association si ça vous tente. Ou juste vous satisfaire d’avoir appris quelque chose d’inutile et donc d’indispensable.

2 commentaires sur “Comparer et classer”

  1. Merci pour cet article fort intéressant.
    Je crois qu’il y a 2 fautes de frappes sur les formules de la rubrique « écart de points ».

    Bonne continuation

    1. Bonjour et merci pour ton commentaire. J’ai trouvé une parenthèse oubliée mais rien d’autre. Tu penses à quelle formule ?

Laisser un commentaire