Modélisation des Adversaires pour l'Entraînement de Modèles Basés sur la Recherche Arborescente de Monte Carlo dans le Jeu de Société Citadels

1. Introduction

La Recherche Arborescente de Monte Carlo (MCTS) s'est imposée comme une technique efficace pour la prise de décision dans les jeux de société, alliant adaptabilité et faible recours aux connaissances spécifiques du domaine. Ses performances sont remarquables dans les jeux déterministes à information parfaite, comme le Go (SILVER et al., 2016).

Cependant, son application se heurte à des limitations significatives dans les environnements avec plusieurs joueurs, des informations cachées et des contraintes de temps, où le coût computationnel élevé des simulations et la difficulté d'adaptation compromettent la réactivité et la qualité des décisions (POWLEY et al., 2014).

Dans ce contexte, les approches hybrides intégrant MCTS et Apprentissage par Renforcement (RL) ont montré un potentiel en permettant de découpler la phase de planification de l'exécution. La construction de structures de décision persistantes, avec stockage préalable de la recherche, permet une sélection instantanée des actions pendant le jeu, réduisant le besoin de simulations en ligne tout en préservant la profondeur stratégique (BROWNE, 2012 ; SWIECHOWSKI, 2023).

Dans cette recherche, un modèle hybride de MCTS avec des techniques d'apprentissage par renforcement hors ligne a été testé et développé. Le modèle a été entraîné et testé avec différents adversaires dans un environnement de simulation du jeu de société Citadels (FAIDUTTI, 2016).

2. Objectif Général

L'objectif général de cette recherche est de développer un framework hybride MCTS-RL capable d'opérer efficacement dans des jeux de société multijoueurs à information cachée, en utilisant Citadels comme étude de cas.

La proposition vise à éliminer les goulots d'étranglement computationnels du MCTS traditionnel grâce à la construction hors ligne d'une structure de décision persistante, permettant des actions rapides et robustes à l'exécution.

3. Méthodologie

Cette recherche se caractérise comme une étude expérimentale appliquée avec une analyse quali-quantitative.

La première étape a impliqué le développement et l'adaptation d'un environnement de simulation numérique pour le jeu de société Citadels. S'en est suivi le développement de cinq agents experts avec des stratégies personnalisées, conçus pour imiter des stratégies réelles utilisées par des joueurs humains, ainsi qu'un agent de base choisissant des actions aléatoirement. Après la validation de l'environnement et des agents développés, le développement du framework hybride MCTS-RL a débuté.

Le modèle MCTS est, dans son essence, un algorithme de recherche heuristique qui opère par l'exécution de multiples simulations. Pour chaque état de jeu distinct visité lors de ces simulations, un nœud correspondant est créé dans une structure de données en arbre. L'état initial du jeu représente le nœud racine de cet arbre.

Cependant, la proposition de stocker l'arbre entier et de le conserver pour les décisions futures est irréalisable en raison de l'énorme facteur de branchement. Pour rendre cela possible, il est nécessaire d'abstraire l'arbre : l'état du jeu est divisé en ses caractéristiques fondamentales (ex. : or du joueur, nombre de cartes en main) et chaque caractéristique est mappée vers une table de données indépendante.

