headlogo

Who is the master?

photo de garde

An english version of this text is available here .

Le problème du classement des joueurs d'échecs est très ancien. Avant 1970, plusieurs systèmes ont coexisté: Ingo de Anton Hoesslinger (Allemagne), le système Harkness utilisé aux USA et conçu par Kenneth Harkness ou le système anglais conçu par Richard Clark.
A partir des années 70, ces systèmes furent tous remplacés par le système ELO, conçu par Arpad Elo, autour de l'idée que les performances d'un joueur suivent une loi de variable aléatoire normalement distribuée. A l'heure actuelle, des raffinements de ce système ont été proposés, comme Chessmetrics (par Jeff Sonas), ou Glicko (par Mark Glickman) qui est utilisé pour classer les joueurs sur de nombreux sites d'échecs en ligne.
Ces systèmes partagent tous le même principe: ils déduisent le classement des joueurs à partir des résultats des parties qu'ils jouent, et non en fonction de la qualité de leurs coups. Ainsi, il est tout à fait possible de gagner des points et des places dans le classement ELO, même si l'on a mal joué, si votre adversaire a simplement joué plus mal que vous. Ce phénomène est supposé se compenser statistiquement sur le nombre de parties jouées, mais il existe un autre effet plus pervers. Comme les points sont ajoutés (ou soustraits) en fonction des résultats de parties jouées, le système ELO est statistiquement fiable sur une population de joueurs opérant à la même époque. Il est en revanche plus difficile de savoir si le classement ELO de 1970 est comparable avec le classement ELO de 2016, un phénomène connu en anglais sous le nom de "drifting", ou dérive. Cela rend évidemment impossible la comparaison objective de joueurs célèbres comme Robert Fischer, Gary Kasparov ou Magnus Carlsen, et explique le nombre d'articles, ou mêmes de livres (par exemple celui de Raymond Keene et Nathan Divinsky: Warriors of the Mind, A Quest for the Supreme Genius of the Chess Board) qui tentent de trouver le "meilleur" joueur d'échecs de tous les temps.

