IA, échecs et go : comment battre l’humain à son propre jeu

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'IA de nous vaincre...

IA, échecs et go :  comment battre l’humain à son propre jeu

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.

Turing (sur la droite) en compagnie de collègues

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 19x19 lignes, sur lequel une pierre noire ou blanche peut être posée à chaque intersection.

Goban traditionnel de 19*19 lignes (Goban1, Wikimedia)
Goban traditionnel de 19*19 lignes (Goban1, Wikimedia)

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.

Lee Sedol contre AlphaGo, REUTERS/Korea Baduk Association/News
Lee Sedol contre AlphaGo, © REUTERS/Korea Baduk Association/News

À 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.

Résultats des matchs d'AlphaZero aux échecs, au shogi et au go, © DeepMind

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 !

Natalia W.


Sources

Computers and Chess - A History
In 1945 Alan Turing (1912-1954) used chess-playing as an example of what a computer could do. Turing himself was a weak chess player. In 1946 Alan Turing made his first reference to machine intelligence in connection with chess-playing. In 1947, Alan Turing specified the first chess program for ches…
Twenty years on from Deep Blue vs Kasparov: how a chess match started the big data revolution
The in depth story of a student project that paved the way for a society-level shift in how we use computers.
In Major AI Breakthrough, Google System Secretly Beats Top Player at the Ancient Game of Go
As recently as this month, top AI experts outside Google questioned whether such a victory could be achieved anytime soon.
Former Go champion beaten by DeepMind retires after declaring AI invincible
Humans take an L after AI triumphs.