Algorithmes de recherche d’arbre de Monte Carlo pouvant jouer au jeu de cartes du Seigneur des Anneaux

Algorithmes de recherche d'arbre de Monte Carlo pouvant jouer au jeu de cartes du Seigneur des Anneaux

Une illustration combinant différents agents en un seul tour de jeu au jeu de cartes Le Seigneur des Anneaux. Crédit : Godlewski & Sawicki.

Lorsque les algorithmes d’apprentissage automatique et d’autres outils de calcul ont commencé à devenir de plus en plus avancés, de nombreux informaticiens ont entrepris de tester leurs capacités en les entraînant à rivaliser avec les humains dans différents jeux. L’un des exemples les plus connus est AlphaGo, le programme informatique développé par DeepMind (une société d’apprentissage en profondeur acquise plus tard par Google), qui a été formé pour rivaliser avec les humains dans le jeu de stratégie complexe et abstrait Go.

Au cours de la dernière décennie, les développeurs ont formé de nombreux autres modèles pour jouer contre des humains à des jeux de stratégie, des jeux de société, des jeux informatiques et des jeux de cartes. Certains de ces agents artificiels ont obtenu des résultats remarquables, battant des champions humains et des experts du jeu établis.

Des chercheurs de l’Université de technologie de Varsovie ont récemment entrepris de développer une technique basée sur les algorithmes de recherche arborescente de Monte Carlo (MCTS) qui pourrait jouer au jeu de cartes classique du Seigneur des Anneaux (LotR), publié en 2011 par Fantasy Flight Games. Un algorithme MCTS est une méthode de décision heuristique universelle qui peut optimiser l’espace de recherche de solution dans un jeu ou un scénario donné, en jouant à une série de jeux aléatoires, appelés « playouts ». Les chercheurs ont présenté leur technique MCTS dans un article récent prépublié sur arXiv.

« Nous sommes fans du jeu de cartes LotR, mais nous avons constaté qu’il n’existait aucune approche d’IA qui pourrait jouer à ce jeu », ont déclaré à TechXplore Bartosz Sawicki et Konrad Godlewski, les deux chercheurs qui ont mené l’étude. « Néanmoins, nous avons trouvé des applications de méthodes de recherche d’arbres pour des jeux de cartes similaires tels que Magic: The Gathering ou Hearthstone. »

La principale raison pour laquelle une méthode de calcul pouvant jouer au jeu de cartes LotR n’existait pas encore est que le développement d’une telle méthode est très difficile. En fait, LotR est un jeu de cartes coopératif caractérisé par un immense espace de solutions possibles, une structure logique complexe et la possibilité que des événements aléatoires se produisent. Ces qualités rendent les règles et stratégies du jeu très difficiles à acquérir par des méthodes informatiques.

« Le tournoi de Go 2016 a été le dernier moment où les joueurs humains ont eu la chance de rivaliser avec les joueurs de l’IA », ont expliqué Sawicki et Godlewski. « L’objectif de notre article était de mettre en œuvre un agent MCTS pour le jeu LotR. »

Le jeu de cartes LotR est difficile à comparer à d’autres jeux de cartes fantastiques et d’aventure, tels que Magic the Gathering, Gwent ou Hearthstone. En fait, contrairement à ces autres jeux, LotR est conçu pour être joué seul ou en équipe coopérative, plutôt qu’en compétition avec d’autres joueurs. De plus, les processus de prise de décision dans le jeu sont très complexes, car le gameplay comprend plusieurs étapes, dont la plupart dépendent du résultat de l’étape précédente.

Malgré ces défis, Sawicki et Godlewiski ont pu développer une méthode basée sur les SCTM qui pourrait jouer au LotR. Ils ont ensuite évalué la technique qu’ils ont développée dans une série de tests, réalisés sur un simulateur de jeu.

« Notre agent MCTS a obtenu un taux de victoire nettement plus élevé qu’un joueur expert basé sur des règles », ont déclaré Sawicki et Godlewski. « De plus, en ajoutant la connaissance du domaine à la politique d’expansion et aux playouts MCTS, nous avons pu améliorer encore l’efficacité globale du modèle.

Les travaux récents de Sawicki et Godlewski prouvent qu’il est possible de combiner avec succès différentes techniques d’IA et de calcul pour créer des agents artificiels capables de jouer à des jeux complexes et coopératifs à plusieurs étapes, comme le jeu de cartes LotR. Néanmoins, l’équipe a découvert que l’utilisation des SCTM pour s’attaquer à ces jeux complexes peut également avoir des limites importantes.

« Le principal problème est que MCTS fusionne la logique de jeu avec l’algorithme d’IA, vous devez donc connaître les mouvements légaux lorsque vous construisez un arbre de jeu », ont expliqué Sawicki et Godlewski. « Pourtant, le débogage des arbres de jeu avec un facteur de branchement important est un cauchemar. Il y a eu de nombreux cas dans lesquels le programme fonctionnait sans problème, mais le taux de victoire était de zéro et nous avons dû examiner l’ensemble de l’arbre manuellement. »

À l’avenir, la technique basée sur le MCTS développée par cette équipe de chercheurs pourrait être utilisée par les passionnés de LotR pour jouer au jeu en collaboration avec une IA. De plus, cette étude récente pourrait inspirer le développement d’autres outils d’IA pouvant jouer à des jeux complexes, stratégiques et à plusieurs étapes. Dans leurs études actuelles et futures, Sawicki et Godlewski aimeraient également explorer le potentiel et les performances des agents d’apprentissage par renforcement profond (RL) formés sur le jeu LotR.

« Notre travail actuel se concentre sur l’utilisation des méthodes RL pour améliorer davantage les performances des agents d’IA dans le jeu », ont ajouté Sawicki et Godlewski. « Dans ce cas, étant donné un état de jeu, le réseau de neurones renvoie une action exécutée par l’environnement (c’est-à-dire le simulateur de jeu). C’est délicat, car le nombre d’actions varie selon les états et les réseaux politiques ne peuvent avoir qu’un nombre fixe Jusqu’à présent, nos résultats sont prometteurs, et nous expliquerons comment nous avons obtenu ces résultats dans un prochain article.  »


Jeux olympiques de Tokyo : Google déploie ces mises à jour pour entrer dans l’esprit des Jeux d’été


Plus d’information:
Konrad Godlewski, Bartosz Sawicki, Optimisation du lecteur MCTS pour Le Seigneur des Anneaux : Le Jeu de Cartes. arXiv : 2109.12001v1 [cs.LG], arxiv.org/abs/2109.12001

Konrad Godlewski, Bartosz Sawicki, agents basés sur les SCTM pour un jeu de cartes solo à plusieurs étapes. arXiv:2109.12112v1 [cs.AI], arxiv.org/abs/2109.12112

© 2021 Réseau Science X

Citation: Algorithmes de recherche d’arbres de Monte Carlo pouvant jouer au jeu de cartes du Seigneur des Anneaux (2021, 8 octobre) récupérés le 8 octobre 2021 sur https://techxplore.com/news/2021-10-monte-carlo-tree-algorithms-lord .html

Ce document est soumis au droit d’auteur. En dehors de toute utilisation équitable à des fins d’étude ou de recherche privée, aucune partie ne peut être reproduite sans l’autorisation écrite. Le contenu est fourni seulement pour information.