DeepMind est de retour sur la Science ! L'IA "Wall Breaker" joue des tours pour vaincre les maîtres humains

Récemment, l'agent IA de DeepMind, DeepNash, a vaincu avec succès des joueurs humains professionnels dans Stratego et s'est classé avec succès parmi les 3 meilleurs.

Le 1er décembre, l'article a été officiellement publié dans Science.

Adresse papier : http://www.science.org/doi/10.1126/science.add4679

Utilisez cette IA pour rendre hommage à John Nash

À l'ère d'aujourd'hui, l'IA de jeu est devenue un Une toute nouvelle étape.

Dans le passé, de nombreux scientifiques utilisaient les échecs et le Go pour entraîner l'IA, mais DeepMind a cette fois utilisé Stratego, qui est un jeu de société classique plus complexe que les échecs et le Go, et plus intelligent que le poker.

Et cet agent IA nommé DeepNash a appris Stratego à partir de zéro en jouant contre lui-même.

Maintenant, DeepNash se classe parmi les trois meilleurs experts humains de l’histoire sur Gravon, la plus grande plateforme Stratego en ligne au monde.

DeepNash adopte une toute nouvelle méthode de jeu, théoriquement basée sur la théorie des jeux et l'apprentissage par renforcement profond sans modèle.

On voit que ce nom est également destiné à rendre hommage au célèbre mathématicien américain John Nash.

L'équilibre de Nash qu'il a proposé, également connu sous le nom d'équilibre des jeux non coopératifs, est une partie très importante de la théorie des jeux.

Quel est le secret de Stratego ?

Les jeux de société ont toujours été la norme pour mesurer les progrès de l'IA car ils nous permettent d'étudier comment les humains et les machines formulent et exécutent des stratégies dans des environnements contrôlés.

Et quel est le secret de ce Stratego ?

La différence avec les échecs et le Go est que Stratego est un jeu d'information incomplet : les joueurs ne peuvent pas observer directement l'identité des pièces de l'adversaire.

En raison de cette complexité, le système Stratego basé sur l'IA est souvent au niveau amateur, peu importe à quel point il travaille, il est impossible d'atteindre le niveau « expert ».

Dans le passé, la raison pour laquelle diverses IA ont remporté de grandes victoires dans les jeux et ont complètement submergé les humains est due à une technologie d'IA appelée "Game Tree Search".

Bien que "Game Tree Search" puisse tuer toutes sortes de jeux avec des informations complètes, il est un peu impuissant pour des jeux comme Stratego car il n'est pas assez évolutif.

À ce stade, DeepNash a complètement détruit la recherche dans l'arbre de jeu.

En fait, DeepNash a maîtrisé la valeur de Stratego, qui a largement dépassé le jeu lui-même.

Le monde réel est souvent très complexe et les informations sont limitées. Les systèmes d’IA véritablement avancés sont confrontés à des environnements comme Stratego.

DeepNash nous a montré avec succès comment l'IA peut réussir à équilibrer les résultats et à résoudre des problèmes complexes dans un contexte d'incertitude.

Comment jouer à Stratego

Stratego est un jeu de capture du drapeau au tour par tour. Dans le jeu, les joueurs doivent bluffer, utiliser des tactiques de détour, collecter des informations et opérer avec habileté.

C'est un jeu à somme nulle, donc tout gain pour un joueur représente une perte égale pour l'adversaire.

Cela ressemble à nos échecs militaires.

La différence entre Stratego et les échecs militaires est qu'il comporte un plus grand nombre de pièces d'échecs, plus de grades militaires, une conception d'échiquier plus simple et aucun chemin de fer, camp ni arbitre.

Lorsque les deux côtés mettent en place une formation, toutes les pièces d'échecs doivent être verticales et ne peuvent pas être vues de l'autre côté.

Une fois la formation terminée, le côté rouge bouge en premier, puis à tour de rôle pour déplacer une pièce.

Parmi les pièces d'échecs, le drapeau militaire et les mines ne peuvent pas être déplacés. Les éclaireurs peuvent déplacer n'importe quelle case horizontalement et verticalement, mais ne peuvent pas traverser les pièces d'échecs. Les autres pièces d'échecs ne peuvent se déplacer que d'une case horizontalement ou verticalement.

