Masterring Stratego, le jeu classique d’informations imparfaites

Deepnash apprend à jouer à Stratego à partir de zéro en combinant la théorie des jeux et une RL Deep sans modèle

Les systèmes d’intelligence artificielle (IA) de jeu ont progressé vers une nouvelle frontière. Stratego, le jeu de société classique plus complexe que les échecs et les go, et plus artisanal que le poker, a maintenant été maîtrisé. Publié dans Sciencenous présentons Deepnashun agent d’IA qui a appris le jeu de zéro à un niveau expert humain en jouant contre lui-même.

Deepnash utilise une nouvelle approche, basée sur la théorie des jeux et l’apprentissage en renforcement profond sans modèle. Son style de jeu converge vers un équilibre Nash, ce qui signifie que son jeu est très difficile pour un adversaire à exploiter. Si dur, en fait, que Deepnash a atteint un classement de tous les temps parmi les trois premiers parmi les experts humains sur la plus grande plate-forme de stratégie en ligne du monde, Gravon.

Les jeux de société ont toujours été une mesure du progrès dans le domaine de l’IA, nous 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 à Go, Stratego est un jeu d’informations imparfaites: les joueurs ne peuvent pas observer directement l’identité des pièces de leur adversaire.

Cette complexité a signifié que d’autres systèmes Stratego basés sur l’IA ont eu du mal à aller au-delà du niveau amateur. Cela signifie également qu’une technique d’IA très réussie appelée «Recherche d’arbre de jeu», précédemment utilisée pour maîtriser de nombreux jeux d’informations parfaites, n’est pas suffisamment évolutive pour Stratego. Pour cette raison, Deepnash va bien au-delà de la recherche d’arbres de jeu.

La valeur de Mastering Stratego va au-delà des jeux. Dans la poursuite de notre mission de résolution de l’intelligence pour faire progresser la science et profiter à l’humanité, nous devons construire des systèmes d’IA avancés qui peuvent fonctionner dans des situations complexes et réelles avec des informations limitées d’autres agents et personnes. Notre article montre à quel point 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 au tour par tour et capture-the-drôle. C’est un jeu de bluff et de tactiques, de rassemblement 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 la même ampleur pour son adversaire.

Stratego est difficile pour l’IA, en partie, car c’est un jeu d’informations imparfaites. Les deux joueurs commencent par organiser leurs 40 pièces de jeu dans la formation de départ qu’ils aiment, initialement cachée les uns des autres au début du jeu. Étant donné que les deux joueurs n’ont pas accès aux mêmes connaissances, ils doivent équilibrer tous les résultats possibles lorsqu’ils prennent une décision – offrant une référence difficile pour étudier les interactions stratégiques. Les types de pièces et leurs classements sont illustrés ci-dessous.

Les informations sont dures gagnées dans Stratego. L’identité de la pièce d’un adversaire 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 des jeux d’informations parfaites telles que les échecs ou 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 des jeux d’information parfaits, tels que DeepMind Alphazerne sont pas facilement transférés à Stratego. La nécessité de prendre des décisions avec des informations imparfaites et le potentiel de bluff, rend Stratego plus semblable au Texas Hold’em Poker et nécessite une capacité humaine une fois notée par l’écrivain américain Jack London: «La vie n’est pas toujours une question de contenir de bonnes cartes, mais parfois, jouant bien une mauvaise main.»

Les techniques de l’IA qui fonctionnent si bien dans des jeux comme Texas Hold’em ne sont pas transférés à Stratego, cependant, en raison de la longueur du jeu – souvent des centaines de mouvements avant qu’un joueur ne gagne. Le raisonnement dans Stratego doit être effectué sur un grand nombre d’actions séquentielles sans aucune idée évidente de la façon dont chaque action contribue au résultat final.

Enfin, le nombre de jeux possibles (exprimés en «complexité des arbres de jeu») est hors du graphique par rapport aux échecs, Go et le poker, ce qui le rend incroyablement difficile à résoudre. C’est ce qui nous a excités à propos de Stratego, et pourquoi il a représenté un défi de plusieurs décennies à la communauté de l’IA.

À la recherche d’un équilibre

