Leela Chess Zero

Avec plus de 320 millions de parties d’échecs au compteur, Leela Chess Zero (Lc0) ne joue pas aux échecs comme les autres. Disponible sous licence GPL-3.0, ce programme a un Elo autour de 3 000, et côtoie les sommets de la (petite) planète échecs. 

Sommaire

• Introduction
• Le grand rival, StockFish
• La mêlée des prétendants
• La montée en puissance dans les tournois
• Impact sur les échecs, perspectives

Introduction

Depuis de nombreuses années, les jeux d’échecs et de go ont vu des affrontements entre humains et ordinateurs. En ce qui concerne les échecs, le tournant qui va entériner la domination des machines sur les hommes est la série de matchs Deep Blue - Kasparov de 1996 à 1997. Pour le jeu de go, les humains ont longtemps conservé un avantage, le match entre AlphaGo et Lee Sedol de 2016 marquant probablement le passage à la domination des machines sur les humains.

Développé chez DeepMind, société spécialisée dans l’intelligence artificielle, AlphaGo est un logiciel s’appuyant sur l’apprentissage supervisé. Des parties de go ont donc été choisies et utilisées pour entraîner un réseau de neurones profond. L’hégémonie de AlphaGo va cependant être de courte durée : fin 2017, une équipe de Deepmind publie un article dans Nature décrivant AlphaGo Zero, un logiciel s’appuyant sur l’apprentissage non supervisé. Le réseau de neurones commence par jouer des coups aléatoires et devient un peu plus fort après chaque partie. Après en avoir joué près de 5 millions, AlphaGo Zero écrase purement et simplement ses concurrents, avec notamment une victoire cent à zéro contre la version de AlphaGo ayant vaincu Lee Sedol. Le roi est mort, vive le roi !

Fin 2017, un second article de DeepMind présente le logiciel AlphaZero, adaptation de AlphaGo Zero aux jeux d’échecs et de shogi, jeux dans lesquels il remporte des victoires contre les meilleurs programmes. Quelques parties d’échecs entre AlphaZero et Stockfish sont montrées. De nouvelles stratégies sont ainsi esquissées, ouvrant la voie à de nouvelles ouvertures et à des avancées théoriques dans la compréhension de ce jeu millénaire. Malheureusement, le logiciel développé par DeepMind n’est pas accessible à tous, au grand dam des passionnés. C’est dans ce contexte qu’arrivent Leela Zero (initié par Gian-Carlo Pascutto) et Leela Chess Zero. Basés sur les publications de DeepMind, les deux logiciels sous licence libre aspirent à dominer les jeux de go et d’échecs.

La clé de voûte d’un logiciel jouant aux échecs est l’évaluation d’une position donnée, ainsi que la sélection des coups jouables. Les évaluations les plus simples sont linéaires : les probabilités de gain associées à l’avantage matériel — la tour est plus forte que le pion —, à l’avantage positionnel — le pion qui atteint la dernière ligne est plus fort que la tour — et à l’initiative — simplifions en assimilant l’initiative à l’attaque — sont combinées linéairement à travers une somme pondérée. Les réseaux de neurones s’affranchissent d’une telle hypothèse et ont une évaluation de la position qui est non-linéaire. En ce qui concerne Lc0, le réseau de neurones est chargé de l’évaluation. À partir d’une position donnée, des coups jouables sont sélectionnés aléatoirement (recherche arborescente Monte-Carlo) et évalués. Pour des raisons d’efficacité, la sélection des coups jouables n’est pas totalement aléatoire : elle s’appuie sur une variante de la stratégie UCT, elle-même inspirée du problème du bandit manchot.

Pour les jeux de go et d’échecs, les machines ont atteint un niveau considérable. En ce qui concerne les échecs, les adversaires redoutables des années 90 sont désormais les partenaires et les enseignants des joueurs professionnels, et ils assistent les plateformes de jeu en ligne dans la détection des tricheurs (point abordé vers 1h03 cet article). Stockfish a longtemps été caricaturé comme un prodige de calcul et un défenseur sans égal, la promesse d’un jeu soporifique à haut niveau. Certaines des parties opposant AlphaZero et Lc0 à Stockfish ont chamboulé cette conception, les réseaux de neurones n’hésitant pas à sacrifier des pièces pour obtenir une position avantageuse à long terme, échappant ainsi à la ligne Maginot qu’avait dressée Stockfish. À n’en pas douter, AlphaZero et Lc0 sont disruptifs.