Lorsque les pièces d'échecs des deux côtés sont dans la même grille, elles sont découvertes ensemble et jugées selon leur taille. La pièce d'échecs gagnante est remise dans sa position d'origine, tournée vers l'arrière, et la pièce d'échecs perdante est retirée.

La méthode de victoire de Stratego est similaire aux échecs militaires chinois. La victoire est obtenue en capturant le drapeau militaire de l'adversaire ou en détruisant toutes les pièces d'échecs en mouvement.

Pourquoi Stratego est-il si difficile pour l'IA ? Cela s’explique en partie par le fait qu’il s’agit d’un jeu d’informations imparfaites.

Deux joueurs de Stratego sont cachés l'un de l'autre lors de la disposition de 40 pièces dans la formation de départ.

Parce que les joueurs n'ont pas accès aux mêmes connaissances, ils doivent équilibrer tous les résultats possibles lorsqu'ils prennent une décision.

Types et classements des pièces d'échecs Stratego

Gauche : Classement des pièces d'échecs. Dans le jeu, la pièce avec le rang militaire le plus élevé gagne, à la seule exception du 10 (Maréchal) qui est attaqué par un espion ; la bombe gagne toujours, à la seule exception d'être capturée par un mineur.

Milieu : Formations de départ possibles. Le drapeau doit être rangé en toute sécurité à l'arrière, avec des bombes sur les côtés pour assurer sa protection. Les deux zones bleu clair sont des « lacs » et il ne faut jamais y pénétrer.

À droite : Une partie en cours, vous pouvez voir que l'espion de l'équipe bleue a capturé le maréchal de l'équipe rouge.

Ce jeu a laissé AlphaZero

Dans Stratego, les informations sont cachées.

Ce n'est que lors de la rencontre avec d'autres joueurs que l'identité des pièces adverses sera révélée.

La différence entre les échecs et le Go est qu'il s'agit de "jeux d'information parfaits" car les deux joueurs connaissent exactement l'emplacement et l'identité de chaque pièce d'échecs.

AlphaZero de DeepMind a toujours bien performé dans les jeux d’informations parfaites, mais dans Stratego, il était perplexe.

Aux échecs, AlphaZero a surpassé Stockfish après 4 heures ; au shogi, AlphaZero a dépassé Elmo après 2 heures et au Go, AlphaZero a surpassé AlphaGo, qui a battu Lee Sedol après 30 heures 

Stratego ressemble plus à Texas Hold' ; em et nécessite des capacités semblables à celles des humains - les humains doivent prendre des décisions avec des informations incomplètes et doivent bluffer.

L'écrivain américain Jack London a souligné un jour : "Dans la vie, nous n'avons pas toujours de bonnes cartes, mais parfois nous pouvons bien jouer avec une mauvaise main

En fait, de nombreuses IA sont également très bonnes." jouer contre l'Allemagne. Mais lorsqu'ils ont affronté Stratego, ils étaient confus : le processus de ce jeu est trop long !

Pour gagner, les joueurs doivent effectuer des centaines de mouvements. Par conséquent, le raisonnement dans le jeu doit être basé sur un grand nombre d’actions continues. Dans ce processus, il est difficile de voir clairement comment chaque action affectera le résultat final.

La différence de taille entre les échecs, le poker, le Go et le Strateg

De plus, le nombre d'états de jeu possibles ("complexité de l'arbre du jeu") par rapport aux échecs, au Go et au Poker est hors du commun, c'est encore plus difficile à résoudre.

Et c'est pourquoi Stratego est si excitant : il représente un défi de plusieurs décennies dans la communauté de l'IA.

Stratego : les hauteurs à conquérir pour l'IA

Au fil des années, comment faire ressortir l'intelligence artificielle dans le jeu Stratego est devenu le centre d'intérêt des chercheurs en IA.

Il y a deux difficultés principales pour vaincre des joueurs humains dans ce jeu.

Tout d'abord, l'arbre de jeu de ce jeu comporte 10 535ème états de puissance, c'est-à-dire qu'il y a 10 535ème configurations de puissance possibles dans un jeu. En revanche, il n’y a que 10 à la puissance 360 ​​des dispositions possibles dans Go.

Deuxièmement, dans Stratego, l'intelligence artificielle doit raisonner sur la stratégie de déploiement de l'adversaire à plus de 10 puissance 66, alors que le poker n'a qu'un millier de paires de cartes possibles.