Dans cette structure, les lignes d'une table représentent les valeurs possibles d'une caractéristique d'état, et les colonnes représentent les actions possibles que l'agent peut prendre (ex. : gagner de l'or, piocher des cartes). Deux valeurs sont stockées dans chaque cellule : le nombre de victoires obtenues (n) après avoir pris cette action dans cet état, et le nombre total de fois où cette combinaison a été explorée (m). Ces tables, une fois remplies par des simulations de parties de Citadels, constituent le modèle appris par l'agent.

Le processus d'entraînement comprend une composante d'apprentissage par renforcement : après chaque partie simulée, les résultats mettent à jour les tables de décision, influençant les choix futurs. Les victoires agissent comme des récompenses et renforcent les actions efficaces, augmentant leur probabilité d'être choisies à nouveau, tandis que les défaites réduisent cette possibilité. Ainsi, au fil de nombreuses simulations, le modèle s'adapte continuellement, équilibrant l'exploration de nouvelles alternatives et l'exploitation de stratégies éprouvées, convergeant progressivement vers des comportements plus efficaces.

4. Résultats et Discussion

Pour évaluer les performances du modèle MCTS proposé, il était fondamental de comprendre la dynamique de pouvoir entre les stratégies de base (agents experts et agent aléatoire). Pour ce faire, chacun a été soumis à une série de 10 000 parties contre quatre adversaires identiques.

La carte de chaleur présentée en Figure 1 illustre les performances de chaque stratégie (axe Y) contre les différents adversaires (axe X). Les stratégies possèdent des forces et des faiblesses distinctes : les Experts 1, 2 et 3 se montrent compétents dans la plupart des scénarios, tandis que les Experts 4 et 5 sont considérablement moins efficaces. Comme prévu, la stratégie complètement aléatoire affiche de très faibles performances contre tout adversaire minimalement structuré.

Figure 1 : Comparaison entre les stratégies.

L'étape suivante consistait à évaluer le modèle MCTS-RL. Différentes sessions d'entraînement ont été menées, chacune se concentrant sur l'un des adversaires, totalisant 100 000 parties d'entraînement pour chaque version du modèle. Ensuite, les performances de chaque modèle entraîné ont été mesurées contre tous les types d'adversaires selon le même modèle de test précédent, ainsi que contre des adversaires variés tirés aléatoirement.

La carte de chaleur présentée en Figure 2 montre le taux de victoire consolidé de chaque modèle. Le résultat le plus significatif fut celui du modèle entraîné dans l'environnement varié, qui a obtenu des performances constantes, surpassant les autres versions du modèle dans presque tous les scénarios de test. Cela suggère que l'exposition à une diversité de stratégies lors de l'entraînement était fondamentale pour développer une capacité de jeu plus robuste et généraliste.

Figure 2 : Comparaison entre les modèles entraînés.

Les modèles entraînés contre les Experts 4 e 5, considérés comme les adversaires les plus faibles, sont devenus des agents étonnamment efficaces. En revanche, l'entraînement contre les Experts 1 et 3, considérés comme des adversaires forts, a produit des modèles aux performances générales très médiocres.

Une explication possible de ce contraste est que les stratégies expertes avancées tendent à être très spécialisées, tandis que le modèle MCTS-RL, en début d'entraînement, s'approche d'un comportement aléatoire. Contre des adversaires forts, même des actions potentiellement avantageuses peuvent ne pas générer suffisamment de victoires pour que le modèle reconnaisse des schémas de succès ; alors que contre des adversaires moins spécialisés, les victoires surviennent plus fréquemment, favorisant l'apprentissage. Cela reste néanmoins une hypothèse qui nécessite confirmation.

5. Conclusion

Cette étude a démontré la viabilité de l'approche proposée, qui utilise une abstraction de l'arbre MCTS pour préserver les connaissances acquises entre les coups. Les résultats ont confirmé que le modèle est capable de développer des stratégies robustes pour l'environnement.

La performance supérieure de l'agent entraîné dans l'environnement varié montre que l'exposition à de multiples tactiques est fondamentale pour construire un modèle généraliste. De plus, la recherche indique que la qualité de l'agent final dépend davantage de la diversité que de la force apparente des adversaires d'entraînement.

Pour des études futures, il serait intéressant d'explorer plus précisément les raisons réelles pour lesquelles des stratégies moins spécialisées ont conduit à des modèles plus efficaces que des stratégies plus fortes. De plus, une comparaison du modèle proposé avec d'autres modèles MCTS aiderait également à obtenir une évaluation plus précise de l'approche.