Le grand rival, StockFish

Il existe un grand nombre de logiciels sachant jouer aux échecs. Les performances de ces derniers évoluent au cours des mises à jour, mais également avec les progrès des (co)processeurs.

L’un des logiciels ayant le plus haut niveau est StockFish, dont la version 12 a fait l’objet d’une dépêche ici, et dont la version 13 est disponible depuis Février 2021. Il est disponible sous licence GPL v3.0 sur github. Une de ses forces, c’est sa plateforme de tests distribués Fishtest. Des volontaires donnent du temps de calcul afin d’évaluer les modifications apportées au programme. L’ajout d’un réseau de neurones à partir de la version 12 a donné un avantage important à StockFish. Avantage d’autant plus précieux qu’il ne nécessite pas l’utilisation d’une carte graphique ou d’un coprocesseur.

StockFish peut utiliser jusqu’à 512 fils d’exécution pour évaluer une position et sélectionner les meilleurs coups. Plus le programme a accès à une puissance de calcul élevée, plus son évaluation est précise. Ainsi, certaines positions complexes ne peuvent être évaluées précisément qu’avec une puissance de calcul élevée, ou après un temps de calcul long. La finesse de l’analyse correspond plus ou moins à la profondeur qui la caractérise. Par exemple, avec une profondeur d’analyse de 20, StockFish évalue la position après 20 coups joués, soit 10 coups pour chaque camp, l’exploration du graphe étant non exhaustive.

La mêlée des prétendants

L’offre est pléthorique, et la liste qui suit n’est qu’illustrative.

En premier lieu, citons Komodo (par Don Dailey et Mark Lefler). Le varan a remporté de nombreuses compétitions. Depuis novembre 2020, la version dragon intègre d’ailleurs un réseau de neurones. Les versions 12 et antérieures sont disponibles gratuitement.

À la sortie du podium constitué par Lc0, StockFish et Komodo, nous trouvons l’illustre Houdini (par Robert Houdart). Les performances passées étaient impressionnantes, mais le logiciel est en perte de vitesse et la dernière version date de novembre 2017. Les versions 1.5a et antérieures sont disponibles gratuitement. La version 6 du magicien a fait l’objet de sérieuses controverses.

Enfin, signalons le superbe Stoofvlees (par Gian-Carlo Pascutto, l’initiateur de Leela Zero). Ce logiciel comporte un réseau de neurones qui a été entraîné à partir de parties de grands maîtres, dans l’espoir de produire un jeu humain à très haut niveau. La carbonade flamande figure en bonne place dans les compétitions internationales mais n’est pas téléchargeable.

La controverse ayant frappé Houdini a probablement hérissé le poil des aficionados du logiciel libre qui peuplent cet espace. Dans la même veine, on peut évoquer les controverses entourant AllieStein dont une partie provenait de Lc0. Plus récemment, chessbase (Albert Silver) a récidivé : Deus X était une copie de Lc0, Fat Fritz 2 est une copie de StockFish. Et c’est 100 euros la copie.

La montée en puissance dans les tournois

En avril 2018, un match est organisé entre Lc0 et le Grand Maître (GM) Andrew Tang. Le réseau de neurones s’appuie sur une GTX 1060 et concède quelques défaites contre le GM. Outre le résumé du match sur lichess, n’hésitez pas à visualiser la performance impressionnante du GM en cadence ultra-rapide sur twitch.

Août 2018, saison 13 du Top Chess Engine Championship (TCEC) : Lc0 remporte la division 4 mais stagne en division 3 après un départage défavorable contre le logiciel Arasan. Les performances de Lc0 sont jugées décevantes, à juste titre, les cartes graphiques étaient en surchauffe.

Février 2019, saison 14 du TCEC : Lc0 accède à la finale. Défaite contre StockFish d’un petit point après 100 parties.