Par conséquent, il n'est pas facile de déchiffrer la structure compliquée de Stratego. Comment vaincre les joueurs humains de Stratego est un défi sans précédent auquel sont confrontés les chercheurs en IA.

Comment vaincre les autres IA ? S'appuyant sur l'arme principale de R-NaD

DeepNash a complètement surpassé les autres IA car elle adopte une nouvelle méthode basée sur une combinaison de théorie des jeux et d'apprentissage par renforcement profond sans modèle.

« Modelless » signifie que DeepNash n'essaie pas de simuler explicitement l'état de l'adversaire dans le jeu.

Surtout dans les premiers stades du jeu, lorsque DeepNash connaît peu les pièces de l'adversaire, cette modélisation, même si elle est réalisable, a une forte probabilité d'être invalide.

De plus, étant donné que l'arbre de jeu de Stratego est si complexe, DeepNash ne peut pas adopter l'arborescence de recherche de Monte Carlo utilisée par d'autres IA lors des jeux. Cette dernière est la clé des réalisations marquantes de l’IA dans les jeux de société moins complexes et le poker.

On constate que si la stratégie d'équilibre peut jouer un rôle dans un jeu d'information complet dans lequel les deux parties agissent à tour de rôle, elle est insuffisante dans un jeu d'information incomplet.

DeepNash adopte une nouvelle idée d'algorithme de théorie des jeux - la programmation dynamique Nash régularisée (Regularized Nash Dynamic, R-NaD).

Cet algorithme d'apprentissage par renforcement sans modèle est au cœur de DeepNash.

Il guide DeepNash et fait évoluer son comportement d'apprentissage dans le sens de l'équilibre de Nash.

DeepNash combine R-NaD avec une architecture de réseau neuronal profond et converge vers l'équilibre de Nash.

Comprend trois étapes : transformation des récompenses, planification dynamique (dynamics) et itération de mise à jour (udate).

L'équipe de recherche a appliqué ces trois étapes à plusieurs reprises jusqu'à ce qu'une série de points fixes soient générés pour prouver que l'algorithme a convergé vers l'équilibre de Nash du jeu original.

Lorsque vous jouez contre les robots Stratego les plus puissants (dont plusieurs vainqueurs du championnat du monde de stratégie informatique), DeepNash a un taux de victoire de 97 % et atteint souvent un taux de victoire de 100 %.

Sur la plateforme de jeu Gravon, DeepNash a atteint un taux de victoire de 84 % contre les meilleurs joueurs humains, se classant parmi les trois meilleurs de l'histoire.

Bien sûr, l'équilibre de Nash ne peut pas être atteint grâce à la théorie des jeux sans restrictions dans le jeu, car le taux de victoire du joueur ne peut pas être garanti de cette manière.

La stratégie d'équilibre n'est pleinement applicable que dans les jeux avec des informations complètes. Dans les jeux avec des informations incomplètes, d'autres stratégies sont nécessaires pour gagner de manière inattendue.

Dans la formation initiale des troupes, DeepNash a adopté un gameplay extraordinaire. Afin de devenir difficile à exploiter, DeepNash a développé une stratégie imprévisible.

Cela signifie que le déploiement initial doit être suffisamment flexible pour empêcher l'adversaire de découvrir son propre schéma lors des séries de matchs suivantes.

En phase de jeu, DeepNash tentera également de randomiser autant que possible entre des actions apparemment identiques pour éviter de devenir exploitable.

Dans ce processus, cacher des informations est très important.

Cachez des informations et confondez votre adversaire

Dans des scénarios du monde réel, les gens utiliseront également d'autres moyens pour gagner, comme le bluff.

Comme le « père de la théorie des jeux » von Neumann l'a décrit : « La vraie vie est pleine de « bluff », de « petits trucs de tromperie » et de « deviner ce que les autres pensent que je vais faire »

Tao. Le « problème de suicide aux yeux rouges et aux yeux bleus » de Zhexuan : je sais, je sais qu'il sait, je sais qu'il sait qu'il sait...

À cet égard, DeepNash n'est pas moins généreux.

L'équipe de recherche a démontré les deux techniques de bluff de DeepNash : le bluff actif (bluff positif) et le bluff passif (bluff négatif).

