Le meilleur joueur d'échecs de tous les temps selon l'ordinateur

Qui est le meilleur joueur d'échecs de tous les temps?

Les talents des champions du monde examiné par un ordinateur

par Matej Guid et Ivan Bratko
Université de Ljubljana, Faculté d'informatique et de sciences de l'information, Laboratoire d'intelligence artificielle, Ljubljana, Slovénie. Ce papier est basé sur un article des mêmes auteurs publié dans le ICGA Journal; la référence complète est donnée ci-dessous.

Qui est le meilleur joueur d'échecs de tous les temps? Les joueurs d'échecs sont souvent intéressés par cette question à laquelle il n'y a pas de réponse objective et bien fondée, car elle nécessite une comparaison entre des joueurs d'échecs de différentes époques qui ne se sont jamais rencontrés sur l'échiquier. Avec l'émergence de programmes d'échecs de haute qualité, la possibilité d'une telle comparaison objective apparaît. Cependant, jusqu'à présent les ordinateurs ont été principalement utilisés comme un outil d'analyse statistique des résultats des joueurs.

Notre approche est différente: nous nous sommes intéressés à la qualité de jeu des joueurs d'échecs indépendamment du score de la partie, que nous avons évaluée à l'aide d'analyses informatiques des coups individuels effectués par chaque joueur. Une méthode pour évaluer la difficulté des positions a été conçue, afin de prendre en compte les différences de styles des joueurs et de compenser le fait que les joueurs positionnels calmes dans leurs parties typiques ont moins de chance de commettre des erreurs tactiques grossières que les joueurs tactiques agressifs. Nous donnons également une méthodologie soigneusement choisie pour utiliser les programmes d'échecs informatiques pour évaluer la force réelle des joueurs d'échecs.

Les quatorze champions du monde de la version classique, depuis le premier championnat du monde d'échecs en 1886 jusqu'à aujourd'hui, ont été évalués. Les matchs pour le titre de "Champion du monde d'échecs", dans lesquels les joueurs se disputaient le titre ou le défendaient, ont été sélectionnés pour être analysés. Plusieurs critères différents ont été conçus. La base de l'évaluation était la différence entre les valeurs des positions résultant des coups joués par l'humain et les coups choisis comme meilleurs par le programme d'échecs. Nous avons également calculé le nombre moyen de gaffes et observé comment les joueurs se comporteraient s'ils devaient tous faire face à des positions aussi complexes. Nos analyses, entre autres choses, montrent clairement que le pourcentage des meilleurs coups joués dépend de la position analysée elle-même et qu'il y a une très forte corrélation avec la différence entre les évaluations des deux meilleurs coups (selon l'ordinateur): plus elle est grande, plus il est facile de trouver le meilleur coup. En observant la quantité moyenne de matériel pendant les parties, nous avons essayé de déterminer l'inclination des joueurs à simplifier les positions. 

 

Globalement, notre analyse informatique semble avoir produit des résultats raisonnables qui peuvent être interprétés de manière satisfaisante par un expert en échecs. Cependant, beaucoup trouveront certains des résultats assez surprenants. Le gagnant selon le critère principal, où nous avons mesuré les écarts moyens entre les évaluations des coups joués et les meilleurs coups évalués par l'ordinateur, est José Raùl Capablanca, le 3e champion du monde.

Comme nous l'avons fait dans l'étude, ce résultat doit être interprété à la lumière de la complexité relativement faible des positions dans les parties de Capablanca. Quoi qu'il en soit, il était également en tête selon d'autres critères où nous avons mesuré la qualité du jeu et n'a été battu par Vladimir Kramnik que selon un seul critère (bien qu'il soit très important), à savoir la qualité du jeu à condition que tous les joueurs traitent des positions aussi complexes. Capablanca et Kramnik se sont tous deux nettement démarqués des autres joueurs..