Mai 2019, saison 15 du TCEC : Lc0 remporte le tournoi avec 7 points d’avance sur StockFish au bout de 100 matchs. À titre illustratif, les parties 61 et 62 de la finale entre StockFish et Lc0 sont visibles ci-dessous. Lc0 remporte les deux parties, avec les pièces noires pour la partie 61 et avec les pièces blanches pour la partie 62. Dans le cadre du TCEC, les premiers coups de chaque position sont imposés par les organisateurs afin d’introduire un déséquilibre dans la position. La position imposée est jouée deux fois, les logiciels alternant les couleurs. En ce qui concerne la position imposée pour les parties 61 et 62, une variante de la Trompowsky, la victoire de Lc0 dans les deux parties montre une compréhension de la position nettement supérieure. Notez que les positions n’aboutissent généralement pas à un mat, la partie s’arrêtant lorsque les deux logiciels s’accordent pour évaluer la position gagnante pour un camp.

TCEC15, partie 61	TCEC15, partie 62

Octobre 2019, saison 16 du TCEC : remportée par StockFish, Lc0 termine à la troisième place et échoue à se qualifier en finale. Le finaliste perdant, AllieStein, s’appuie partiellement sur Lc0.

Avril 2020, saison 17 du TCEC : remportée par Lc0 avec 5 points d’avance sur StockFish au bout de 100 matchs.

Juillet 2020, saison 18 du TCEC : Lc0 échoue en finale contre StockFish avec 7 points de retard. Ci-dessous une des victoires de Lc0 avec les blancs : après le sacrifice de la dame, victoire par abandon, l’avantage final de deux pièces (fou + cavalier) est décisif.

Juillet 2020, lors de la sixième coupe TCEC, Lc0 échoue en finale contre AllieStein. Ce dernier a vaincu StockFish en demi-finale, et s’appuie partiellement sur Lc0.

Août 2020 : StockFish intègre un réseau de neurones et passe à la vitesse supérieure.

Octobre 2020, saison 19 du TCEC : Lc0 échoue en finale contre StockFish avec 9 points de retard. Ci-dessous une des victoires de StockFish avec les blancs : après le sacrifice d’un cavalier puis d’une qualité (échange d’une tour contre un fou), l’avantage final de quatre pions contre une tour est décisif. Le réseau de neurones assistant l’algorithme d’évaluation de la position ajouté dans la version 12 de Stockfish semble renforcer le logiciel, avec une capacité accrue à convertir en victoire les positions avantageuses.

Novembre 2020, septième coupe TCEC : Lc0 échoue en finale contre StockFish.

Décembre 2020, saison 20 du TCEC : Lc0 échoue à nouveau en finale contre StockFish avec 6 points de retard.

Février 2021, huitième coupe TCEC : Lc0 échoue encore en finale contre StockFish. Ci-dessous la victoire de Lc0 contre AllieStein en demi-finale.

Impact sur les échecs, perspectives

Les derniers tournois montrent que Lc0 joue très bien aux échecs. Mais le roi StockFish semble indétrônable, en particulier depuis qu’il intègre un réseau de neurones. Cependant, l’année 2021 pourrait réserver de belles surprises. L’un des principaux développeurs de Lc0 a écrit un nouveau moteur, Ceres, dont le niveau de parallélisme semble doubler la puissance de calcul de Lc0. Dans ces conditions, le duel entre Stockfish et Lc0 pourrait tourner à l’avantage de Lc0, mais pour bénéficier des nouveaux algorithmes apportés par Ceres, une réécriture complète de Lc0 semble inéluctable.

Les ordinateurs et l’intelligence artificielle ont révolutionné le jeu d’échecs à haut niveau. Les premières études théoriques dont on a trace étaient dédiées aux finales et remontent à environ 820. À partir de la fin des années 90, les analyses informatiques deviennent prépondérantes. Typiquement, les positions étaient étudiées avec StockFish ou ses précurseurs, véritables oracles permettant d’évaluer les chances de gain associées à différentes variantes. L’arrivée des réseaux de neurones AlphaZero et Lc0 change complètement la donne : on peut ré-évaluer la plupart des ouvertures ainsi que les positions complexes obtenues en milieu de jeu. Le fait d’avoir accès à plusieurs programmes, chacun ayant une approche spécifique, conduit à mieux comprendre et évaluer les positions complexes.

Aller plus loin

• Github Lc0 (246 clics)
• Estimation Elo Lc0 (165 clics)
• Jouez contre Lc0 (287 clics)
• Page Wikipedia de Lc0 (56 clics)
• Page Wikipédia de Lc0 (175 clics)