Pour les IA, les jeux de société sont de formidables terrains d’apprentissage, ce qui leur a permis de battre les humains au jeu de Go, aux échecs, au poker, au backgammon… Stratego est l’un des jeux de société que l’IA n’a pas encore maîtrisé, des chercheurs de Deepmind AI présentent « DeepNash », un agent autonome formé avec un apprentissage par renforcement multi-agents sans modèle qui apprend à jouer à Stratego au niveau expert.
Depuis des années, la communauté de recherche en IA s’intéresse au jeu de société Stratego, créé en 1947, qui, depuis, a connu plusieurs versions. Ce jeu de stratégie et de bluff se joue à deux, chacun des joueurs tentant de prendre le drapeau de l’autre. Il est très complexe : si chaque joueur dispose de 40 pions de différentes valeurs, il ne sait pas où se trouve le drapeau de l’ennemi ni quelles sont les pièces en face de lui, donc ne connaît pas leur valeur. Le plateau de jeu comporte 100 cases, huit sont occupées par deux lacs infranchissables, les joueurs commencent le jeu en disposant leurs pions sur les quatre premières lignes du plateau situées devant eux.(phase 1)
La seconde phase du jeu débute, les joueurs déplacent à tour de rôle des pièces, à l’exception du drapeau et des six bombes qui sont des pièces fixes. Lorsque deux pièces se rencontrent, leur valeur est révélée et la pièce la plus faible est retirée (ou les deux si elles ont la même force). Lorsque la pièce mobile la plus faible, le Spy, attaque le Maréchal, de valeur 10, il gagne cependant et le 10 est capturé.
Si on peut l’assimiler à un mix de poker et d’échecs, contrairement à ces derniers, les algorithmes d’apprentissage par renforcement (RL) n’ont pas répondu aux attentes des chercheurs en IA et n’ont pas vraiment relevé les deux défis principaux de ce jeu, à savoir les 10535 états potentiels dans l’arbre de jeu Stratego et les 1066 déploiements possibles au début du jeu. En effet, les méthodes d’IA existantes atteignent à peine un niveau de jeu amateur.
Deepnash
Développer des agents intelligents qui apprennent de bout en bout à prendre des décisions optimales sous des informations imparfaites dans Stratego, à partir de zéro, sans données de démonstration, est donc le défi que se sont lancés les chercheurs de Deepmind AI. Ils ont choisi pour cela la version la plus complexe du jeu : Stratego Classique et présentent Deepnash, un agent autonome qui a battu les meilleures méthodes existantes et a atteint le niveau de jeu expert.
DeepNash repose sur un algorithme RL basé sur des principes et sans modèle, appelé dynamique de Nash régularisée (R-NaD), combiné à une architecture de réseau neuronal profond pour converger vers un équilibre epsilon-Nash. (La notion de dynamique de Nash fait référence au mathématicien John Forbes Nash dans la théorie des jeux).
Un équilibre de Nash garantit que l’agent fonctionnera bien, quelque soit l’adversaire. Il est souvent utilisé pour jouer contre les humains dans des jeux à somme nulle à deux joueurs.
L’algorithme Regularized Nash Dynamics (R-NaD), reposant sur le concept de régularisation, implémenté via le réseau de neurones profond, converge donc vers un équilibre de Nash approximatif, au lieu de “cycler” autour de lui, et modifie directement la dynamique d’apprentissage multi-agent sous-jacente. (figure 1b)
L’évaluation de Deepnash
L’équipe a ensuite évalué les performances de Deepnash sur la plateforme Gravon, un serveur de jeux en ligne bien connu des joueurs de Stratego où il a été mesuré par rapport à huit bots IA. Le tableau ci-dessous démontre son efficacité puisqu’il a remporté 97% des challenges :
Il a également été testé durant deux semaines en avril dernier contre les meilleurs joueurs humains et a remporté 84% des 50 parties, ce qui le positionne à la 3ème place du défi Classic Stratego 2022. Deepnash a ainsi démontré ses capacités pour le déploiement, le bluff et les compromis.
DeepNash pourrait débloquer d’autres applications RL pour des problèmes multi-agents du monde réel, caractérisés par des informations imparfaites, qui sont actuellement hors de portée des méthodes d’IA de pointe.
Sources de l’article :
ArXiv : “Mastering the Game of Stratego with Model-Free Multiagent Reinforcement Learning” (arXiv:2206.15378)
Julien Perolat , Bart de Vylder , Daniel Hennes , Eugene Tarassov , Florian Strub , Vincent de Boer , Paul Muller , Jerome T. Connor , Neil Burch , Thomas Anthony , Stephen McAleer , Romuald Elie , Sarah H. Cen , Zhe Wang , Audrunas Gruslys , Aleksandra Malysheva , Mina Khan , Sherjil Ozair , Finbarr Timbers , Toby Pohlen , Tom Eccles , Mark Rowland , Marc Lanctot , Jean-Baptiste Lespiau , Bilal Piot , Shayegan Omidshafiei , Edward Lockhart, Laurent Sifre , Nathalie Beauguerlange , Rémi Munos , David Silver , Satinder Singh , Demis Hassabis , Karl Tuyls.
