Recherche
DeepNash apprend à jouer à Stratego à partir de zéro en combinant la théorie des jeux et le Deep RL sans modèle
Les systèmes d’intelligence artificielle (IA) de jeu ont franchi une nouvelle frontière. Stratego, le jeu de société classique, plus complexe que les échecs et le Go, et plus astucieux que le poker, est désormais maîtrisé. Publié dans Sciencenous présentons DeepNashun agent IA qui a appris le jeu de zéro jusqu'à un niveau d'expert humain en jouant contre lui-même.
DeepNash utilise une nouvelle approche, basée sur la théorie des jeux et l'apprentissage par renforcement profond sans modèle. Son style de jeu converge vers un équilibre de Nash, ce qui signifie que son jeu est très difficile à exploiter pour un adversaire. Si difficile, en fait, que DeepNash a atteint le top trois de tous les temps parmi les experts humains sur la plus grande plateforme Stratego en ligne au monde, Gravon.
Les jeux de société ont toujours été une mesure de progrès dans le domaine de l’IA, permettant d’étudier comment les humains et les machines développent et exécutent des stratégies dans un environnement contrôlé. Contrairement aux échecs et au Go, Stratego est un jeu d'information imparfaite : les joueurs ne peuvent pas observer directement l'identité des pièces de leur adversaire.
Cette complexité signifie que d’autres systèmes Stratego basés sur l’IA ont eu du mal à dépasser le niveau amateur. Cela signifie également qu’une technique d’IA très réussie appelée « recherche dans l’arbre de jeu », utilisée auparavant pour maîtriser de nombreux jeux à information parfaite, n’est pas suffisamment évolutive pour Stratego. Pour cette raison, DeepNash va bien au-delà de la recherche dans l’arbre du jeu.
La valeur de la maîtrise de Stratego va au-delà du jeu. Dans la poursuite de notre mission consistant à résoudre le problème du renseignement pour faire progresser la science et bénéficier à l’humanité, nous devons construire des systèmes d’IA avancés capables de fonctionner dans des situations complexes et réelles avec des informations limitées sur d’autres agents et personnes. Notre article montre comment DeepNash peut être appliqué dans des situations d’incertitude et équilibrer avec succès les résultats pour aider à résoudre des problèmes complexes.
Apprendre à connaître Stratego
Stratego est un jeu de capture de drapeau au tour par tour. C'est un jeu de bluff et de tactique, de collecte d'informations et de manœuvres subtiles. Et c'est un jeu à somme nulle, donc tout gain d'un joueur représente une perte de même ampleur pour son adversaire.
Stratego est un défi pour l'IA, en partie parce qu'il s'agit d'un jeu d'informations imparfaites. Les deux joueurs commencent par disposer leurs 40 pièces de jeu dans la formation de départ de leur choix, initialement cachées les unes des autres au début de la partie. Étant donné que les deux acteurs n'ont pas accès aux mêmes connaissances, ils doivent équilibrer tous les résultats possibles lorsqu'ils prennent une décision, ce qui constitue une référence difficile pour l'étude des interactions stratégiques. Les types de pièces et leurs classements sont indiqués ci-dessous.
Gauche: Le classement des pièces. Dans les batailles, les pièces de rang supérieur gagnent, sauf que le 10 (maréchal) perd lorsqu'il est attaqué par un espion, et les bombes gagnent toujours sauf lorsqu'elles sont capturées par un mineur.
Milieu: Une possible formation de départ. Remarquez comment le drapeau est rangé en toute sécurité à l'arrière, flanqué de bombes protectrices. Les deux zones bleu pâle sont des « lacs » et on n’y entre jamais.
Droite: Un jeu en jeu, montrant Blue's Spy capturant le 10 de Red.
L’information est durement gagnée dans Stratego. L'identité d'une pièce adverse n'est généralement révélée que lorsqu'elle rencontre l'autre joueur sur le champ de bataille. Cela contraste fortement avec les jeux d'information parfaite tels que les échecs ou le Go, dans lesquels l'emplacement et l'identité de chaque pièce sont connus des deux joueurs.
Les approches d'apprentissage automatique qui fonctionnent si bien sur les jeux d'information parfaits, tels que DeepMind's AlphaZéro, ne sont pas facilement transférables vers Stratego. La nécessité de prendre des décisions avec des informations imparfaites et la possibilité de bluffer rapproche davantage Stratego du poker Texas hold'em et nécessite une capacité humaine, un jour notée par l'écrivain américain Jack London : « La vie n'est pas toujours une question de tenir de bonnes cartes, mais parfois, je joue bien une mauvaise main.
Les techniques d'IA qui fonctionnent si bien dans des jeux comme le Texas hold'em ne sont cependant pas transférées à Stratego, en raison de la longueur du jeu – souvent des centaines de coups avant qu'un joueur ne gagne. Le raisonnement dans Stratego doit être effectué sur un grand nombre d’actions séquentielles sans aperçu évident de la manière dont chaque action contribue au résultat final.
Enfin, le nombre d’états de jeu possibles (exprimé par la « complexité de l’arbre du jeu ») est hors du commun par rapport aux échecs, au Go et au poker, ce qui rend leur résolution incroyablement difficile. C’est ce qui nous a enthousiasmés à propos de Stratego et pourquoi il représente un défi depuis des décennies pour la communauté de l’IA.
L'ampleur des différences entre les échecs, le poker, le Go et le Stratego.
À la recherche d'un équilibre
DeepNash utilise une nouvelle approche basée sur une combinaison de théorie des jeux et d'apprentissage par renforcement profond sans modèle. « Sans modèle » signifie que DeepNash ne tente pas de modéliser explicitement l'état de jeu privé de son adversaire pendant la partie. En particulier dans les premiers stades du jeu, lorsque DeepNash connaît peu les pièces de son adversaire, une telle modélisation serait inefficace, voire impossible.
Et parce que la complexité de l’arbre de jeu de Stratego est si vaste, DeepNash ne peut pas utiliser une approche solide du jeu basé sur l’IA – la recherche arborescente de Monte Carlo. La recherche arborescente a été un ingrédient clé de nombreuses réalisations marquantes de l’IA pour les jeux de société moins complexes et le poker.
Au lieu de cela, DeepNash s'appuie sur une nouvelle idée algorithmique de la théorie des jeux que nous appelons Regularized Nash Dynamics (R-NaD). Travaillant à une échelle sans précédent, R-NaD oriente le comportement d'apprentissage de DeepNash vers ce que l'on appelle un équilibre de Nash (plongez dans les détails techniques dans notre journal).
Le comportement de jeu qui aboutit à un équilibre de Nash est inexploitable au fil du temps. Si une personne ou une machine jouait à Stratego parfaitement inexploitable, le pire taux de victoire qu'elle pourrait atteindre serait de 50 %, et seulement si elle faisait face à un adversaire tout aussi parfait.
Lors des matchs contre les meilleurs robots Stratego – dont plusieurs vainqueurs du championnat du monde Computer Stratego – le taux de victoire de DeepNash dépassait 97 %, et était souvent de 100 %. Face aux meilleurs joueurs humains experts de la plateforme de jeux Gravon, DeepNash a atteint un taux de victoire de 84 %, ce qui lui a valu l'un des trois premiers classements de tous les temps.
Attendez-vous à l'inattendu
Pour atteindre ces résultats, DeepNash a démontré des comportements remarquables tant lors de sa phase initiale de déploiement de pièces que lors de la phase de gameplay. Pour devenir difficile à exploiter, DeepNash a développé une stratégie imprévisible. Cela signifie créer des déploiements initiaux suffisamment variés pour empêcher son adversaire de repérer des schémas sur une série de parties. Et pendant la phase de jeu, DeepNash randomise entre des actions apparemment équivalentes pour éviter les tendances exploitables.
Les joueurs de Stratego s'efforcent d'être imprévisibles, il est donc utile de garder les informations cachées. DeepNash démontre comment il valorise les informations de manière assez frappante. Dans l'exemple ci-dessous, contre un joueur humain, DeepNash (bleu) a sacrifié, entre autres pièces, un 7 (Majeur) et un 8 (Colonel) en début de partie et a ainsi pu localiser le 10 (Maréchal) de l'adversaire, 9 (Général), un 8 et deux 7.
Dans cette situation de début de partie, DeepNash (bleu) a déjà localisé bon nombre des pièces les plus puissantes de son adversaire, tout en gardant secrètes ses propres pièces clés.
Ces efforts ont laissé DeepNash dans une situation matériellement désavantageuse ; il a perdu un 7 et un 8 tandis que son adversaire humain a conservé toutes ses pièces classées 7 et plus. Néanmoins, disposant d'informations solides sur les hauts gradés de son adversaire, DeepNash a évalué ses chances de victoire à 70 % – et il a gagné.
L'art du bluff
Comme au poker, un bon joueur de Stratego doit parfois représenter la force, même lorsqu'il est faible. DeepNash a appris diverses tactiques de bluff. Dans l'exemple ci-dessous, DeepNash utilise un 2 (un Scout faible, inconnu de son adversaire) comme s'il s'agissait d'une pièce de haut rang, poursuivant le 8 connu de son adversaire. L'adversaire humain décide que le poursuivant est très probablement un 10, et tente donc pour l'attirer dans une embuscade tendue par leur espion. Cette tactique de DeepNash, ne risquant qu'une pièce mineure, réussit à débusquer et à éliminer le Spy de son adversaire, une pièce critique.
Le joueur humain (rouge) est convaincu que la pièce inconnue qui poursuit son 8 doit être le 10 de DeepNash (note : DeepNash avait déjà perdu son seul 9).
Pour en savoir plus, regardez ces quatre vidéos de jeux complets joués par DeepNash contre des experts humains (anonymisés) : Jeu 1, Jeu 2, Jeu 3, Jeu 4.
Le niveau de jeu de DeepNash m'a surpris. Je n'avais jamais entendu parler d'un joueur Stratego artificiel qui se rapprochait du niveau nécessaire pour gagner un match contre un joueur humain expérimenté. Mais après avoir moi-même joué contre DeepNash, je n'ai pas été surpris par le classement dans le top 3 qu'il a ensuite atteint sur la plateforme Gravon. Je pense qu'il ferait très bien l'affaire s'il était autorisé à participer aux Championnats du monde humains.
Vincent de Boer, co-auteur de l'article et ancien champion du monde Stratego
Directions futures
Alors que nous avons développé DeepNash pour le monde hautement défini de Stratego, notre nouvelle méthode R-NaD peut être directement appliquée à d'autres jeux à somme nulle à deux joueurs d'informations parfaites ou imparfaites. R-NaD a le potentiel de se généraliser bien au-delà des paramètres de jeu à deux joueurs pour résoudre des problèmes réels à grande échelle, souvent caractérisés par des informations imparfaites et des espaces d’états astronomiques.
Nous espérons également que R-NaD pourra aider à débloquer de nouvelles applications de l'IA dans des domaines qui mettent en vedette un grand nombre de participants humains ou IA ayant des objectifs différents et qui pourraient ne pas avoir d'informations sur les intentions des autres ou sur ce qui se passe dans leur environnement, comme dans le grand -optimisation à grande échelle de la gestion du trafic pour réduire les temps de trajet des conducteurs et les émissions associées des véhicules.
En créant un système d'IA généralisable et robuste face à l'incertitude, nous espérons étendre les capacités de résolution de problèmes de l'IA dans notre monde intrinsèquement imprévisible.
Apprenez-en plus sur DeepNash en lisant notre article dans Science.
Pour les chercheurs intéressés à essayer R-NaD ou à travailler avec notre nouvelle méthode proposée, nous avons une version open source notre code.
