Recherche arborescente de Monte-Carlo : une revue des inconvénients, des avantages et des limites dans les jeux multijoueurs complexes

1. Introduction

La recherche arborescente de Monte-Carlo (MCTS) est une famille d'algorithmes de recherche qui construit un arbre de décision en quatre étapes : sélection, expansion, simulation et rétropropagation. Au lieu d'exiger une fonction d'évaluation complète pour chaque état, la méthode estime la qualité des actions à partir de nombreuses simulations, en équilibrant l'exploration d'alternatives rarement visitées et l'exploitation d'actions connues. Cette caractéristique a contribué à des résultats expressifs dans des jeux tels que le Go, les échecs et le shogi, en particulier dans des environnements à deux joueurs avec information parfaite (BROWNE et al., 2012).

Cependant, les jeux numériques et de société contemporains présentent des conditions plus complexes : plusieurs adversaires, information cachée, hasard, grands espaces d'actions et décisions en temps réel. Dans ces situations, une simulation supplémentaire ne produit pas toujours une meilleure décision. Un plus grand nombre de joueurs élargit l'arbre de recherche et rend difficile la modélisation des réponses des adversaires. L'information imparfaite peut provoquer une fusion de stratégies lorsque les états cachés sont traités de manière inadéquate, tandis que la pression temporelle réduit le budget computationnel disponible. Malgré l'application croissante de MCTS dans ces scénarios, la littérature reste fragmentée et concentrée sur les jeux classiques.

2. Objectifs

L'objectif général de ce travail était d'identifier et d'organiser les limitations récurrentes de MCTS dans les jeux numériques et de société multijoueurs, en particulier dans les environnements à information imparfaite, stochasticité et contraintes de temps.

Comme objectifs spécifiques, le travail cherchait à rassembler les stratégies qui atténuent ces limitations et à identifier les lacunes de recherche pouvant guider les études futures et favoriser des évaluations plus comparables et reproductibles.

3. Méthodologie

Une revue de la littérature a été réalisée sur des études publiées entre 2013 et 2025, avec des recherches dans les bases de données IEEE Xplore, HAL Science Ouverte et Google Scholar. Les stratégies de recherche combinaient les termes « Monte Carlo Tree Search » et « MCTS » avec des expressions liées aux jeux numériques, aux jeux de plateau et aux jeux multijoueurs. La sélection a considéré les travaux dont le titre ou le résumé abordait MCTS, une variante directe ou une méthode hybride appliquée à des jeux compétitifs ou coopératifs. Les études hors du champ, les documents sans accès au texte intégral et les travaux dont la portée n'était pas compatible avec les objectifs de la revue ont été exclus.

Les recherches ont récupéré 24 enregistrements, dont deux étaient dupliqués entre les requêtes, ce qui a donné 22 travaux uniques potentiellement pertinents (17 en anglais et cinq en français). Après sélection, 18 études ont été retenues pour une analyse complète et quatre ont été exclues. Le corpus final a rassemblé 13 études d'IEEE Xplore, trois de HAL et deux trouvées via Google Scholar, et parmi celles sélectionnées, 15 textes étaient en anglais et trois en français. Les travaux ont été classés par type de jeu, algorithme utilisé, contraintes de l'environnement, résultats rapportés et stratégies d'atténuation. L'analyse thématique a été organisée en trois catégories structurelles de limitation, les limites de performance, les angles morts tactiques et les compromis dans la modélisation des adversaires, et deux amplificateurs dépendants du domaine, l'information imparfaite et les décisions en temps réel.

4. Résultats et Discussion

Les études analysées indiquent que MCTS fonctionne de manière plus constante dans les jeux aux états bien définis, avec un facteur de branchement modéré et un budget computationnel suffisamment important pour un nombre élevé de simulations. Parmi les 18 travaux sélectionnés, huit portaient sur des jeux numériques, six étudiaient des jeux de plateau ou de société et les autres analysaient des jeux de cartes, des environnements de jeu général ou des applications connexes. Les algorithmes basés sur MCTS ont été utilisés dans 14 études, souvent combinés avec des réseaux de neurones, des abstractions de l'espace d'actions, des politiques de simulation et des techniques de réglage des paramètres.

La première limitation identifiée concerne la performance de la recherche. Bien que l'augmentation du nombre de simulations améliore généralement la qualité des décisions, les gains marginaux tendent à diminuer à mesure que les nouvelles simulations commencent à revisiter des trajectoires déjà suffisamment explorées. Les résultats obtenus au Go, dans les jeux de stratégie en temps réel et dans les jeux de société montrent que doubler le budget computationnel peut produire des bénéfices réduits ou nuls au-delà d'un certain point. En outre, les études sur la profondeur de compétence montrent que cette limite dépend à la fois de la complexité du jeu et de la configuration de l'agent. Les stratégies d'atténuation incluent l'abstraction de l'espace d'actions, la simplification des simulations et le réglage automatique des politiques, des constantes d'exploration et des stratégies de rollout via l'algorithme évolutionnaire N-Tuple Bandit (NTBEA) (GOODMAN ; PEREZ-LIEBANA ; LUCAS, 2024).

