Comments on Comment comparer les niveaux de joueurs à un jeu ? (et : le classement Elo aux échecs)

Il y a pas mal de biais possibles en particulier lorsqu'il s'agit de parties jouées dans le cadre d'un tournoi, essentiellement pour des raisons psychologiques.

Il est par exemple beaucoup plus facile pour un joueur faible de faire un exploit contre un joueur fort à la dérive lors de la dernière partie d'un tournoi (le joueur fort n'ayant par exemple plus grand chose à espérer ou ayant le morale à zéro) que contre ce même joueur fort lors de la 1er partie.

Un autre type de biais peut apparaitre également selon la méthode de tirage. Par exemple, en cas de système suisse accéléré (on fait jouer au début les joueurs forts entre eux et les joueurs faibles entre eux), lorsqu'un joueur faible va finalement rencontrer un joueur fort, ce sera quand le joueur fort aura commencé par perdre (plus ou moins mauvaise forme probable pour une raison ou une autre) et quand le joueur faible aura commencé par gagner (plus ou moins bonne forme probable pour une raison ou pour une autre). Dans ce type de tournoi, l'écart de force que l'on calculera entre deux joueurs de force inégale sera me semble-t-il (en moyenne) plus petit que l'écart de force réel entre les deux joueurs.

Je n'avais pas vu ton tweet (<URL: https://twitter.com/gro_tsen/status/1554401181593735168 >), mais il me semble que ma remarque donne ce que tu pourrais considérer comme une preuve plus conceptuelle : si X et Y sont indépendantes des lois exponentielles de paramètres respectifs λ et μ, on a alors :
P(X>Y) = E( P(X>Y|Y) )
= E( exp(-λY) )
= μ/(λ+μ)
Du coup, on a en notant p=P(X>Y), on a p/(1-p) = λ/μ. Ça permet de montrer la relation r/(1-r) = p/(1-p) * q/(1-q) entre les trois probabilités P(X>Y), P(Y>Z) et P(X>Z), d'où on déduit P(X>Z).

Je te cite : "La seconde partie, elle, est la définition de l'échelle de niveaux plus qu'elle n'est un postulat : on peut imaginer qu'on définit arbitrairement les joueurs de niveaux 0 et 1, puis on définit les joueurs de niveau 2 comme ceux qui ont autant de chances de gagner contre un joueur de niveau 1 qu'un joueur de niveau 1 contre un joueur de niveau 0, puis les joueurs de niveau 3 comme ceux qui ont cette même probabilité de gagner contre les joueurs de niveau 2, etc. "

Mais c'est faux, il y a aussi un postulat. Une fois qu'on a arbitrairement défini les niveaux 0 et 1, et défini le niveau 2 comme les joueurs qui ont la même probabilité p de gagner contre les niveaux 1 que les niveaux 1 contre les niveaux 0, il faut postuler que les joueurs qui ont cette même probabilité de victoire p contre les niveaux 2, ont aussi autant de chances de gagner contre un niveau 1 que un niveau 2 contre un niveau 0. Ce qui n'est pas garanti.

J'avais aussi essayé de comprendre ces histoires de classement Elo il y a quelques temps, et j'avais été assez surpris du niveau de confusion des explications de la page Wikipedia.

J'étais arrivé à l'interprétation suivante du modèle faisant intervenir la fonction logistique, qui est moins riche mathématiquement que ce que tu présentes, mais est plus simple à présenter, et en un certain sens plus naturelle : Alice a quatre fois plus de chances de gagner que de perdre contre Barbara, (soit des probabilités de gain/pertes de 4/5 et 1/5). On peut interpréter ça comme "Alice est quatre fois plus forte que Barbara", et donc aussi "Barbara et quatre fois plus forte que Carole". En supposant que les forces relatives de joueurs se comparent multiplicativement, on aurait donc envie de dire que Alice est 16 fois plus forte que Carole, donc que les probabilités de gain/perte dans ce cas seraient de 16/17 et 1/17, ce qui est l'hypothèse faite dans par le classement Elo.

