Towards a Characterisation of Monte-Carlo Tree Search Performance in Different Games

The paper introduces a dataset and preliminary analysis to investigate the performance of different Monte Carlo Tree Search (MCTS) variants across a diverse set of games, using a comprehensive set of game features and predictive models to gain insights into which MCTS strategies work best in various gaming contexts.

Abstract

Many enhancements to Monte-Carlo Tree Search (MCTS) have been proposed over almost two decades of general game playing and other artificial intelligence research. However, our ability to characterise and understand which variants work well or poorly in which games is still lacking. This paper describes work on an initial dataset that we have built to make progress towards such an understanding: 268,386 plays among 61 different agents across 1494 distinct games. We describe a preliminary analysis and work on training predictive models on this dataset, as well as lessons learned and future plans for a new and improved version of the dataset.

Method

The authors used a dataset comprising 268,386 plays between 61 different MCTS agents across 1494 distinct games, with each game represented by 809 features. They employed predictive modeling techniques, training models to forecast outcomes between pairs of agents and utilizing SHAP (SHapley Additive exPlanations) values to interpret the importance of different features in the models' predictions. This approach allowed them to identify key factors influencing the performance of MCTS variants in various gaming scenarios.

Main Finding

The authors discovered that certain features, such as the advantage of one player over another in random play, are strong predictors of MCTS performance. They also found that play-out strategies that terminate early tend to result in poor performance for MCTS agents, and that matches against random agents may provide insights about the games themselves but not necessarily about the agents' performance. These findings suggest that the performance of MCTS variants can be significantly influenced by the characteristics of the games they are applied to, and that a more thorough analysis considering combinations of features could further elucidate these relationships.

Conclusion

The conclusion of the paper is that the authors have made progress towards characterizing the performance of different variants of Monte Carlo Tree Search (MCTS) in various games by constructing an initial dataset and conducting a preliminary analysis. They have identified some key predictors of MCTS performance, such as the advantage of one player over another in random play, and have learned valuable lessons about the construction of the dataset. The authors plan to improve the dataset and continue with more elaborate analyses in future research to further understand the relationship between MCTS performance and game characteristics.

Keywords

Monte Carlo Tree Search (MCTS), dataset, predictive models, SHAP values, game features, playing strength, agents, general game playing, artificial intelligence, Ludii, zero-sum games, utility scores, cross-validation, feature importance, random play-outs, early termination, performance predictors.