Les échecs et le go sont des jeux pratiqués par les Hommes depuis des millénaires, mais cela n’a pas empêché l’intelligence artificielle de nous battre en quelques décennies. Dans cet article, découvrez comment les algorithmes d’échecs et de go ont évolué depuis les années 50, pour aller jusqu’à vaincre les champions en titre. Bonne lecture !
Une brève histoire des ordinateurs aux échecs
Dès que les premiers ordinateurs modernes apparaissent, au milieu du XXème siècle, les premiers informaticiens essayent de leur apprendre à jouer aux échecs. Par exemple, Alan Turing, pionnier dans le développement de l’informatique et de l’intelligence artificielle, rédigea en 1950 un logiciel d’échecs qui répondait aux critères du test de Turing. Ce test, dont il développa la théorie la même année, consiste en une confrontation d’un humain et d’une machine : l’humain doit déterminer si la machine face à lui est un ordinateur ou un humain, selon la manière dont il fonctionne. Le logiciel d’échecs de Turing arrivait à passer ce test, ce qui signifie qu’il jouait aux échecs d’une telle façon qu’il n’était pas possible de déterminer s’il s’agissait d’un ordinateur ou d’un humain.
A partir de ce moment-là, une succession de logiciels d’échecs furent créés, tous plus puissants que les autres. En effet, la force d’un logiciel d’échecs classique dépend généralement de sa puissance de calcul, c’est-à-dire sa capacité à évaluer le plus de variantes possibles et de plus en plus de coups en avant. Ainsi, quand les ordinateurs sont devenus plus performants, les logiciels d’échecs ont naturellement suivi.
♟️ Ouvertures et finales, qu’est-ce que c’est ? Les logiciels d’échecs sont agrémentés de bases de données d’ouvertures et de finales afin d’améliorer leur vitesse de calcul et leur précision. Les ouvertures, à savoir les premiers coups de la partie, ont fait l’objet d’un travail théorique sur de nombreuses générations de joueurs. D’un autre côté, les finales reposent sur des combinaisons de coups précises où la moindre erreur peut changer le résultat de la partie.
Si leur puissance de calcul augmentait, les logiciels d’échecs ne sont pas arrivés à atteindre le niveau des plus grands joueurs d’échecs avant un certain temps. C’est seulement en 1996 que le logiciel d’échecs Deep Blue, développé par IBM, parvient à décrocher un point contre le champion du monde en titre de l’époque, Garry Kasparov. Depuis Deep Blue, les logiciels n’ont jamais cessé de s’améliorer : aujourd’hui, le logiciel Stockfish écrase n’importe quel joueur d’échecs, y compris Magnus Carlsen, le champion du monde en titre.
La difficulté de programmer un logiciel de go
En parallèle des progrès informatiques qui ont permis de développer de puissants logiciels d’échecs relativement rapidement, les programmes de go ont suivi une évolution très lente. Le premier programme de go a été créé dans les années 60, mais, jusque dans les années 2010, aucun champion de go n’a fléchi contre un ordinateur sans devoir lui accorder un handicap conséquent.
Pourquoi une telle différence entre les échecs et le go ? Pour bien comprendre, il faut se pencher sur les règles du jeu originaire de Chine. Le jeu de go se joue sur un plateau (goban) de 19×19 lignes, sur lequel une pierre noire ou blanche peut être posée à chaque intersection.
Ainsi un joueur de go dispose de 361 options pour jouer son premier coup – et son adversaire de 360 réponses. Cela représente près de 130 000 possibilités pour calculer un seul coup avec la puissance de calcul pure d’un ordinateur. À titre de comparaison, aux échecs, seuls 20 coups sont possibles pour chaque camp en début de partie, soit 400 possibilités. Si l’on part du principe que le logiciel évalue toutes les options disponibles pour jouer un coup, on pourra donc dire qu’un ordinateur de même puissance est 325 fois plus fort aux échecs qu’au go.
Outre ces considérations mathématiques, le go est un jeu très complexe : si, aux échecs, un joueur ayant ne serait-ce qu’un pion de moins est facilement considéré comme perdant, l’avantage sur une position de go s’évalue en fonction du territoire conquis. Ce territoire ne dépend pas nécessairement du nombre de pierres sur le goban. Faute de référentiel, il est ainsi plus difficile pour un ordinateur de faire un choix entre deux coups similaires.
Au fil des ans, la programmation d’un logiciel de go performant est ainsi devenue un défi pour les informaticiens. Défi qui fut finalement relevé en 2015 par une filiale de Google : Deepmind.
L’intelligence artificielle de Google, reine des jeux
Google s’est emparé du défi de la programmation de logiciels de jeu avec une certaine idée en tête : se séparer de la puissance de calcul brute pour introduire des méthodes de machine learning. Le machine learning est une méthode d’apprentissage d’une intelligence artificielle : à l’aide d’une base de données, le logiciel va apprendre à reconnaître des motifs et des situations, pour les mettre en application.
AlphaGo a été entrainé avec une base de données de plus de 230 000 parties de go, et près de 6 000 ouvertures de parties de go. En tout, Alpha Go pouvait piocher dans près de 30 millions de coups de maîtres de go pour choisir les siens en fonction des situations qui se présentaient à lui. Une fois le logiciel entraîné, ce dernier enchaîne les victoires : d’abord, il bat Fan Hui, champion d’Europe 2015 de go, 5 à 0. En 2016, Alpha Go affronte Lee Sedol, joueur coréen prodige, et remporte une nouvelle fois la victoire. En 2019, le joueur annoncera d’ailleurs sa retraite professionnelle au go, en qualifiant AlphaGo d’adversaire « impossible à battre ». En mai 2017, Deepmind propose une nouvelle version de son logiciel, qui battra Ke Jie, un autre joueur professionnel de go.
À cause du passé particulier de la programmation de logiciels de go, AlphaGo est alors une véritable révolution. Pourtant, Deepmind ne s’arrête pas là : en octobre 2017, l’entreprise développe une version d’AlphaGo qui a appris à jouer au go uniquement en jouant contre elle-même, sans entraînement sur une base de données. Et les résultats furent concluants : non seulement cette version était performante contre des humains, mais elle battit sa version précédente 89 fois dans un match de 100 parties.
Forte de son succès, l’équipe Deepmind présente deux mois plus tard AlphaZero, un logiciel d’échecs, qui – comme la dernière version d’AlphaGo – a appris à jouer aux échecs uniquement contre lui-même. Seulement, plutôt de que faire jouer AlphaZero contre des professionnels, ses développeurs organisèrent un match contre le seul adversaire capable de le battre : le logiciel Stockfish 8. Le résultat est sans appel : sur 100 parties, 72 se sont finies par un match nul ; mais les 28 autres, dont 3 avec les Noirs, donnèrent lieu à une victoire d’AlphaZero.
Ce résultat a fait réagir la sphère échiquéenne, pas seulement à cause de la victoire du logiciel de Deepmind, mais aussi à cause de sa manière de jouer. En effet, AlphaZero défie quelque fois la logique du jeu d’échecs telle que la majorité des joueurs ont pu l’apprendre : sacrifices de pièces inattendus, mouvements “dangereux” de Roi… Des coups surprenants qui ont porté leurs fruits : d’abord confiant, Stockfish se considère gagnant face à ce qu’il considère comme des erreurs, et ce n’est toujours qu’à quelques coups de sa défaite que Stockfish comprend qu’il n’a plus aucune issue.
Google Deepmind n’a jamais diffusé le code d’AlphaZero au grand public. Est-ce par peur de détruire le monde du jeu d’échecs et d’en retirer son intérêt compétitif ? Comment un ordinateur a-t-il pu apprendre mieux par lui-même ce jeu, pourtant inventé par les humains ? Ces questionnements, qui n’ont pas forcément de réponses évidentes, ne sont peut-être pas prêts de s’arrêter. Entre force brute, machine learning, et même self-learning, d’autres méthodes d’apprentissage seront probablement développées, et feront naître une intelligence artificielle encore plus puissante qu’AlphaZero.
Les jeux de plateaux peuvent sembler être une problématique oisive, mais les méthodes utilisées pour la programmation d’un logiciel – qu’il soit classique ou qu’il fonctionne avec une IA – servent de fondations à des expérimentations dans d’autres domaines de la science : voitures autonomes, médecine assistée par ordinateur… Pour ces raisons, les jeux serviront sûrement encore longtemps de terrain de jeu pour les programmeurs du monde entier. Game on !
Par Natalia Wojnowski
Sources
- Computers and Chess – A History, billwall (Chess.com, 17 avril 2017)
- Twenty years from Deep Blue vs Kasparov : how a chest match started the big data revolution, Mark Robert Anderson (The Conversation, 11 mai 2017)
- In a Huge Breakthrough, Google’s AI Beats a Top Player at the Game of Go, Cade Metz (WIRED, 27 janvier 2016)
- Former Go champion beaten by DeepMind retires after declaring AI invincible, James Vincent (The Verge, 27 novembre 2019)
Cet article a été publié pour la première fois le 23 septembre 2021 sur Hypertext, le blog de l’association Plug’n’Play. N’hésitez pas à y faire un tour pour trouver d’autres articles sur le numérique !