Autrement dit, la probabilité r = p·q/(1−p−q+2p·q) est celle qui vérifie r/(1-r) = p/(1-p) * q/(1-q). On a donc une relation multiplicative entre les force relative des joueurs ; le classement Elo revient à passer au logarithme dans cette égalité pour avoir seulement à considérer les différence des classements de deux joueurs.

Il y a quelques stéréotypes extrêmes dans les jeux : les cycles (pierre-feuille-ciseaux), les ordres totaux (A > B > C) et le full-aléa (vainqueur tiré uniformément au hasard).

Est-il possible d'envisager un théorème de structure qui désosserait n'importe quel jeu comme une combinaison de ces stéréotypes ? Pas forcément avec la liste de stéréotypes ci-dessus, si celle-ci n'est pas la bonne…

Au lieu de s'intéresser à des jeux qui vérifient certaines conditions et de chercher à mesurer le niveau d'un joueur dans ce cadre, on pourrait alors partir d'un jeu absolument quelconque et… peut-être pas quantifier les niveaux (par des nombres réels) mais en tout cas dire des choses. Et on pourrait se poser la question du sens à associer à un jeu J le "jeu vérifiant nos conditions" K le plus proche, ou encore celle du sens à donner aux niveaux des joueurs pour K…

Je pose cette question en ayant en tête le théorème de Furstenberg qui désosse les actions ergodiques de Z sur un espace de probabilité standard en des morceaux très structurés ("arithmétiques") et des morceaux très désordonnés ("probabilistes"). Dans ce cadre, tout système se réalise comme "mélange" des stéréotypes de base. Le lemme de régularité de Szemerédi incarne le même leitmotiv dans le domaine de la théorie des graphes.

Voir par exemple : https://terrytao.wordpress.com/2007/04/07/simons-lecture-ii-structure-and-randomness-in-ergodic-theory-and-graph-theory/

Je me demande si, dans le grand voisinage des questions que tu considères, ce travail est susceptible de t'intéresser :
https://ar5iv.labs.arxiv.org/html/physics/0703122
https://www.lpt.ups-tlse.fr/spip.php?article239

La nulle aux échecs est bien plus commune à haut niveau que chez les amateurs (pas seulement les nulles de salon), donc on peut déjà se poser la question de si S(p, q) est bien indépendant du niveau…

de mémoire, pour les joueurs débutants aux échecs, ils ont le classement Elo de 1500, sachant que leur premier classement Elo effectif correspond à leur performance réelle au bout de 10 ou 15 parties (~souvenir de 1995/2000)

Ça me fait pensée à cette entrée d'il y a dix ans : http://www.madore.org/~david/weblog/d.2012-06-02.2051.amplificateur-probas.html . Peut-être qu'au tennis, on a moyen d'y arriver, à la loi gaussienne, en tant que moyenne sur plein d'échanges - quelle que soit la loi d'un échange donné ?

***

Autre question qui me vient à l'esprit. Au go, les joueurs se battent pour contrôler les 361 intersections du goban. La victoire est donnée au joueur qui a le score le plus élevé à la fin, ce "score" correspondant en gros au nombre d'intersections contrôlées (bon c'est un peu plus subtil, surtout avec les règles japonaises ; mais passons les détails). Et pour équilibrer le jeu, on attribue d'office un certain nombre de points au second joueur, le "komi" (typiquement 6.5 points). Peut-on dire quelque chose d'intelligent sur la probabilité de gagner vs. la probabilité d'atteindre tel ou tel score ?

(Bon, ce n'est peut-être pas une question si intéressante en vrai. Je la pose sans vraiment y avoir réfléchi en profondeur.)

***

Sinon, y a-t-il moyen d'introduire un nombre naturel qui mesure à quel point l'hypothèse d'unidimensionnalité est violée, i.e. à quel point la probabilité de gagner dépend non seulement de la différence de niveau mais aussi des styles de jeu ? Je serai très curieux de voir une comparaison de ces nombres pour différents jeux : entre les échecs, le go, le bridge, différents sports etc., lesquels sont les moins "unidimensionnels" ?

Je suis sans doute influencé par les threads récents de John Baez sur Twitter, mais est-ce qu'il n'y a pas moyen de faire intervenir le principe de maximum (partiel) d'entropie là-dedans ?