L'IA déteste l'incertitude. Pourtant, pour naviguer dans notre monde imprévisible, il doit apprendre à faire des choix avec des informations imparfaites, comme nous le faisons chaque jour.
DeepMind juste a pris un coup à résoudre cette énigme. L'astuce consistait à intégrer la théorie des jeux dans une stratégie algorithmique vaguement basée sur le cerveau humain appelée apprentissage par renforcement profond. Le résultat, DeepNash, a renversé des experts humains dans un jeu de société hautement stratégique appelé Stratego. Jeu notoirement difficile pour l'IA, Stratego nécessite de multiples forces d'esprit humain : réflexion à long terme, bluff et stratégie, le tout sans connaître les pièces de votre adversaire sur le plateau.
"Contrairement aux échecs et au go, Stratego est un jeu d'informations imparfaites : les joueurs ne peuvent pas observer directement l'identité des pièces de leur adversaire", DeepMind écrit dans un article de blog. Avec DeepNash, "les systèmes d'intelligence artificielle (IA) de jeu ont franchi une nouvelle frontière".
Ce n'est pas que du plaisir et des jeux. Les systèmes d'IA qui peuvent facilement manœuvrer le caractère aléatoire de notre monde et ajuster leur "comportement" en conséquence pourraient un jour gérer des problèmes du monde réel avec des informations limitées, comme l'optimisation du flux de trafic pour réduire le temps de trajet et (espérons-le) éteindre la rage au volant en conduisant soi-même les voitures deviennent de plus en plus présentes.
"Si vous fabriquez une voiture autonome, vous ne voulez pas supposer que tous les autres conducteurs sur la route sont parfaitement rationnels et vont se comporter de manière optimale", a affirmé Valérie Plante. Dr Noam Brown de Meta AI, qui n'a pas participé à la recherche.
Le triomphe de DeepNash survient dans la foulée d'une autre avancée de l'IA ce mois-ci, où un algorithme appris à jouer à Diplomacy— un jeu qui nécessite négociation et coopération pour gagner. Au fur et à mesure que l'IA acquiert un raisonnement plus flexible, devient plus généralisée et apprend à naviguer dans les situations sociales, elle peut également donner un aperçu des processus neuronaux et de la cognition de notre propre cerveau.
Rencontrez Stratego
En termes de complexité, Stratego est une bête complètement différente par rapport aux échecs, au Go ou au poker, tous des jeux que l'IA a déjà maîtrisés.
Le jeu consiste essentiellement à capturer le drapeau. Chaque côté a 40 pièces qu'ils peuvent placer à n'importe quelle position sur le plateau. Chaque pièce a un nom et un rang numérique différents, tels que "maréchal", "général", "éclaireur" ou "espion". Les pièces de rang supérieur peuvent capturer les pièces de rang inférieur. Le but est d'éliminer l'opposition et de capturer son drapeau.
Stratego est particulièrement difficile pour l'IA car les joueurs ne peuvent pas voir l'emplacement des pièces de leurs adversaires, à la fois lors de la configuration initiale et tout au long du jeu. Contrairement aux échecs ou au Go, dans lequel chaque pièce et mouvement est en vue, Stratego est un jeu avec des informations limitées. Les joueurs doivent "équilibrer tous les résultats possibles" chaque fois qu'ils prennent une décision, ont expliqué les auteurs.
Ce niveau d'incertitude est en partie la raison pour laquelle Stratego a bloqué l'IA pendant des siècles. Même les algorithmes de jeu les plus réussis, tels que AlphaGo et AlphaZero, s'appuyer sur des informations complètes. Stratego, en revanche, a une touche de Texas Holdem, un jeu de poker que DeepMind a déjà conquis grâce à un algorithme. Mais cette stratégie a échoué pour Stratego, en grande partie à cause de la durée du jeu, qui, contrairement au poker, comprend normalement des centaines de coups.
Le nombre de jeux potentiels est époustouflant. Les échecs ont une position de départ. Stratego a plus de 1066 positions de départ possibles - bien plus que toutes les étoiles de l'univers. L'arbre de jeu de Stratego, la somme de tous les mouvements potentiels dans le jeu, totalise un nombre stupéfiant de 10535.
"La simple complexité du nombre de résultats possibles dans Stratego signifie que les algorithmes qui fonctionnent bien sur les jeux à information parfaite, et même ceux qui fonctionnent pour le poker, ne fonctionnent pas", a affirmé Valérie Plante. auteur de l'étude, le Dr Julien Perolat de DeepMind. Le défi est «ce qui nous a excités», a-t-il déclaré.
un bel esprit
La complexité de Stratego signifie que la stratégie habituelle de recherche de mouvements de jeu est hors de question. Surnommée la recherche d'arbres de Monte Carlo, une "approche fidèle du jeu basé sur l'IA", la technique trace des itinéraires potentiels - comme des branches sur un arbre - qui pourraient aboutir à la victoire.
Au lieu de cela, la touche magique pour DeepNash est venue du mathématicien John Nash, décrit dans le film un bel esprit. Pionnier de la théorie des jeux, Nash a remporté le prix Nobel pour ses travaux sur la équilibre de Nash. En termes simples, dans chaque jeu, les joueurs peuvent puiser dans un ensemble de stratégies suivies par tout le monde, de sorte qu'aucun joueur ne gagne quoi que ce soit en changeant sa propre stratégie. Dans Statego, cela entraîne un jeu à somme nulle : tout gain réalisé par un joueur entraîne une perte pour son adversaire.
En raison de la complexité de Stratego, DeepNash a adopté une approche sans modèle pour son algorithme. Ici, l'IA ne cherche pas à modéliser précisément le comportement de son adversaire. Comme un bébé, il a une ardoise vierge, en quelque sorte, à apprendre. Cette configuration est particulièrement utile dans les premières étapes du jeu, "lorsque DeepNash en sait peu sur les pièces de son adversaire", rendant les prédictions "difficiles, voire impossibles", ont déclaré les auteurs.
L'équipe a ensuite utilisé l'apprentissage par renforcement profond pour alimenter DeepNash, dans le but de trouver l'équilibre de Nash du jeu. C'est un match parfait : l'apprentissage par renforcement aide à décider du meilleur coup suivant à chaque étape du jeu, tandis que DeepNash fournit une stratégie d'apprentissage globale. Pour évaluer le système, l'équipe a également conçu un "tuteur" utilisant les connaissances du jeu pour filtrer les erreurs évidentes qui n'auraient probablement pas de sens dans le monde réel.
Practice makes perfect
Comme première étape d'apprentissage, DeepNash a joué contre lui-même dans 5.5 milliards de parties, une approche populaire dans la formation à l'IA appelée self-play.
Lorsqu'un côté gagne, l'IA est récompensée et les paramètres actuels de son réseau de neurones artificiels sont renforcés. L'autre côté - la même IA - reçoit une pénalité pour atténuer la force de son réseau neuronal. C'est comme répéter un discours devant un miroir. Au fil du temps, vous comprenez les erreurs et vous améliorez vos performances. Dans le cas de DeepNash, il dérive vers un équilibre de Nash pour un meilleur gameplay.
Qu'en est-il des performances réelles ?
L'équipe a testé l'algorithme contre d'autres robots Stratego d'élite, dont certains ont remporté le championnat du monde Computer Stratego. DeepNash a écrasé ses adversaires avec un taux de victoire d'environ 97 %. Lorsqu'il s'est déchaîné contre Gravon, une plate-forme en ligne pour les joueurs humains, DeepNash a battu ses adversaires humains. Après plus de deux semaines de matchs contre les joueurs de Gravon en avril de cette année, DeepNash s'est hissé à la troisième place de tous les matchs classés depuis 2002.
Cela montre que l'amorçage des données de jeu humain vers l'IA n'est pas nécessaire pour que DeepNash atteigne des performances de niveau humain et les batte.
L'IA a également présenté un comportement intrigant lors de la configuration initiale et pendant le jeu. Par exemple, plutôt que de s'installer sur une position de départ "optimisée" particulière, DeepNash a constamment déplacé les pièces pour empêcher son adversaire de repérer des modèles au fil du temps. Pendant le jeu, l'IA a rebondi entre des mouvements apparemment insensés - comme sacrifier des pièces de haut rang - pour localiser les pièces de rang encore plus élevé de l'adversaire lors de la contre-attaque.
DeepNash peut aussi bluffer. Dans une partie, l'IA a déplacé une pièce de rang inférieur comme s'il s'agissait d'une pièce de haut rang, attirant l'adversaire humain pour qu'il poursuive la pièce avec son colonel de haut rang. L'IA a sacrifié le pion, mais à son tour, a attiré la précieuse pièce d'espionnage de l'adversaire dans une embuscade.
Bien que DeepNash ait été développé pour Stratego, il est généralisable au monde réel. La méthode de base peut potentiellement demander à l'IA de mieux aborder notre avenir imprévisible en utilisant des informations limitées, du contrôle des foules et du trafic à l'analyse des turbulences du marché.
"En créant un système d'IA généralisable et robuste face à l'incertitude, nous espérons amener les capacités de résolution de problèmes de l'IA plus loin dans notre monde intrinsèquement imprévisible", a déclaré l'équipe.
Crédit image: Derek Bruff / Flickr
