AlphaZero : l'IA de Google maîtrise les échecs et le Go en 24 heures

Les jeux de plateau (comme les échecs) sont un domaine largement étudié dans l'histoire de l'intelligence artificielle. Des pionniers comme Turing, Babbage, von Neumann et Shannon ont développé des théories, algorithmes et matériels pour analyser et jouer aux échecs. Et au cours des dernières années, nous avons vu des programmes similaires surpasser les humains dans des jeux bien plus complexes comme le Go et le Shogi (échecs japonais).

DeepMind de Google a un parcours phénoménal lorsqu'il s'agit de battre les humains aux jeux de plateau. En 2015, leur projet AlphaGo est devenu le premier programme informatique de Go à battre un humain (un joueur professionnel de Go). Et maintenant, ils ont développé un programme AlphaGo qui peut apprendre le jeu d'échecs par lui-même et battre un humain ou tout autre programme informatique (y compris Stockfish et Deep Blue) en près de 4 heures.

Les programmes IA conventionnels (de jeux de plateau) sont hautement optimisés pour leur domaine et ne peuvent pas être généralisés à d'autres problèmes sans intervention humaine. Le programme AlphaZero, en revanche, peut atteindre une performance surhumaine dans plusieurs domaines difficiles. Sans connaissance préalable sauf les règles du jeu et en partant d'un jeu aléatoire, AlphaZero a atteint un niveau de jeu surhumain en 24 heures aux jeux d'échecs, de Shogi et de Go, et a battu le meilleur programme mondial dans chaque cas. Comment ont-ils fait et quels sont les résultats exacts ? Découvrons-le.

Méthodologie

En octobre 2017, DeepMind a annoncé que leur algorithme AlphaGo Zero a atteint une performance surhumaine en utilisant un réseau de neurones convolutif profond et entraîné uniquement par apprentissage par renforcement. Les ingénieurs ont utilisé la même approche pour construire un algorithme générique, appelé AlphaZero, qui remplace les augmentations spécifiques au domaine et les connaissances artisanales utilisées dans les algorithmes de jeu conventionnels par des réseaux de neurones profonds et un algorithme d'apprentissage par renforcement tabula rasa.

AlphaZero utilise un algorithme MCTS (Monte-Carlo Tree Search) à usage général plutôt que la recherche alpha-bêta. Il apprend les estimations de valeur et les probabilités de coup en jouant contre lui-même, puis utilise les informations apprises pour guider sa recherche.

Différences avec l'algorithme AlphaGo Zero

L'algorithme AlphaGo Zero estime et optimise la probabilité de gagner, en tenant compte des résultats binaires gain ou perte. AlphaZero, en revanche, estime et optimise le résultat attendu, en tenant compte des matchs nuls ou d'autres résultats potentiels.

Les règles du jeu de Go sont invariantes par réflexion et rotation. Ce fait est très bien utilisé dans AlphaGo et sa version avancée AlphaGo Zero de deux manières :

• Augmenter les données d'entraînement en créant 8 symétries pour chaque position.
• Transformer la position via une réflexion ou rotation sélectionnée aléatoirement avant d'être calculée par le réseau de neurones, dans l'algorithme MCTS, de sorte que le calcul soit moyenné sur différents biais.

Dans le cas des échecs et du shogi, les règles sont asymétriques, et on ne peut pas supposer de symétries en général. Dans AlphaZero, les données d'entraînement ne sont pas augmentées et la position du plateau n'est pas transformée pendant le MCTS.

AlphaGo Zero utilise le meilleur joueur des itérations précédentes pour générer des parties d'auto-jeu. Après la completion de chaque itération, la performance du nouveau joueur est évaluée contre le meilleur joueur. S'il gagne avec une marge de 55 %, le meilleur joueur est remplacé et les parties d'auto-jeu sont générées par le nouveau joueur. Cependant, AlphaZero maintient un unique réseau de neurones (mis à jour continuellement) plutôt que de faire une pause jusqu'à la fin d'une itération.

Optimisation et entraînement d'AlphaZero

AlphaZero utilise des hyper-paramètres pour tous les jeux sans aucune optimisation spécifique au jeu. Afin d'assurer l'exploration, un facteur de bruit est intégré, qui est proportionnellement mis à l'échelle au nombre de coups légitimes pour ce type de jeu.

Comme AlphaGo Zero, l'état du plateau est encodé par des plans spatiaux et les actions sont encodées soit par des plans spatiaux, soit par un vecteur plat, selon les règles de base de chaque jeu.

Les développeurs ont appliqué AlphaZero aux échecs, au shogi et au Go. La même architecture de réseau, hyper-paramètres et réglages ont été utilisés pour les 3 jeux. Une instance individuelle de l'algorithme est entraînée pour chaque jeu. En partant de paramètres initialisés aléatoirement, l'entraînement a été conduit pendant 700 000 étapes, en utilisant 5 000 unités de traitement tensoriel (TPU) de première génération pour générer des parties d'auto-jeu et 64 TPU de deuxième génération pour entraîner les réseaux de neurones.

Référence : arxiv.org

Résultats

Comme on peut le voir dans la figure, AlphaZero a surpassé Stockfish après 300 000 étapes (après 4 heures) aux échecs ; il a surpassé Elmo en 110 000 étapes (en 2 heures) ; et il a surpassé AlphaGo Lee en 165 000 étapes (après 8 heures).

Les instances entièrement entraînées (entraînées pendant 3 jours) d'AlphaZero ont été testées contre AlphaGo Zero, Elmo et Stockfish, jouant 100 matchs à la cadence de 1 minute par coup. Les résultats étaient assez impressionnants (mentionnés dans le tableau ci-dessous).

AlphaGo Zero et AlphaZero ont utilisé une seule machine avec 4 unités de traitement tensoriel, Elmo et Stockfish ont performé au mieux en utilisant 64 threads et 1 Go de taille de hash. AlphaZero les a tous battus, perdant 8 parties contre Elmo et aucune contre Stockfish.

Les développeurs de Google ont également examiné la performance de la recherche MCTS dans AlphaZero. Elle recherche 40 000 positions par seconde au shogi et 80 000 aux échecs, comparé à 35 000 000 pour Elmo et 70 000 000 pour Stockfish. AlphaZero utilise son réseau de neurones profond pour se concentrer plus sélectivement sur les options les plus prometteuses, on peut dire une approche plus humaine.

À lire : 15 meilleurs moteurs d'échecs basés sur leurs classements

Bien qu'AlphaZero soit encore à ses débuts, il constitue une étape importante vers son objectif. Si des approches similaires peuvent être appliquées à d'autres problèmes structurés, comme le repliement des protéines, la découverte de nouveaux matériaux ou la réduction de la consommation d'énergie, les résultats ont le potentiel d'impacter positivement notre avenir.