Le bluff actif consiste à prétendre que ses pièces d'échecs sont de haut niveau pour intimider l'adversaire. En termes simples, c'est du « bluff ».

Dans cet exemple, DeepNash nous a appris une bonne leçon :

En jouant contre des joueurs humains (côté rouge), DeepNash (côté bleu) a sacrifié 7 (majeur) et 8 (colonel) au début de la partie. les pièces sont trouvées par le 10 (maréchal), le 9 (général), un 8 et deux 7 de l'adversaire.

À ce stade, DeepNash (côté bleu) a trouvé bon nombre des pièces les plus puissantes de l'adversaire, et en même temps, a caché ses propres pièces clés.

À première vue, DeepNash semble être clairement désavantagé : ses 7 et 8 sont éliminés, mais l'adversaire humain conserve toutes les pièces classées 7 et plus.

Cependant, DeepNash a eu le dernier mot : en s'appuyant sur les informations fiables qu'il avait détectées sur la haute direction de l'adversaire, il a estimé sa probabilité de victoire à 70 %.

En fin de compte, il a gagné.

L'art du bluff

Au poker, les bons joueurs joueront à la guerre psychologique pour intimider l'autre partie même lorsque nous sommes faibles.

DeepNash a également appris cette stratégie de bluff : le bluff négatif.

C'est ce que nous appelons souvent « faire semblant d'être un cochon et manger le tigre » : déguisez vos pièces d'échecs de haut niveau en pièces d'échecs de bas niveau, attendez que l'adversaire soit dupé, puis gagnez-les d'un seul coup.

Dans l'exemple ci-dessous, DeepNash utilise le 2 (très faiblement un éclaireur) pour chasser le 8 de l'adversaire qui révèle son identité.

L'adversaire humain en détermine que le poursuivant a probablement 10 ans et tente donc de l'attirer dans le cercle d'embuscade de l'espion.

En fin de compte, DeepNash a réussi à détruire la pièce d'échecs clé de l'adversaire avec la petite pièce d'échecs 2.

Le joueur humain (côté rouge) est convaincu que la pièce inconnue qui poursuit son 8 doit être le 10 de DeepNash (car à ce moment DeepNash a déjà perdu son seul 9

Ce qui suit est une comparaison entre DeepNash et (anonyme) experts humains) Cliquez sur ces quatre vidéos de jeu complètes, Jeu 1, Jeu 2, Jeu 3 et Jeu 4, et vous obtiendrez plus de surprises (l'adresse de la vidéo est répertoriée dans le matériel de référence)

Le niveau de jeu de DeepNash Je suis. surpris. Je n'ai jamais entendu parler d'un joueur Stratego artificiel qui soit même proche du niveau requis pour gagner contre des joueurs humains

Mais après avoir joué contre lui moi-même, je l'ai classé dans le top 3 sur Gravon. il est permis de participer au championnat du monde humain, il s'en sortira bien

——Vincent de Boer, co-auteur du journal, ancien champion du monde Stratego

L'avenir est incommensurable

On voit, ce roman R-NaD La méthode de DeepMind peut être directement appliquée à d'autres jeux à somme nulle à deux joueurs avec des informations parfaites ou imparfaites

R-NaD a le potentiel d'aller au-delà du jeu à deux joueurs et de résoudre des problèmes réels à grande échelle

Dans De plus, R-NaD devrait également débloquer de nouvelles applications de l'IA dans d'autres domaines avec des objectifs différents

Par exemple, dans l'optimisation à grande échelle de la gestion du trafic, où les gens ne connaissent pas les intentions des autres ou les informations environnementales, R-NaD est utile. censé optimiser le temps de trajet des conducteurs.

Le monde humain est intrinsèquement imprévisible

Maintenant, les gens ont créé un système d'IA général qui est robuste face à l'incertitude, ce qui nous rend plein d'espoir pour l'avenir de l'humanité.

Références :

http://www.science.org/doi/10.1126/science.add4679

https://www.nature.com/articles/d41586-022-04246-7

https :/ /www.deepmind.com/blog/mastering-stratego-the-classic-game-of-imperfect-information

https://youtu.be/HaUdWoSMjSY

https://youtu.be/L-9ZXmyNKgs

https://youtu.be/EOalLpAfDSs

https://youtu.be/MhNoYl_g8mo

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!