Aujourd’hui, on remarque que certains (dont les meilleurs) moteurs/IA d’échecs participent à des championnats entre ordinateurs (les plus renommés étant le World Computer Chess Championship et le Top Chess Engine Championship), leur niveau est maintenant largement supérieur à celui des meilleurs joueurs humains. Il est donc naturel de se poser la question : l’intelligence artificielle mettra-t-elle bientôt fin aux tournois humains d’échecs ? Cet article, répond à cette question en analysant en profondeur l’évolution récente des intelligences artificielles aux échecs grâce à des algorithmes de réseaux de neurones encore perfectibles.
Le jeu d’échecs, datant du XVe siècle avec les règles telles qu’on les connaît actuellement, est d’une complexité telle que le jeu n’est pas résolu et ne le sera peut-être jamais. Un jeu résolu est un jeu dont le résultat (gain, perte ou nul) peut être correctement prédit à partir de n’importe quelle position, en supposant que les deux joueurs jouent à la perfection. On peut facilement se rendre compte de la complexité à résoudre ce jeu en déterminant le nombre de parties uniques jouables : 10120 (un 1 suivi de 120 zéros), un nombre inconcevable, en sachant que le nombre estimé d’atomes dans l’univers est de « seulement » 1080…
Les programmes d’échecs font partie de l’un des plus anciens domaines de l’intelligence artificielle (IA), ayant débuté au début des années 1930, mais n’ayant que récemment dépassé l’humain dans ce jeu. En effet, l’intelligence artificielle aux échecs reçut un coup de projecteur en 1997 lors de la défaite de Kasparov, alors champion du monde d’échecs et l’un des meilleurs joueurs de tous les temps, contre l’IA Deep Blue d’IBM. C’est à partir de ce match que la supériorité humaine aux échecs commença à être menacée.
Aujourd’hui il existe de nombreux moteurs/IA d’échecs, dont les meilleurs participent même à des championnats entre ordinateurs (les plus renommés étant le World Computer Chess Championship et le Top Chess Engine Championship), leur niveau étant maintenant largement supérieur à celui des meilleurs joueurs humains. Les quatre IA les plus titrées sont Stockfish, Houdini, Komodo et LeelaChessZero.
Concepts échiquéens
Les moteurs d’échecs les plus performants reposent sur un ensemble de concepts et d’algorithmes combinés qui leur permettent d’atteindre un niveau de jeu bien supérieur aux joueurs humains.
Un des concepts les plus importants pour la plupart des IA est le fait d’attribuer une valeur à chaque pièce du jeu, sur lesquelles se basent les algorithmes pour trouver les meilleurs coups. Les valeurs communément admises sont les suivantes : un pion vaut 1 point, un fou 3 points, un cavalier 3, une tour 5 et la dame 9 (le roi n’a pas de valeur, celui-ci ne pouvant pas être capturé). En comptant le nombre de points que vaut le total des pièces sur l’échiquier dans chaque camp, on peut savoir si un des joueurs a l’avantage ou si la partie est équilibrée à un moment donné, en fonction des pièces capturées. Par exemple, on considère généralement que capturer un fou et un cavalier (6 points) est légèrement meilleur que capturer une tour (5 points).
Certains concepts dérivés d’études théoriques humaines des échecs font partie prenante des algorithmes des moteurs d’échecs. Parmi eux, on retrouve :
● Le contrôle du centre : le joueur ayant le mieux contrôlé le centre (notamment les quatre cases centrales), c’est-à-dire ayant le plus de pièces visant le centre ou sur le centre, obtient une position plus avantageuse
● Le développement des pièces : un joueur ayant sorti plus de pièces de leurs positions initiales que son adversaire aura un avantage dans la suite de la partie
● La sécurité du roi : il est plus facile de menacer de mat un roi non entouré de pièces alliées qu’un roi caché derrière une forteresse de pions
● Le déséquilibre matériel : si le total des valeurs des pièces restantes d’un joueur est supérieur à celui de son adversaire, alors celui-ci a un avantage
● La structure de pions : par exemple, si un joueur a deux ou trois pions sur une même colonne, alors sa position peut être plus compliquée à jouer que son adversaire sur le long terme
Algorithmes des moteurs d’échecs
Les meilleurs moteurs d’échecs actuels sont composés de deux parties : un algorithme de recherche de coups permettant de proposer une sélection restreinte de bons coups, et une fonction d’évaluation pour choisir le coup à jouer.
Deux algorithmes de recherche majoritairement utilisés sont l’algorithme Recherche Arborescente de Monte-Carlo (MCTS) et l’élagage alpha-bêta.
Ces algorithmes explorent l’arbre des configurations possibles de l’échiquier, représenté de la manière suivante (voir schéma ci-dessous) : chaque nœud de l’arbre est une configuration sur l’échiquier à un moment donné de la partie, en commençant par la configuration initiale du jeu en haut de l’arbre (premier nœud). Chaque nœud fils (descendant d’un nœud père) est la configuration sur l’échiquier après avoir joué un coup après la configuration du nœud père. Tous les nœuds fils représentent donc les coups jouables au moment de la configuration du nœud père.
On peut par exemple enregistrer pour chaque configuration le nombre de simulations jouées qui sont passées par cette configuration, ainsi que le nombre de victoires, et sélectionner quelques meilleurs coups possibles en choisissant les nœuds avec les plus grands pourcentages de victoire et/ou des nœuds n’ayant pas été beaucoup explorés.
C’est ainsi que marche en partie le moteur LeelaChessZero, en appliquant l’algorithme MCTS pour faire une présélection de quelques bons coups parmi tous ceux possibles.
Après cette présélection, les IA d’échecs utilisent une fonction d’évaluation pour choisir le coup à jouer. Cette fonction peut prendre par exemple la forme d’une pondération d’un ensemble de critères déterminant une position avantageuse ou mauvaise, telle que :
c1 * déséquilibre matériel + c2 * développement des pièces + c3 * sécurité du roi + c4 * contrôle du centre + c5 * structure de pions + …
Le coup choisi sera ensuite celui dont la configuration maximisera la fonction d’évaluation.
C’est une fonction de ce genre qu’utilisait Stockfish jusqu’en 2020. Seulement, depuis l’avènement des réseaux de neurones (Deep Learning), de nouveaux moteurs comme LeelaChessZero (créé début 2018) ont vu le jour utilisant un réseau de neurones. Cet algorithme crée lui-même la fonction d’évaluation à partir d’un grand nombre de simulations de parties. Cette révolution dans l’intelligence artificielle aux échecs a entraîné les concepteurs de Stockfish à modifier leur IA en implémentant un tel réseau de neurones, ce qui augmenta son niveau déjà très élevé.
Un autre point à noter qui donne un tel niveau aux moteurs d’échecs est la profondeur de calcul : ils peuvent calculer une énorme quantité de configurations, et par exemple évaluer les configurations après les 30 prochains coups.
Afin d’illustrer cette idée, lors d’un match opposant le moteur AlphaZero (précurseur de LeelaChessZero) à Stockfish en 2017, AlphaZero regardait 80000 configurations par seconde, et Stockfish 70 millions par seconde. Malgré cet énorme différentiel de calcul, AlphaZero fut le gagnant au terme de plusieurs parties. La clé de la victoire d’AlphaZero fut le réseau de neurone implémenté qui créa en 4 heures de simulations de parties une meilleure fonction d’évaluation que celle de Stockfish, ce qui l’avantagea dans cette opposition.
Tables de finale
En plus de tous ces algorithmes, les IA enregistrent dans leur mémoire des tables de finale. On appelle communément finale une fin de partie, où le nombre de pièces restant sur l’échiquier est très réduit. Une table de finale est une base de données qui contient des positions de finales du jeu d’échecs et leur évaluation théorique avec un jeu parfait (partie nulle ou victoire d’un des camps, et nombre de coups avant la victoire). Ainsi, les IA peuvent chercher à éviter ou à atteindre une position donnée. De telles bases de données de finales sont générées en utilisant entre autres une forme d’analyse rétrograde : les positions de trois pièces sont utilisées pour l’analyse des positions de quatre pièces, ces dernières participent à la génération de celles de cinq pièces, etc.
En général, la base de données enregistre chaque position possible avec certaines pièces restant sur l’échiquier, et les meilleurs coups selon que ce soit aux blancs ou aux noirs de jouer le prochain coup.
Pour le moment, des tables ont été constituées pour des finales allant jusqu’à 7 pièces (2 rois + 5 pièces). Pour les finales à 6 pièces ou moins, toutes les positions ont été étudiées (près de 4000 milliards). Pour les finales à 7 pièces, les situations incluant un roi seul face à 6 pièces de la couleur opposée ont été ignorées (car solution trop évidente pour le camp ayant 6 pièces), mais le nombre de positions analysées reste gigantesque (plus de 400 000 milliards). Les recherches sur la création de tables avec 8 pièces sont en cours.
Certains moteurs intègrent donc ces tables de finales, leur permettant de jouer parfaitement sans calculer lorsque le nombre de pièces sur l’échiquier est inférieur à 8.
L’intelligence artificielle mettra-t-elle bientôt fin aux tournois humains d’échecs ?
Les intelligences artificielles aux échecs, malgré leur évolution récente grâce à des algorithmes de réseaux de neurones, restent perfectibles : en effet, elles n’ont pas résolu la plupart des positions, il est encore impossible pour elles de prédire comment se terminera une partie à un moment donné, sur une victoire ou un match nul, sauf pour des finales à 7 pièces ou moins. L’immense nombre de parties uniques jouables fait que les IA d’échecs ne sont pas encore prêtes à résoudre la majorité des configurations, malgré leur niveau de jeu presque parfait.
Enfin, même dans le cas où l’intelligence artificielle résoudrait un grand nombre de positions du jeu d’échecs, il sera impossible pour les joueurs humains de retenir toutes les suites de coups selon les coups adverses, les variantes étant trop nombreuses à retenir. Les meilleurs joueurs mondiaux se préparent déjà avant les tournois avec des moteurs d’échecs pour analyser certaines variantes des ouvertures (premiers coups) les plus jouées par leurs adversaires. Cependant, les résultats ne sont pas toujours au rendez-vous même lorsque le début de partie a été analysé à l’avance, car les joueurs ne peuvent pas retenir les milieux de partie, tellement le nombre de configurations différentes est élevé. Aussi, le déroulement des parties dépend à moitié des coups de l’adversaire, qui peut choisir à n’importe quel moment de sortir d’une variante déjà connue en jouant des coups inattendus.
En conclusion, l’intelligence artificielle a certes dépassé l’humain, mais l’attrait pour les échecs et les tournois humains ne sont pas près de disparaître.
