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.
Ca Kr Fi Ka An Kh Sm Pe Kp Ks Bo Po La Sp To Ca Ta Eu Al St Carlsen 52 54 54 57 58 57 58 56 60 61 59 60 61 61 64 66 69 70 82 Kramnik 49 52 52 55 56 56 57 55 59 60 58 60 60 60 63 65 68 70 83 Fischer 47 49 51 53 57 56 57 56 59 60 60 61 61 62 64 68 70 73 85 Kasparov 47 49 50 53 54 54 54 53 57 58 56 56 58 58 60 62 66 68 82 Anand 44 46 48 48 54 52 53 53 57 56 57 57 59 59 62 64 69 71 86 Khalifman 43 45 44 47 47 50 51 52 53 54 55 55 56 56 60 62 64 67 79 Smyslov 43 45 45 47 49 51 50 51 53 55 54 54 54 55 59 63 64 68 82 Petrosian 43 44 45 47 49 50 51 52 53 54 54 55 55 56 59 63 63 67 80 Karpov 44 46 45 48 48 49 50 49 51 52 52 52 52 52 56 58 60 63 76 Kasimdzhanov 41 43 42 45 45 48 48 48 50 52 52 52 54 53 56 60 62 65 80 Botvinnik 40 41 41 44 45 48 46 48 49 49 50 54 52 52 56 60 60 64 80 Ponomariov 42 43 41 45 44 47 47 47 49 49 51 51 52 52 55 58 59 62 77 Lasker 41 41 40 45 44 46 47 46 49 49 48 50 51 50 54 58 59 63 78 Spassky 40 41 40 43 42 45 47 46 48 47 49 49 50 51 53 58 57 61 75 Topalov 40 41 39 44 42 45 46 45 49 48 49 49 50 51 54 57 57 61 75 Capablanca 37 38 37 41 39 42 42 42 45 45 45 47 47 48 47 53 54 59 76 Tal 35 36 34 39 37 39 39 38 43 41 41 43 43 43 44 48 49 54 72 Euwe 32 33 32 36 32 37 37 38 41 39 41 42 43 44 44 47 52 56 75 Alekhine 31 31 29 34 30 35 33 35 38 36 37 39 38 40 40 43 47 45 69 Steinitz 20 19 17 20 16 22 19 22 25 22 22 25 24 27 27 26 30 27 33
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
là.
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 finale.
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 finale de l'article peut être consultée et
commandée
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
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: 15:39, 21/02/2024