La deuxième limitation correspond aux angles morts du raisonnement tactique. Comme MCTS estime la valeur moyenne des continuations échantillonnées, l'algorithme peut échouer dans des positions qui exigent de reconnaître des séquences tactiques spécifiques, des menaces à long terme ou des configurations peu fréquentes. Au Go, des situations telles que les échelles et le semeai illustrent des scénarios dans lesquels une structure tactique évidente pour des joueurs expérimentés peut ne pas être identifiée par la recherche.

La troisième limitation concerne la modélisation des adversaires. Dans les jeux à trois participants ou plus, le processus de recherche doit représenter non seulement les décisions du joueur à la racine de l'arbre, mais aussi les réponses possibles de chaque adversaire. Les modèles qui conservent des structures indépendantes pour chaque adversaire tendent à mieux représenter le comportement stratégique, bien qu'ils augmentent considérablement le coût computationnel. En revanche, des approches simplifiées, telles que la recherche paranoïaque et les politiques généralisées, réduisent ce coût mais peuvent échouer à représenter des comportements pertinents. La littérature suggère que les approches fondées sur la focalisation sélective, la généralisation des réponses des adversaires et la décomposition de l'arbre sont des alternatives prometteuses, bien qu'elles soient encore peu évaluées dans les jeux à grand nombre de participants (BAIER ; KAISERS, 2020).

L'information imparfaite intensifie ces limitations. Dans les jeux de cartes, Pokémon et d'autres environnements à états cachés, la déterminisation, qui consiste à supposer une configuration possible de l'information inconnue et à rechercher comme si elle était vraie, peut provoquer la fusion de stratégies incompatibles. L'Information Set MCTS, une variante de la recherche arborescente de Monte-Carlo conçue pour gérer l'incertitude, réduit ce problème en regroupant les états que le joueur ne peut pas distinguer, en préservant uniquement l'information réellement disponible au moment de la décision (COWLING ; POWLEY ; WHITEHOUSE, 2012). Malgré cela, le hasard inhérent à l'environnement et la nécessité d'inférer le comportement des adversaires continuent de limiter la fiabilité des estimations produites.

Dans les environnements en temps réel, tels que les jeux de stratégie, les MOBA et les jeux de tir à la première personne, les contraintes de temps deviennent un facteur critique. MCTS doit sélectionner des actions dans des intervalles très courts tout en gérant des espaces d'actions combinatoires, des unités multiples et des observations partielles. Dans ce contexte, les abstractions hiérarchiques, les macro-actions, l'élagage des actions et les politiques obtenues par apprentissage supervisé ou par apprentissage par renforcement apparaissent comme des stratégies récurrentes (ONTAÑÓN, 2013). Dans certaines situations, des méthodes alternatives peuvent être plus performantes. L'algorithme évolutionnaire à horizon glissant (RHEA), par exemple, fait évoluer de courtes séquences d'actions et effectue une replanification continue, se révélant particulièrement adapté aux jeux coopératifs et aux environnements fortement stochastiques dans lesquels l'arbre de recherche change rapidement (SFIKAS ; LIAPIS, 2022).

Des applications de MCTS qui dépendent moins des décisions en temps réel ont également été identifiées, telles que l'équilibrage automatique, le playtesting et le soutien à la conception de jeux. Dans ces scénarios, le temps de traitement cesse d'être une contrainte critique, permettant d'explorer extensivement différentes configurations, d'identifier des déséquilibres et d'évaluer des alternatives de conception. Bien que la plupart des études rapportent des résultats favorables aux approches proposées, certains travaux ont observé une performance inférieure de MCTS par rapport à des techniques concurrentes, comme dans les jeux Kingdomino et Pandemic.

5. Conclusion

La revue a également identifié cinq opportunités pertinentes pour la recherche future : (i) l'adoption et la standardisation de benchmarks partagés pour les jeux multijoueurs à information imparfaite ; (ii) l'évaluation systématique des techniques de modélisation des adversaires dans les jeux à plus grand nombre de participants ; (iii) l'étude de la relation entre la complexité perçue par les joueurs humains et la profondeur effective de la recherche ; (iv) l'étude des séries compétitives au meilleur des trois et au meilleur des cinq, en tenant compte de l'historique des picks et bans ; et (v) l'expansion des applications de MCTS dans l'équilibrage automatique, le playtesting et la génération procédurale de contenu.