L'IA DeepNash bluffe encore mieux que les humains au Stratego
DeepMind, filiale d’Alphabet (comme Google), est surtout célèbre pour avoir mis au point AlphaGo, son intelligence artificielle qui n’a cessé de progresser dans sa capacité à jouer au go.
L’algorithme est cependant encore amélioré avec AlphaGo Zero, qui joue uniquement contre lui-même. Puis, avec AlphaZero, qui surpasse largement n’importe quel joueur humain ou informatique, non seulement au go, mais encore aux échecs et au shōgi.
Moins de deux semaines après l’annonce de Cicero par Meta, une IA capable de se hisser parmi les meilleurs joueurs de Diplomacy, DeepMind réplique le 1er décembre 2022 avec DeepNash. Sa nouvelle IA, en partant de zéro et en jouant uniquement contre elle-même, a atteint le même niveau que des joueurs experts au Stratego.
C’est quoi, Stratego ?
Stratego est un jeu de société, de stratégie et de bluff, pour deux joueurs, publié en 1946. Il est fortement inspiré de L’Attaque, créé par la Française Hermance Edan en 1908.
À l’instar des échecs, 40 pièces, représentant différentes unités militaires, sont disposées de part et d’autre d’un plateau de 92 cases. Le but est de capturer le drapeau de son adversaire, ou d’éliminer suffisamment de ses unités pour l’empêcher de se déplacer.
Deux particularités le distinguent des autres jeux du genre :
La disposition des pièces n’est pas fixe en début de partie, ce sont les joueurs qui décident de leur placement, ce qui représente pas moins de 1066 configurations de départ possibles ;
les pièces ont deux faces : l’une neutre, vue par l’adversaire, l’autre, qui détermine son type (drapeau, espion, éclaireur…), connue uniquement de son propriétaire. C’est donc un jeu à information imparfaite, contrairement aux échecs ou au go par exemple.
Le jeu n’a pas pris une ride, et est toujours disponible en boutique.
DeepNash, l’IA qui bat les humains au Stratego
De fait, Stratego est un jeu bien plus complexe que ses homologues, les échecs et le go, ou que le poker. Le tableau ci-dessous permet de bien s’en rendre compte :
| Jeux | Échecs | Poker | Go 19x19 | Stratego |
|---|---|---|---|---|
| Nombre de tours (environ) | 60 | 15 | 300 | 1000 |
| Configurations de départ | 1 | 106 | 1 | 1066 |
| Complexité de l'arbre de décision | 10123 | 1017 | 10360 | 10535 |
Les approches d’apprentissage automatique, qui fonctionnent sur les jeux à information parfaite, ne sont pas facilement transférables ici. La nécessité de prendre des décisions avec des informations imparfaites, et la possibilité de bluffer, font que Stratego s’apparente davantage au poker Texas hold’em.
À l’inverse, les techniques d’IA qui fonctionnent dans des jeux comme le Texas hold’em ne sont pas transférables au Stratego, en raison du nombre important de tours nécessaires pour déterminer un gagnant.
Une nouvelle approche a donc été utilisée, basée sur la théorie des jeux et l’apprentissage par renforcement profond sans modèle, « sans modèle » signifiant que DeepNash ne tente pas de modéliser explicitement l’état du jeu de son adversaire pendant la partie. Dans les premiers tours notamment, quand il ne connaît encore que peu de pièces adverses, une telle modélisation serait inefficace, voire impossible.
Au lieu de cela, le style de DeepNash converge vers un équilibre de Nash, ce qui rend son jeu ardu à exploiter pour l’adversaire. Tellement difficile qu’il a atteint le troisième rang parmi les experts humains sur Gravon, la principale plateforme en ligne de Stratego.
L’IA s’est ainsi montrée particulièrement imprévisible, tant dans la phase initiale de placement des pièces, que lors des déplacements. Pour ces derniers, elle retenait un coup aléatoire parmi plusieurs possibilités équivalentes, pour ne pas donner à l’adversaire l’opportunité d’y déceler des tendances.
Enfin, elle a compris que la composante bluff faisait partie intégrante de la tactique pour l’emporter, et savait utiliser des pièces faibles comme s’il s’agissait d’unités de haut rang, pour tendre des embuscades aux joueurs humains.
L’équipe derrière le projet espère pouvoir appliquer cette nouvelle méthode à d’autres jeux à somme nulle à deux joueurs, à information parfaite ou imparfaite. Voire, de la généraliser au-delà des jeux à deux, pour aborder des problèmes réels à grande échelle, caractérisés par une information imparfaite et une quantité astronomique d’états possibles.
Enfin, pour les plus motivés, l’ensemble du code est mis à disposition sur GitHub.