Un scientifique français, Jean-Marc Alliot de l'Institut de recherche en informatique de Toulouse,
a inventé une nouvelle méthode pour mieux classer les joueurs d'échec et déterminer qui est le meilleur joueur de tous les temps.
Qui est le plus fort? Aux échecs, au jeu de go, aux dames et même dans les autres sports (tennis) , la réponse est apportée par un "
classement", plus ou moins fiable, toujours complexe, et qui n'est pa évident à comprendre. Pour les échecs c'est le fameux classemenrt ELO.
C'est une méthode
inventée par Arpad Elo dans les années 1950 qui permet de classer les joueurs en f
onction de leurs résultats.
Une victoire rapporte des points, d'autant plus si vous battez un joueur avec plus de points que vous -et donc potentiellement plus fort- et inversement.
Efficace et facile à mettre en place, ce classement a, bien sûr des défauts !
- Qui est vraiment le meilleur? Fisher, Kasparov ou Magnus..
Répertorions les problèmes
- Le classement Elo est déduit à partir des résultats des parties, et non en fonction de la qualité des coups, indique Jean-Marc Alliot, chercheur CNRS de l'Institut de recherche en informatique de Toulouse (lire ses articles ci-dessous) . Conséquence: il est tout à fait possible de gagner des points et des places dans le classement Elo même si l'on a mal joué, tant que l'adversaire a encore plus mal joué.
- Le deuxième problème est d'ordre temporel. Comme les points sont comptés en fonction des affrontements réels, le système Elo est uniquement valable pour des joueurs de la même époque.Mais comment savoir si le classement de 1970 est comparable avec celui de 2016, alors que les joueurs -et les techniques- se sont améliorés au fil du temps?
Comment, alors, déterminer si le "meilleur joueur de tous les temps" est Robert Fischer, Gary Kasparov ou Magnus Carlsen? "C'est ce problème qui explique le nombre d'articles, ou mêmes de livres" qui tentent de répondre à cette question, indique encore le chercheur français.
- Désormais on peut "Calculer le meilleur coup possible"
Jean-Marc Alliot a inventé une nouvelle méthode, qu'il détaille dans une étude publiée dans International Computer Games Association :
"Le classement "Elo est basé sur les résultats des matchs. Ma méthode évalue directement la qualité intrinsèque des coups. Une idée pas strictement nouvelle mais qui raffine considérablement le classement final."
Comment déterminer le meilleur coup possible?
En calculant
l'écart entre les coups joués par les champions du monde et ceux qu'aurait choisis le meilleur programme actuel, Stockfish. Ce logiciel, qui joue systématiquement des coups quasi parfaits, est de très loin meilleur que les plus grands champions humains.
- La méthode de Jean-Marc Alliot : analyser les coups de 26 000 parties
Jean-Marc Alliot a compilé tous les coups des 26 000 parties disputées par tous les champions du monde depuis 1860. Il les a ensuite comparés avec ce qu'aurait joué Stockfish, grâce au supercalculateur OSIRIM du CNRS.
Puis, grâce à un modèle mathématique qu'il détaille dans son étude, il a calculé les probabilités d'erreur et l'importance des erreurs lors de chaque rencontre, et donc les probabilités de victoire lors d'un match entre deux joueurs.
-non seulement ses prédictions sont très proches des résultats observés lorsque les compétiteurs se sont effectivement affrontés, mais elles dépassent celles qui sont basées sur le score Elo.
-Son classement final place l'actuel champion du monde Magnus Carlsen en tête, confirmant que les joueurs jouent de mieux en mieux au fil du temps.
Bobby Fischer, traditionnellement considéré comme le meilleur joueur de tous les temps, est troisième. Quant à Garry Kasparov, le plus connu du grand public, il est quatrième.
Avec sa méthode, Jean-Marc Alliot a calculé le classement des meilleurs joueurs d'échecs de tous les temps. Ici, le pronostic des matchs entre les différents champions du monde dans leur meilleure année (en pourcentage).
Ce système il s'imposera-t-il un jour comme le nouveau classement d'échecs?
"Ma méthode permet de remplacer tout classement à partir du moment où l'on dispose d'un 'oracle', c'est-à-dire un programme capable de savoir quel est le coup parfait, et donc d'évaluer de façon fiable la qualité des coups joués par un humain, répond Jean-Marc Alliot.
- Conclusion : Et demain?
- Le système Elo, même imparfait, reste très facile à établir et mettre en place et ne demande pas de capacités de calculs importantes, contrairement à la nouvelle méthode. Il a encore de beaux jours devant lui, mais...
- L'accroissement des puissances de calcul permettra, dans un avenir proche, d'étendre ce nouveau système de calcul à davantage de joueurs.
- De plus, il pourrait s'appliquer facilement à d'autres jeux (dames, othello, go..) mais aussi aux jeux vidéos.
=> Cet article n'est qu'une simple compilation de publications originales.
=> Les deux articles ci-dessous sont publiés à l'identique des sources toujours indiquées.
----------------------------------------------------------------------------------
Un chercheur de Toulouse propose une nouvelle approche, plus juste que la méthode Elo, pour classer les plus grands maîtres d'échecs.
Sur le ring, sur un terrain ou autour d’un plateau de jeu, un match permet de déterminer qui est le meilleur à un instant donné. Mais comment intégrer ces résultats isolés dans un classement global ? Les fédérations sportives utilisent une foule de systèmes différents. L’univers très rationnel et mathématisé des échecs a majoritairement adopté, dans les années 1970, la méthode du Hongrois Arpad Elo (1903-1992). Les points s’y accumulent sans limites selon les résultats et augmentent avec le niveau des compétiteurs. L’actuel champion du monde Magnus Carlsen est ainsi monté jusqu’à 2 882 points en mai 2014, le plus haut score jamais atteint.
Est-il pour autant forcément le meilleur joueur de l’histoire ?
Les limites du classement Elo
La méthode Elo marche très bien,
mais ne prend pas en compte la qualité des coups.
Certains remettent en effet en cause ce système et proposent de nouveaux types de classement. Dans des travaux publiés dans la revue de l’International Computer Games Association, Jean-Marc Alliot, de l’IRIT
1, s’applique ainsi à trouver une manière de trier les joueurs en fonction de leur talent plutôt que par leur seul bilan en compétition. On pourrait penser que le palmarès reflète fidèlement les capacités de chacun, mais un match ne se résume pas à une victoire.
« La méthode Elo est basée sur l’idée que les points évoluent en fonction du résultat d’une partie et du classement de l’adversaire, explique le directeur de recherche. Elle marche très bien, mais ne prend pas en compte la qualité des coups. On peut parfaitement gagner en jouant mal, à condition que votre challenger joue encore plus mal. »
La différence de classement Elo entre deux compétiteurs permet, grâce à
des tables préétablies(link is external), d’estimer les chances de victoire de chacun. Un joueur qui a 100 points de plus qu’un autre a ainsi 64 % de chances de le battre, 95 % s’il en a 500. Si quelqu’un fait mieux que prévu, il remporte des points. S’il fait moins bien, il en perd.
Les anciens classements qui cohabitaient avant la méthode Elo partaient d’ailleurs du même principe, y compris le système Ingo dans lequel les meilleurs joueurs avaient le plus petit score. La qualité du jeu n’est à aucun moment évaluée. Les chiffres sont également soumis à une forme d’inflation et de dérive, qui empêchent de s’en servir pour comparer des compétiteurs d’époques différentes.
Le problème est encore plus flagrant dans d’autres sports. Le fameux classement ATP du tennis accorde ainsi des points en fonction des résultats en tournois sur les 52 dernières semaines. Qu’un joueur ratatine le numéro 1 mondial ou qu’une série de forfaits le débarrasse de la concurrence, remporter un tournoi du grand chelem lui rapporte quoiqu’il arrive 2 000 points.
Prendre en compte les mouvements plutôt que les matchs
Le système de Jean-Marc Alliot préfère donc classer les joueurs selon la qualité de l’ensemble de leurs coups. Il s’est pour cela appuyé sur un maître d’un genre particulier : Stockfish.
Libre et gratuit(link is external), le meilleur logiciel d’échecs du monde surpasse aujourd’hui largement les humains les plus talentueux. Ses choix peuvent donc être considérés comme « presque » parfaits, ce qui permet de juger la valeur des décisions d’un compétiteur à leur écart par rapport à celles de Stockfish.
Quand la victoire est déjà assurée,
beaucoup préfèrent jouer le coup le plus simple plutôt que le meilleur.
Des comparaisons statistiques entre les hommes et une intelligence artificielle ont déjà été tentées à plusieurs reprises dans le passé, mais elles manquaient de la force de calcul aujourd’hui disponible. L’intégralité des 26 000 matchs disputés par tous les champions du monde depuis le règne de Wilhelm Steinitz (1836-1900), fondateur des échecs modernes, a ici été extraite. Installé sur le supercalculateur toulousain OSIRIM
2, Stockfish a évalué en 62 000 heures de calcul ces plus de 2 millions de positions.
« Il faut alors déjouer un écueil, précise Jean-Marc Alliot. Quel est le meilleur entre celui qui joue en général mieux, mais commet parfois des erreurs importantes, et celui qui ne joue jamais exactement le meilleur coup, mais ne commet pas d’erreur sérieuse. Quand la victoire est déjà assurée, de nombreux compétiteurs préfèrent également jouer le coup le plus simple plutôt que le meilleur. »
Le programme jauge chaque position en termes de points, selon les pièces d’avance ou de retard sur l’adversaire. Le coup parfait ne dégrade pas cette position et l’on peut calculer à quel point les champions s’en écartent ou pas.
Un classement plus prédictif
Ces statistiques établissent la probabilité qu’a un joueur de commettre une erreur dans une situation donnée, ce qui permet de simuler des matchs entre tous les membres de l’échantillon. Comme beaucoup des compétiteurs retenus dans l’étude se sont réellement affrontés, ces estimations ont pu être confrontées aux résultats officiels. La méthode fonctionne non seulement très bien, mais elle dépasse même les prédictions basées sur le classement Elo.
Les travaux de Jean-Marc Alliot comparent des couples de joueurs, sans encore offrir d’ordre global. Les choses se compliquent en effet quand les experts se battent entre eux, sans moyen de les intercaler précisément dans un ensemble cohérent. Le sommet est par contre clair : donné gagnant contre les dix-neuf autres champions, Magnus Carlsen peut être légitimement considéré comme le meilleur de tous les temps. Un résultat qui conforte l’idée que le niveau a bien augmenté, même si Bobby Fisher (1943-2008) est troisième et devance des joueurs contemporains comme Viswanathan Anand.
« Le système Elo est perfectible, mais il est stable depuis longtemps, simple à mettre en œuvre et fonctionnel, avoue Jean-Marc Alliot. Il faudrait présenter des avantages importants aux fédérations pour qu’elles changent de paradigme et modifient leurs classements. Un système comme le mien nécessite encore de nombreuses vérifications et certainement des améliorations. L’augmentation des puissances de calcul devrait cependant permettre de le généraliser à tous les joueurs et de concurrencer le système Elo. »
SOURCE
Cet article est une copie exacte de l'article original
-----------------------------------------------------------------------------
Article du Site de JM ALLIOT
Who is the master?
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. 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.
| 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 | |
| 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 est disponible là. Ces deux versions sont quasiment identiques à la version finale publiée dans le journal de l'ICGA, à l'exception de la mise en page et de quelques corrections mineures. 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, comme tout article scientifique, 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.
SOURCE DE CET ARTICLE ici strictement copié à l'identique
http://www.alliot.fr/CHESS/ficga.html.fr
COMPLEMENTS
http://www2.cnrs.fr/presse/communique/5007.htm
http://www.lexpress.fr/actualite/sciences/classement-elo-un-nouveau-systeme-pour-mieux-classer-les-joueurs-d-echecs_1902095.html