En 2006, Guid et Bratko (Computer analysis of World Chess Champions, ICGA journal, 29-2, 2006) ont développé l'idée originale que l'on pouvait classer les joueurs d'échecs non pas en fonction du résultat de leurs parties, mais en comparant les coups qu'ils jouent aux coups que jouerait un ordinateur. L'idée sous-jacente était qu'un bon programme d'ordinateur en 2006 était meilleur que la grande majorité des joueurs humains, et qu'en regardant le pourcentage de coups "parfaits" (identiques à ceux choisis par l'ordinateur) joués, on pourrait ainsi trouver le "meilleur" joueur. Cette idée, pour remarquable qu'elle soit, prêtait cependant le flanc à plusieurs critiques: sur le plan pratique, le travail fait par Guid et Bratko souffrait de la "faible" qualité du programme utilisé pour évaluer les coups à l'époque, et aussi du peu de parties évaluées, essentiellement par manque de puissance de calcul. Mais il existait un problème plus fondamental. Quel est le meilleur joueur: celui qui joue presque à chaque fois le meilleur coup, mais fait de temps en temps d'énormes erreurs, ou celui qui joue seulement "presque" le meilleur coup à chaque fois, mais ne commet jamais de graves erreurs?

En 2012, Diogo Ferreira (ICGA journal, Determining the strength of chess players based on actual play, 35-1, 2012) a brillamment raffiné l'idée. Il a continué à comparer les coups joués par les joueurs humains avec ceux que jouerait un ordinateur, a calculé la différence entre les deux, et a considéré cette différence comme une loi de distribution propre à chaque joueur. En calculant la loi de convolution des deux lois de deux joueurs différents (considérées comme des lois indépendantes), il peut corréler cette nouvelle loi avec les résultats d'une partie. Malheureusement, là aussi, le travail souffre de problèmes de puissance de calcul dans sa mise en oeuvre pour être statistiquement significative, et présente d'autre part une petite imprécision méthodologique. Enfin, il existe un autre problème plus fondamental, qui est le problème du contexte. Une erreur n'a pas la même "valeur" en fonction du contexte dans laquelle elle est commise. Ainsi, faire une petite erreur, voire une erreur un peu importante, dans une position qui est déjà largement gagnante (ou perdante) n'aura que peu d'influence sur le résultat de la partie, alors qu'elle sera peut-être décisive si la partie est encore équilibrée, et le système de Ferreira ne permet pas de distinguer les deux cas.

L'article publié dans la revue de l'ICGA (ICGA Journal, 39-1, 2017) que l'on trouvera ci-dessous fait le bilan des méthodes utilisées jusqu'ici et en explique les avantages et les faiblesses, puis les raffine et les évalue sur un corpus très important de parties: 26000 parties, correspondant à toutes les parties jouées par l'ensemble des champions du monde de Steinitz à Carlsen, évaluées à un temps de tournoi par le meilleur programme actuel (Stockfish, dont le classement ELO est probablement supérieur d'environ 300 points au meilleur joueur humain actuel), soit 62000 heures de CPU sur le cluster OSIRIM de l'Institut de Recherche en Informatique de Toulouse.
Il montre surtout qu'il est possible de proposer une autre interprétation, en considérant le jeu d'échecs comme un processus Markovien (et en utilisant toujours un ordinateur pour évaluer la qualité des coups). Cette interprétation résout tous les problèmes mentionnés ci-dessus, et, en utilisant un peu d'algèbre linéaire, permet donc en théorie de réaliser un classement plus fiable des joueurs d'échecs à travers les siècles.
L'autre intérêt de cet article est l'analyse statistique du jeu d'échecs qu'elle permet. Il montre par exemple que les joueurs jouent statistiquement moins bien avec les noirs qu'avec les blancs, pour des raisons probablement psychologiques.

La question que l'on me pose régulièrement arrivé à ce stade est "Alors, quel était le meilleur ?". L'article montre que la réponse n'est peut-être pas tout à fait aussi simple que la question. Les méthodes basées sur des interprétations de distributions, ou des interprétations markoviennes, ne permettent pas de réaliser un classement des joueurs, elles permettent seulement de les comparer deux à deux. J'encourage donc fortement à lire l'article dans sa totalité. Ceci dit, pour fournir une réponse simple (et forcément incomplète) on trouve ci-dessous le tableau extrait de l'article donnant les résultats des confrontations en face à face des 20 champions du monde considérés dans l'étude, en utilisant l'année pendant laquelle ils ont eu leur meilleur niveau de jeu (Carlsen: 2013, Kramnik: 1999, Fischer: 1971, Kasparov: 2001, Anand: 2008, Khalifman: 2010, Smyslov: 1983, Petrosian: 1962, Karpov: 1988, Kasimdzhanov: 2011, Botvinnik: 1945, Ponomariov: 2011, Lasker: 1907, Spassky: 1970, Topalov: 2008, Capablanca: 1928, Euwe: 1941, Tal: 1981, Alekhine: 1922, Steinitz: 1894). Chaque case du tableau correspond au pourcentage de points marqués dans une confrontation hypothétique des deux joueurs, et la colonne de gauche peut être considérée (avec des bémols) comme le classement de ces 20 champions. Le tableau n'est pas symmétrique, car les résultats ne sont pas les mêmes suivant que l'on joue en premier ou en second.