En parallèle, nous avons effectué une analyse du match du championnat du monde entre Kramnik et Topalov. Les résultats (perte moyenne par coup: Kramnik 0.1220, Topalov 0.1328; seules les parties avec contrôle classique du temps ont été prises en compte) indiquent que le jeu de Kramnik était légèrement meilleur, tandis que la qualité générale du jeu dans le match était à un niveau tout à fait décent (en comparaison avec d'autres matchs de championnat du monde), bien que le record (0.0903 de Kramnik dans le match de Londres 2000 contre Kasparov) n'était vraiment pas en danger. Notez que plus cette mesure est faible, meilleure est la performance. 

Le programme d'échecs Crafty a été utilisé pour effectuer les analyses. Nous avions besoin d'un programme open source afin de le modifier légèrement, comme cela est décrit dans l'article. On pourrait argumenter que Crafty est plus faible qu'au moins certains des quatorze champions du monde qui ont été pris en considération. Cependant, au total, plus de 37'000 positions ont été évaluées et même si les évaluations ne sont pas toujours parfaites, pour notre analyse, il suffit qu'elles soient suffisamment précises en moyenne puisque les petites erreurs occasionnelles s'annulent par le calcul de la moyenne statistique. Quoi qu'il en soit, nous voudrions encourager d'autres chercheurs qui pourraient avoir accès au code source des programmes d'échecs commerciaux les plus puissants, à les modifier et à les exécuter de la manière que nous avons proposée, afin d'obtenir également une comparaison entre différents moteurs.

Le critère de base pour évaluer les champions du monde était la différence moyenne entre les coups joués et les meilleurs coups évalués par l'analyse informatique. Selon cette analyse, le vainqueur était le troisième champion du monde, José Raùl Capablanca. Ce résultat doit être interprété à la lumière de la complexité relativement faible des positions dans les parties de Capablanca, ce qui est tout à fait en accord avec les évaluations connues de son style dans la littérature échiquéenne. Par exemple, Garry Kasparov, dans son ensemble de livres My Great Predecessors, lorsqu'il commente les parties du champion cubain, spécule qu'occasionnellement il ne se donnait même pas la peine de calculer des variations tactiques profondes. Le Cubain préférait simplement jouer des coups qui étaient clairs et si bien justifiés sur le plan positionnel que le calcul des variantes n'était tout simplement pas nécessaire. Il décrit également Capablanca avec les mots suivants: "Il s'est arrangé pour gagner les tournois et les matchs les plus importants, restant invaincu pendant des années (de tous les champions, il est celui qui a perdu le moins de parties), et son style, l'un des plus purs, le plus limpide de toute l'histoire des échecs, étonne par sa logique."

Les résultats de la mesure du taux de gaffes sont similaires. Nous nous attendions à ce que les joueurs positionnels obtiennent de meilleurs résultats selon ce critère que les joueurs tactiques, puisque dans les positions calmes, il y a moins d'occasions de gaffer. Notez l'excellent résultat de Tigran Petrosian qui est largement reconnu comme un pur joueur positionnel. Conformément à cette observation, Steinitz, qui a vécu dans une ère romantique d'échecs tactiques, a clairement pris la dernière place.

Capablanca est réputé pour jouer un jeu "simple" et éviter les complications, alors qu'il est courant que Steinitz et Tal soient confrontés à de nombreuses positions "sauvages" dans leurs parties. Les résultats de la mesure de la complexité coïncident clairement avec cette opinion commune.

La méthode d'évaluation de la complexité des positions est décrite en détail dans l'article original (voir également la référence ci-dessous). Le graphique des erreurs commises par les joueurs à différents niveaux de complexité indique clairement la validité de la mesure choisie de la complexité des positions; les joueurs commettent peu d'erreurs dans les positions simples, et le taux d'erreur augmente avec la complexité.

Nous avons utilisé la mesure de la complexité des positions mentionnée ci-dessus pour déterminer la distribution des coups joués dans différents intervalles de complexité, sur la base des positions auxquelles les joueurs ont été eux-mêmes confrontés. Ceci, à son tour, définit largement leur style de jeu. Par exemple, Capablanca était beaucoup moins confronté à des situations complexes que Tal, qui doit être considéré comme un joueur tactique.

La principale lacune de ces deux critères, telle que détaillée dans les sous-sections précédentes, réside dans le fait qu'il existe plusieurs types de joueurs avec leurs caractéristiques spécifiques propres, auxquels les critères ne s'appliquent pas directement. On peut raisonnablement s'attendre à ce que les joueurs positionnels commettent en moyenne moins d'erreurs que les joueurs tactiques, en raison des positions un peu moins complexes dans lesquelles ils se trouvent du fait de leur style de jeu. Ces derniers, en moyenne, sont confrontés à des positions plus complexes, mais ils sont aussi plus aptes à les gérer et utilisent cet avantage pour obtenir d'excellents résultats en compétition. Nous avons voulu déterminer comment les joueurs se comporteraient face à des positions tout aussi complexes. Le vainqueur a été le quatorzième champion du monde Vladimir Kramnik. Kramnik a également obtenu la meilleure performance de tous les matches; son erreur moyenne dans son match contre Kasparov (Londres, 2000) n'était que de 0,0903. Nous avons également essayé de déterminer comment les joueurs se comporteraient s'ils jouaient tous dans le style de Capablanca, Tal, etc. Il est intéressant de noter que Kasparov surclasserait Karpov, à condition qu'ils jouent tous deux dans le style de Tal.

Le pourcentage de meilleurs coups joués seul ne décrit pas réellement la qualité d'un joueur autant qu'on pourrait le croire. Dans certains types de positions, il est beaucoup plus facile de trouver un bon coup que dans d'autres. Des expériences ont montré que le pourcentage des meilleurs coups joués est fortement corrélé à la différence d'évaluation du meilleur et du deuxième meilleur coup dans une position donnée. Plus la différence est grande, plus le pourcentage de réussite du joueur à jouer le meilleur coup est élevé.

Sur la base de cette observation, un autre critère a été le nombre attendu de meilleurs coups joués, à condition que tous les joueurs traitent des positions avec une différence égale entre les deux meilleurs coups, comme décrit dans la section précédente. Cela représente une autre tentative de ramener les champions à un dénominateur commun. Voir les résultats juste en dessous.

Kramnik, Fischer et Alekhine avaient le plus haut pourcentage de meilleurs coups joués, mais la différence mentionnée ci-dessus était également élevée. En revanche, Capablanca, qui était juste après en ce qui concerne le pourcentage du meilleur coup joué, a mieux traité en moyenne la plus petite différence entre les deux meilleurs coups. Le gagnant selon ce critère est une fois de plus Capablanca. Lui et Kramnik ont à nouveau nettement dépassé les autres.

Le calcul de la quantité moyenne de matériel, c'est-à-dire la somme des valeurs exprimées numériquement de toutes les pièces sur l'échiquier, n'avait pas pour but de déterminer la qualité du jeu, mais de recueillir des informations supplémentaires sur le style de jeu d'un joueur. Nous avons principalement essayé d'observer l'inclinaison d'un joueur à simplifier les positions.

Parmi les joueurs qui se distinguent des autres, Kramnik a manifestement eu affaire à moins de matériel sur l'échiquier (rappelez-vous ses échanges de ♕♛ précoces dans ses parties du Mur de Berlin contre Kasparov). Le contraire pourrait être dit pour Steinitz, Spassky et Petrosian.

Les auteurs Matej Guid a obtenu son doctorat en informatique à l'Université de Ljubljana, en Slovénie. Ses recherches portent sur les jeux vidéo, les systèmes d'explication et de tutorat automatisés, la recherche heuristique et l'apprentissage automatique basé sur les arguments. Certains de ses travaux scientifiques, dont la thèse de doctorat intitulée Search and Knowledge for Human and Machine Problem Solving, sont disponibles sur la page Recherche de Matej. Les échecs sont l'un des passe-temps favoris de Matej depuis son enfance. Il a été champion junior de Slovénie à plusieurs reprises et détient le titre de maître FIDE.

Ivan Bratko est professeur d'informatique à l'université de Ljubljana, en Slovénie. Il dirige le laboratoire d'intelligence artificielle de la faculté d'informatique et de sciences de l'information de l'université de Ljubljana. Il a mené des recherches sur l'apprentissage automatique, les systèmes à base de connaissances, la modélisation qualitative, la robotique intelligente, la programmation heuristique et les échecs informatiques (connaissez-vous le célèbre test Bratko-Kopec?). Le professeur Bratko a publié plus de 200 articles scientifiques et un certain nombre de livres, dont le best-seller Prolog Programming for Artificial Intelligence. Les échecs sont l'un de ses passe-temps favoris.

L'article original a été publié dans l'ICGA Journal, Vol 29, No. 2, Juin 2006, pages 65-73. Il a également été présenté à la 5e conférence internationale sur les ordinateurs et les jeux, qui se tint du 29 au 31 mai 2006 à Turin, en Italie, et a été publié dans le livre des actes.

Liens

• Un programme informatique pour identifier la beauté dans les problèmes et les études

  Un problème d'échecs détient-il la clé de la conscience humaine?
• Histoire de la computation échiquéenne – Connaissance vs force brute
• Il y a 25 ans: Deep Blue battait Kasparov
• L'aventure de la programmation dans les échecs (1e partie): Comment des adversaires mignons sont devenus des machines imbattables
• L'aventure de la programmation dans les échecs (2e partie): Vaincre par la force brute
• L'aventure de la programmation dans les échecs (3e partie): Aux origines de Fat Fritz
• Échecs et Intelligence Artificielle: qu’en pense Frederic Friedel, le gourou de ChessBase? (1e partie)
• Échecs et Intelligence Artificielle: qu’en pense Frederic Friedel, le gourou de ChessBase? (2e partie)
• Échecs sur ordinateur: La plus longue expérience en informatique
• Fat Fritz 2.0 - Le nouveau n°1
• La stimulation électrique transcrânienne peut-elle doper le joueur d'échecs?