L'histoire des moteurs d'échecs et ses programmes informatiques
Tout au long de l'histoire, les échecs ont été révolutionnés plusieurs fois.
A la fin du 19ème siècle, le premier champion du monde Wilhelm Steinitz provoqua ses adversaires à l'attaquer vigoureusement et jeta les bases des échecs positionnels.
Au milieu du 20ème siècle, le sixième champion du monde Mikhail Botvinnik a commencé à consacrer énormément de temps à la préparation physique et aux échecs avant les tournois et les matchs, annonçant l'ère du professionnalisme strict aux échecs.
Dans les années 1970, sous l'influence du onzième champion du monde Robert James Fischer, la théorie de l'ouverture a connu des changements considérables. De nouveaux systèmes d'ouverture tels que le hérisson (Hedgehog ) ont été introduits et de nouvelles idées ont été découvertes dans les anciens systèmes d'ouverture, démontrant la nature inépuisable des échecs.
Rien d'autre, cependant, n'a autant révolutionné les échecs que l'apparition des moteurs d'échecs informatiques. De nos jours, même les plus grands débutants sont familiers avec les termes "Stockfish" et "Rybka" (surtout quand ils crient leurs noms dans les chats en ligne tout en imitant les jeux des meilleurs joueurs d'échec). Même un ordinateur d'échecs sur votre téléphone portable est plus fort qu'un grand maître de nos jours. Il n'est pas surprenant que les joueurs aient commencé à s'en servir comme outil et à en tirer des leçons.
Même si nous considérons tous les moteurs d'échecs informatiques comme quelque chose de normal et les utilisons quotidiennement, la plupart d'entre nous ne sont pas familiers avec les défis et les problèmes auxquels les générations précédentes ont dû faire face afin d'en créer un. Qui a conçu le premier moteur d'échecs par ordinateur ? Combien de temps a-t-il fallu aux ordinateurs pour devenir plus forts que les humains ? Quelle est la différence entre les moteurs d'échecs informatiques classiques et l'AlphaZero de Google ?
Dans cet article, nous allons répondre à ces questions et examiner de plus près l'histoire des moteurs d'échecs informatiques.
Sommaire
- 1. Le 18ème siècle : le turc
- 2. Les années 1950 : le début d'une époque
- 3. Les années 1960 et 1970 : un petit pas ou un pas de géant ?
- 4. Les années 1980 : un challenge pour l'humanité
- 5. 1990 - 1997 : les moteurs prennent le relais
- 6. 1997-2006 : le dernier combat de l'humanité
- 7. 2006-2017 : l'âge d'or des moteurs d'échecs informatiques
- 8. 2017 et au-delà : une nouvelle révolution ?
1. Le 18ème siècle : le turc
En 1769, l'illusionniste français François Pelletier jouait un numéro devant Marie-Thérèse d'Autriche, au château de Schönbrunn à Vienne. Parmi les spectateurs se trouvait l'inventeur et auteur hongrois Wolfgang von Kempelen. Inspirée par la performance de Pelletier, Kempelen a immédiatement commencé à construire l'invention qui allait devenir l'un des canulars les plus célèbres de l'histoire.
L'année suivante, en 1770, au même endroit, Kempelen exposa le Turc - le premier automate d'échecs de l'histoire. Sa construction complexe se composait de plusieurs compartiments avec divers mécanismes opérationnels. Il incorporait un modèle grandeur nature d'un humain, vêtu de vêtements orientaux traditionnels (d'où son nom).
Le Turc était capable de jouer aux échecs tout seul et de battre des adversaires humains. Elle a même été capable de reconnaître les mouvements illégaux et de forcer ses adversaires à les reprendre. Dans une exposition, il a même résolu le casse-tête difficile de la tournée des cavaliers tout autour du plateau.
Il y avait juste un problème. Tout était faux. Ce nétait pas le Turc qui faisait tous les mouvements. C'était un humain caché à l'intérieur (voir l'article de Smithsonian magazine
Voyez-vous, pendant la construction, Kempelen a imaginé plusieurs compartiments cachés, assez grands pour accueillir un adulte. Il a même fait des couloirs coulissants, à travers lesquels une personne pouvait se déplacer d'un compartiment à l'autre. Il était important de préserver l'illusion - avant chaque exposition, Kempelen invitait le public à examiner l'automate, pendant lequel l'opérateur de la machine restait caché.
Et ça a marché ? Kempelen a fait le tour de l'Europe en exposant son invention jusqu'en 1804. Après sa mort, la machine a changé plusieurs fois de propriétaires et a continué à jouer aux échecs jusqu'en 1854, quand un incendie à Philadelphie a scellé son destin. C'est étonnant que personne n'ait réalisé la fraude durant la vie du Turc.
Ainsi, le premier "moteur" d'échecs par ordinateur fut un succès commercial majeur.
Cependant, si l'on fait abstraction de plusieurs automates similaires, le développement des moteurs d'échecs a stagné au cours des 100 années suivantes. La véritable percée n'a eu lieu qu'à la fin des années 1940 et au début des années 1950. Et comme pour beaucoup d'autres avancées technologiques, un événement historique majeur a joué le rôle de catalyseur.
2. Les années 1950 : le début d'une époque
Pendant la Seconde Guerre mondiale, les dirigeants de l'Axe et des Alliés ont passé beaucoup de temps à recruter les meilleurs scientifiques et à les rassembler en équipes. Le but était clair : gagner la guerre. Les plus grands esprits du XXe siècle ont consacré leurs années de guerre à développer des technologies et des armes qui aideront à vaincre l'ennemi. La science était au service de l'industrie de guerre.
Malgré cela, la guerre a donné lieu à un nombre impressionnant de percées. Les scientifiques ont jeté les bases d'un certain nombre de nouveaux domaines. Dans le contexte de cet article, l'informatique présente un intérêt particulier. Deux noms célèbres ont joué un rôle crucial dans son développement : Claude Shannon et Alan Turing.
Shannon est largement reconnu comme le père de la théorie moderne de l'information, tandis que Turing est le père de l'ordinateur moderne (machine de Turing !). Leurs contributions dans le domaine de l'informatique sont bien connues. Ce qui est peut-être moins connu, c'est que Shannon et Turing sont aussi les pères des moteurs informatiques d'échecs.
Après avoir terminé leur doctorat à la veille de la guerre, Shannon et Turing ont commencé à travailler sur la cryptanalyse, respectivement aux États-Unis et au Royaume-Uni. Ils ont suivi de près le travail des uns et des autres et se sont même rencontrés en personne en 1943, pendant le séjour de deux mois de Turing au Bell's Lab à New York, où travaillait Shannon. Après la fin de la guerre, ils ont tous les deux manifesté un intérêt accru pour la programmation d'un ordinateur d'échecs.
(Source principale décrivant la relation entre Shannon et Turing : Life In Code And Digits - When Shannon Met Turing)
En 1949, Shannon a publié un article emblématique intitulé "Programming a Computer For Playing Chess", dans lequel il décrit un algorithme pour la machine à jouer aux échecs. Simultanément, Turing développait son propre programme de jeu d'échecs. Son travail sur "Turbochamp" a commencé en 1948 et s'est terminé en 1950.
Il est à noter de mentionner Turing Turbochamp programmé sur papier, sans accès à un véritable ordinateur. Il a essayé de le tester sur Ferranti Mark I - le premier ordinateur disponible sur le marché - et a échoué. Finalement, il l'a testé manuellement ( !) lors d'une partie amicale d'échecs en 1951.
(51 ans plus tard, nul autre que Garry Kasparov testait "Turbochamp". Le programme n'avait aucune chance, mais les plus grands joueurs de tous les temps ont reconnu à quel point la réussite de Turing était formidable).
Il n'est pas encore certain que Shannon et Turing aient travaillé indépendamment ou aient été inspirés l'un par l'autre - le contenu de leurs conversations en 1943 n'est pas connu. Cependant, même s'ils n'ont pas collaboré, leur contribution a été immense. Les générations suivantes de développeurs d'échecs par ordinateur ont tous " reposé sur les épaules " de ces deux géants.
En 1951, le collègue de Turing, Dietrich Prinz, réussit à implémenter l'algorithme sur Ferranti Mark I et créa un programme capable de résoudre le mat en deux. En 1956, une équipe de scientifiques dirigée par Stan Ulam (un des inventeurs de la bombe h) a créé un programme capable de jouer aux échecs sur un échiquier 6×6. Et finalement, en 1957, l'ingénieur d'IBM Alex Bernstein a créé le premier programme automatisé capable de jouer à un jeu d'échecs dans son intégralité.
L'ère des échecs par ordinateur était officiellement commencée...
3. Les années 1960 et 1970 : un petit pas ou un pas de géant ?
Les premiers moteurs d'échecs informatiques étaient plutôt faibles et primitifs. Au cours des années 1960 et 1970, cependant, leur force s'est rapidement accrue. Deux facteurs majeurs ont contribué à ce saut qualitatif :
* Algorithmes améliorés et plus sophistiqués
Dans les années 1960 et 1970, les algorithmes pour les moteurs d'échecs informatiques ont été considérablement améliorés. La fondation a été établie par le génie de John Von Neumann, qui a développé l'algorithme MiniMax, parfaitement adapté au jeu d'échecs (il minimise le score d'un joueur tout en maximisant celui d'un autre). Dans les décennies qui ont suivi, la recherche MiniMax a été améliorée grâce à des techniques heuristiques avancées et à "l'approfondissement itératif", ce qui a progressivement augmenté la profondeur de la recherche par MiniMax.
* Matériel amélioré et plus rapide
La plus grande restriction pour Turing et d'autres pionniers était la puissance de calcul. Dans les années 1960 et 1970, cependant, la vitesse du matériel a augmenté de façon exponentielle - selon la loi de Moore, la puissance de calcul a doublé tous les deux ans. Il a permis l'implémentation d'algorithmes avancés et le temps de recherche pour le MiniMax a été considérablement réduit.
Mais il ne s'agissait pas seulement de la puissance de calcul brute. Dans les années 1960 et 1970, les échecs par ordinateur ont pris de l'importance. Le premier championnat d'échecs entièrement informatisé a eu lieu en 1970 à New York. Peu après, en 1974, le premier championnat du monde d'échecs par ordinateur a eu lieu à Stockholm. L'apparition de la "scène" a inévitablement conduit à la fondation de sociétés spécialisées qui ont commencé à développer des logiciels et du matériel de jeu d'échecs personnalisés. Ce qui a permis aux moteurs d'échecs informatiques de s'améliorer encore.
A quel point " faire mieux " était bon ? A quel point les moteurs d'échecs informatiques étaient-ils bons par rapport aux humains à un moment donné ? L'expérience a montré qu'un programme était assez bon pour battre un amateur, mais pas assez bon pour rivaliser avec un maître d'échecs.
Par exemple, en 1967, MacHack VI est devenu le premier moteur d'échecs informatique à battre un adversaire humain. Sa force de jeu tourne autour de 1300 USCF. Mais déjà en 1976, un saut significatif s'est produit - le moteur d'échecs Chess 4.5 a gagné la section de classe B du tournoi Paul Mason en Californie du Nord. En 1977, il a également remporté l'Omnium du Minnesota avec une cote de performance de 2271 et battu un joueur de classe A, Stenberg, en 1969.
Cependant, les ordinateurs n'étaient pas sur un pied d'égalité avec les humains les plus forts. En 1968, le Maître International David Levy a parié 3000$ qu'il serait capable de battre n'importe quel moteur informatique d'échecs dans les 10 prochaines années. En 1977, il a gagné son pari dans un match contre le moteur informatique d'échecs KAISSA. Il a également battu la nouvelle version de MacHack en 1978.
Par conséquent, à la fin des années 1970, il pouvait rivaliser avec les humains, mais ne pouvait pas jouer à un niveau "maître".
Mais les années 1980 sont arrivées.
4. Les années 1980 : un challenge pour l'humanité
Au début des années 1980, la programmation de moteurs d'échecs par ordinateur est devenue une activité lucrative. Les ordinateurs personnels se sont répandus dans les ménages. L'intérêt pour les logiciels personnalisés et spécialisés - y compris les moteurs d'échecs informatiques - a explosé. Rien qu'en 1982, les sociétés d'échecs informatiques ont dépassé les 100 millions de ventes.
Il n'est donc pas surprenant que les moteurs d'échecs informatiques aient continué à s'améliorer. En 1980, leur programmation est devenue une compétition sérieuse. Edward Fredkin, professeur d'informatique à l'Université Carnegie Mellon, a présenté le prix Fredkin. Il a offert des prix en argent pour diverses réalisations dans le monde de la programmation d'échecs par ordinateur (5000$ pour le premier moteur à atteindre le niveau Maître, 10000$ pour le premier moteur à atteindre le niveau Grand Maître, 100000$ pour le premier moteur à battre le champion du monde).
La course était lancée. Le nombre et la puissance des moteurs d'échecs informatiques ont continué à augmenter.
Le collègue de Fredkin de l'Université Carnegie Mellon a ouvert la voie. Le projet le plus notable et le fer de lance d'une génération entière est Deep Thought - le premier moteur informatique d'échecs à avoir atteint le niveau Grandmaster. En 1988, il a partagé la première place avec le grand maître Tony Miles dans le championnat US Open. En 1989, il a facilement battu le Maître International David Levy quatre matchs à zéro.
La chute de l'humanité semblait inévitable. À la recherche de son champion, il s'est tourné vers le champion du monde en titre et sans doute le plus grand joueur de tous les temps - Garry Kasparov. Tout d'abord, lors d'une exposition simultanée iconique à Hambourg en 1985, il a joué contre 32 ( !) moteurs d'échecs les plus puissants - et les a tous battus ( !!!). Puis, en 1989, il a affronté Deep Thought dans un match de deux matchs, qu'il a également gagné (source : Kasparov And Thirty Years Of Computer Chess).
Ainsi, dans ses rencontres avec les moteurs dans les années 1980, Garry est devenu l'"élu".
Hélas, dans les années 1990, lui aussi tomberait.
5. 1990 - 1997 : les moteurs prennent le relais
Ainsi, en 1989, l'humanité a gagné la bataille, mais pas encore la guerre. Dans les années 1990, il y a eu beaucoup plus d'affrontements entre les humains et les moteurs d'échecs informatiques. Les meilleurs moteurs d'échecs ont même participé à des tournois d'échecs d'élite - avec un succès mitigé. Plusieurs matchs "humain contre machine" ont été organisés, mais aucun d'entre eux n'est devenu célèbre comme le match dans lequel le moteur a battu le champion du monde en 1997.
En 1989, les chercheurs impliqués dans le projet Deep Thought ont été embauchés par IBM. Ils ont commencé à développer une version plus puissante du moteur.
Le nom du projet était Deep Blue. En 1996, seulement 7 ans après le match Kasparov - Deep Thought, le deuxième round de "man vs machine" a eu lieu : le premier match Kasparov - Deep Blue. Dans le tout premier jeu, Deep Blue a choqué Kasparov et est devenu le premier moteur d'ordinateur d'échecs à battre un champion du monde dans un jeu classique. Toutefois, Garry a lui-même composé et a remporté le match avec le résultat 4-2, prolongeant une fois de plus l'inévitable.
L'échec n'a pas découragé les programmeurs de Deep Blue. Au cours de l'année suivante, ils ont continué à améliorer la puissance du moteur. Ils ont même embauché le grand maître Joel Benjamin comme consultant pour les aider à construire le livre d'ouverture. Après une préparation minutieuse, ils ont mis Kasparov au défi de rejouer une nouvelle fois - et comme ils disent - le reste appartient à l'histoire.
Dans le célèbre match, Kasparov a gagné le premier match. Mais le 44ème mouvement contre-intuitif du moteur l'a confondu. Cela a ébranlé sa confiance et il a raté de sérieuses occasions de match nul dans le 2e match. Puis Deep Blue l'a écrasé en 6ème partie avec un sacrifice de cavalier tôt dans la première partie. Cela a scellé le destin de Kasparov et a valu à l'équipe Deep Blue le prix Fredkin (source : Deep Blue Inventors Win Fredkin Prize for Computer Chess.
Après le match, il a affirmé qu'IBM avait triché et qu'un humain était en train de faire les mouvements (Joel Benjamin). D'autres sources pensent qu'un bug dans le code de Deep Blue lui a apporté la victoire (source : Did Deep Blue Beat Kasparov Because Of A Glitch?
Dans tous les cas, 1997 a symboliquement marqué la fin de la domination humaine sur les moteurs informatiques d'échecs.
Cependant, les humains ne se sont pas encore résignés.
6. 1997-2006 : le dernier combat de l'humanité
Après la victoire de Deep Blue, tout le monde s'attendait à ce que l'écart entre les humains et les machines se creuse davantage. Cependant, au cours des six années suivantes, jusqu'en 2003 environ, l'humanité a livré sa dernière bataille.
Par exemple, en 2000, le moteur d'échecs informatique Deep Junior a participé au Dortmund Elite Supertournament - et a obtenu seulement 50% des points. En 2002, le nouveau champion du monde Vladimir Kramnik a fait match nul contre le moteur d'échecs informatique Deep Fritz (malgré une erreur catastrophique de mat-en-1). En 2003, Garry Kasparov a fait match nul contre Deep Junior 7 et X3d Fritz.
Hélas, cette petite lueur d'espoir a été rapidement détruite par le moteur d'échecs informatique Hydra. En 2004, il a battu les GM Evgeny Vladimirov (3-1) et Ruslan Ponomariov (2-0). Puis, en 2005, il a détruit Michael Adams, un membre du top 10 mondial, avec un score dévastateur : 5,5-0,5.
Et en 2006, Deep Fritz a enfoncé le dernier clou dans le cercueil de l'humanité en battant le champion du monde Vladimir Kramnik 4-2.
7. 2006-2017 : l'âge d'or des moteurs d'échecs informatiques
La décennie 2006-2017 est l'âge d'or des moteurs d'échecs informatiques.
Sur une base quotidienne, les moteurs d'échecs informatiques ont infiltré tous les domaines des échecs - de la diffusion à l'analyse du jeu. Ils sont devenus un outil intégral pour tout joueur de tournoi d'échecs. Ils ont élevé une génération de jeunes joueurs bien plus forts - la génération dite informatique. Lorsque les smartphones sont apparus, leurs versions Android et iOS ont été immédiatement développées, au grand dam de tout comité anti-triche des tournois.
Le championnat mondial d'échecs par ordinateur a continué à se développer. En raison du prestige et de l'argent en jeu, certaines controverses ont suivi. Le cas le plus tristement célèbre est la disqualification du moteur d'échecs informatique Rybka, le vainqueur consécutif des quatre éditions entre 2007 et 2010, en raison du plagiat de code (source : Rybka, The World’s Best Chess Engine, Outlawed and Disqualified.
En plus du championnat du monde d'échecs, une nouvelle compétition a été introduite en 2010 - Top Chess Engines Competition. Contrairement au WCC, la TCEC propose des parties plus longues jouées avec du matériel haut de gamme, ce qui conduit à une meilleure qualité des échecs.
Les rapprochements homme-machine ont prouvé que l'écart se creuse. Au cours de la décennie, un certain nombre de matchs de handicap ont eu lieu, au cours desquels les moteurs ont donné diverses cotes à des grands maîtres forts. Les résultats ont été déprimants pour l'humanité. Par exemple, en 2014, le moteur d'échecs informatique Stockfish a battu le GM Daniel Naroditsky qui a utilisé l'aide d'une première version de Rybka. En 2015, le moteur d'échecs Komodo a joué 6 parties contre Sergei Movsesian, un ancien membre du top 10 et l'a facilement écrasé. Et en 2016, Hikaru Nakamura, un membre actuel du top 10 mondial, se sentira lui aussi déprimé face à Komodo.
Pendant la période 2006-2017, les moteurs d'échecs informatiques classiques ont dominé. Jusqu'à la fin de 2017, il ne s'est rien passé de révolutionnaire. Leur force changeait constamment, mais lentement. Tout semblait familier et personne ne s'attendait à des changements radicaux, à des percées majeures.
8. 2017 et au-delà : une nouvelle révolution ?
IMAGE illustration-moteur-echecs-ia-google-alphazero
Le 5 décembre 2017, un groupe de scientifiques de la société Google AI Deep a fait du bruit dans le monde des échecs.
Dans l'article intitulé "Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm", ils ont décrit le développement d'un nouveau moteur d'échecs, AlphaZero, basé sur une approche complètement nouvelle. Au lieu d'une recherche alpha-bêta et d'une fonction d'approximation linéaire pour l'évaluation de position utilisée par les moteurs traditionnels, AlphaZero utilise une fonction d'approximation non linéaire basée sur un réseau neuronal profond et la simulation Monte Carlo. En conséquence, au lieu de recourir à la force brute dans l'analyse, AlphaZero est capable d'"auto-apprendre" les échecs.
L'équipe a testé la puissance du nouveau moteur lors d'un match de 100 parties contre le moteur d'échecs classique le plus puissant actuellement disponible - Stockfish 8. Le résultat du match a été stupéfiant : +28 -0 =72 (28 victoires, 0 défaites et 72 parties nulles) en faveur de AlphaZero. Mais ce qui était encore plus impressionnant, c'était le style de jeu de l'AlphaZero - il était beaucoup plus intuitif et humain que le jeu des moteurs traditionnels.
Les réactions sur le papier ont été mitigées. Beaucoup de joueurs d'échecs ont été stupéfaits - le puissant Stockfish qui a subi une telle défaite était en effet un miracle. Mais d'un autre côté, il y avait beaucoup de scepticisme. Beaucoup de critiques ont été adressées sur l'environnement du match - Stockfish a fonctionné sur du matériel de qualité inférieure et a joué sans livre d'ouverture. Un article intéressant à lire à ce sujet : Alpha Zero a scientific breakthrough in AI.
Cependant, le 7 décembre 2018, un autre article a été publié par l'équipe de Deep Mind, intitulé "A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play". Ils y présentaient les résultats d'un autre match entre Alpha Zero et Stockfish. Sur 1000 parties, A0 a gagné 155 parties et n'en a perdu que 6, même si l'ancienne version de Stockfish a été utilisée, c'est un résultat impressionnant.
Que le scepticisme soit justifié ou non, Alpha Zero a eu un impact significatif sur le monde des échecs. Ils ont forcé tout le monde à s'interroger sur la suite des événements. Cela pourrait signifier le début d'une autre révolution...