CaKrFiKaAnKhSmPeKpKsBoPoLaSpToCaTaEuAlSt
Carlsen 52545457585758566061596061616466697082
Kramnik49 525255565657555960586060606365687083
Fischer4749 5153575657565960606161626468707385
Kasparov474950 53545454535758565658586062666882
Anand44464848 545253535756575759596264697186
Khalifman4345444747 5051525354555556566062646779
Smyslov434545474951 50515355545454555963646882
Petrosian43444547495051 525354545555565963636780
Karpov4446454848495049 5152525252525658606376
Kasimdzhanov414342454548484850 52525254535660626580
Botvinnik40414144454846484949 505452525660606480
Ponomariov4243414544474747494951 5152525558596277
Lasker414140454446474649494850 51505458596378
Spassky40414043424547464847494950 515358576175
Topalov4041394442454645494849495051 5457576175
Capablanca373837413942424245454547474847 53545976
Tal35363439373939384341414343434448 495472
Euwe3233323632373738413941424344444752 5675
Alekhine313129343035333538363739384040434745 69
Steinitz20191720162219222522222524272726302733 
Table 9: Head to head match result predictions between different World Champions in their best year

Il faut noter que la méthode peut être appliquée à n'importe quel jeu à deux joueurs pour lesquels on dispose d'un "oracle", c'est à dire, en pratique d'un programme suffisamment fort pour être capable de fournir des coups "quasi-parfaits". On pourrait donc établir de la même façon une évaluation des joueurs de reversi, de checkers, de dames, de backgammon et probablement même bientôt de Go.

Le draft de l'article complet est disponible en pdf ici et une version html peut être consulté en ligne . Il est également disponible en format epub, mobi, et azw3 pour le consulter sur des liseuses. La version pdf est quasiment identique à la version finale publiée dans le journal de l'ICGA, à l'exception de la mise en page et de quelques corrections mineures. Les autres versions peuvent être moins lisibles en ce qui concerne les formules mathématiques en raison de la conversion de format, mais elles sont également globalement identiques à la version originale.
Je tiens à remercier à nouveau Jaap Van Den Herik, qui fut l'éditeur principal de cet article est qui est aujourd'hui éditeur honoraire du journal. Il a en particulier accepté de publier l'article dans son intégralité, sans coupure et sans le réduire malgré sa longueur, même si cela le plaçait en dehors des standards habituels. Je tiens aussi à remercier tout spécialement l'ensemble des référents de l'article, qui ont contribué à l'améliorer considérablement, avec des évolutions qui ont pris plus d'une année entre la version originale et la version finale. Ils ont préféré rester anonymes, mais cet article leur doit beaucoup. La version originale de l'article peut être consulté et commandé sur le site IOS Press.

Cet article a donné lieu à un communique de presse et un article dans le journal du CNRS, et a également reçu une couverture dans des media grands publics comme l'Express, 20 minutes, la Dépêche, le Figaro. Il a aussi été présenté (en anglais) sur le site de chessbase.

Comme tout article scientifique, il doit être lu, relu, critiqué, commenté et corrigé. Il contient certainement encore des imprécisions ou des erreurs. La base de données de parties (en PGN) évaluées par Stockfish sur le cluster de l'IRIT peut être téléchargée ici ce qui permet à qui le souhaite de refaire l'ensemble des calculs faits dans l'article et d'en vérifier les résultats.

La référence exacte de l'article est:

@Article{,
  author = 	 {Jean-Marc Alliot},
  title = 	 {Who is the master?},
  journal = 	 {ICGA Journal},
  year = 	 {2017},
  volume =	 {39},
  number =	 {1},
  OPTpages =	 {},
  OPTmonth = 	 {},
  note = 	 {DOI 10.3233/ICG-160012}
}

Photo: Bundesarchiv, Bild 183-76052-0335 / Kohls, Ulrich / CC-BY-SA 3.0, CC BY-SA 3.0 de, https://commons.wikimedia.org/w/index.php?curid=5665206


Retour à ma page principale

Le téléchargement ou la reproduction des documents et photographies présents sur ce site sont autorisés à condition que leur origine soit explicitement mentionnée et que leur utilisation se limite à des fins non commerciales, notamment de recherche, d'éducation et d'enseignement.
Tous droits réservés.

Dernière modification: 02:31, 19/05/2017 xhtml validation