Deepnash utilise une nouvelle approche basée sur une combinaison de théorie des jeux et d’apprentissage en renforcement profond sans modèle. «Sans modèle» signifie que Deepnash n’essaie pas de modéliser explicitement l’état de jeu privé de son adversaire pendant le jeu. Dans les premiers stades du jeu en particulier, lorsque Deepnash en sait peu sur 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 fidèle des jeux basés sur l’IA – la recherche de Monte Carlo Tree. La recherche d’arbres a été un ingrédient clé de nombreuses réalisations historiques dans l’IA pour les jeux de société moins complexes et le poker.

Au lieu de cela, Deepnash est alimenté par une nouvelle idée algorithmique théorique du jeu que nous appelons régularisé Nash Dynamics (R-NAD). Travaillant à une échelle inégal notre papier).

Le comportement de jeu qui se traduit par un équilibre Nash est inexplicable au fil du temps. Si une personne ou une machine jouait à Stratego parfaitement inexploité, le pire taux de victoire qu’ils pourraient atteindre serait de 50%, et seulement s’ils sont confrontés à un adversaire tout aussi parfait.

Dans les matchs contre les meilleurs robots Stratego – dont plusieurs gagnants du Championnat du monde Computer Stratego – le taux de victoire de Deepnash a dépassé 97% et était fréquemment à 100%. Contre les meilleurs joueurs humains experts sur la plate-forme des jeux Gravon, Deepnash a obtenu un taux de victoire de 84%, ce qui lui a obtenu un classement parmi les trois premiers.

Attendez-vous à l’inattendu

Pour obtenir ces résultats, Deepnash a démontré des comportements remarquables à la fois au cours de sa phase initiale de déploiement de la pièce et dans la phase de gameplay. Pour devenir difficile à exploiter, Deepnash a développé une stratégie imprévisible. Cela signifie que la création de déploiements initiaux variait suffisamment pour empêcher ses modèles de repérage de son adversaire sur une série de jeux. Et pendant la phase de jeu, Deepnash a randomé des actions apparemment équivalentes pour empêcher les tendances exploitables.

Les joueurs de Stratego s’efforcent d’être imprévisibles, il est donc de la valeur de garder les informations cachées. Deepnash 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) au début du jeu et, par conséquent, a pu localiser les 10 (maréchal), 9 (général), un 8 et deux 7.

Ces efforts ont laissé Deepnash dans un désavantage important significatif; Il a perdu un 7 et un 8 tandis que son adversaire humain a conservé toutes leurs pièces classées 7 et plus. Néanmoins, ayant une solide Intel sur les meilleurs cuivres de son adversaire, Deepnash a évalué ses chances gagnantes à 70% – et il a gagné.

L’art du bluff

Comme dans le poker, un bon joueur de stratégie doit parfois représenter la force, même lorsqu’il est faible. Deepnash a appris une variété de telles 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. Cette tactique de Deepnash, risquant uniquement une pièce mineure, réussit à éliminer et à éliminer l’espion de son adversaire, une pièce critique.

Voir plus en regardant ces quatre vidéos de matchs complets joués par Deepnash contre des experts humains (anonymisés): Match 1, Match 2, Match 3, Match 4.

Directions futures

Alors que nous avons développé Deepnash pour le monde très défini de Stratego, notre nouvelle méthode R-NAD peut être directement appliquée aux autres jeux à somme nulle à deux joueurs d’informations à la fois parfaites ou imparfaites. R-NAD a le potentiel de généraliser bien au-delà des paramètres de jeu à deux joueurs pour résoudre les problèmes du monde réel à grande échelle, qui sont souvent caractérisés par des informations imparfaites et des espaces d’état astronomiques.

Nous espérons également que R-NAD peut aider à déverrouiller de nouvelles applications de l’IA dans des domaines qui comportent un grand nombre de participants humains ou d’IA avec différents objectifs qui pourraient ne pas avoir d’informations sur l’intention des autres ou ce qui se passe dans leur environnement, comme dans l’optimisation à grande échelle de la gestion du trafic pour réduire les temps de trajet des conducteurs et les émissions de véhicules associées.

En créant un système d’IA généralisable qui est robuste face à l’incertitude, nous espérons apporter davantage les capacités de résolution de problèmes de l’IA dans notre monde intrinsèquement imprévisible.

En savoir plus sur Deepnash en lisant Notre article en science.

Pour les chercheurs intéressés à essayer R-NAD ou à travailler avec notre méthode nouvellement proposée, nous avons open source Notre code.