Injecting Combinatorial Optimization into MCTS: Application to the Board Game boop

The paper introduces a new AI method that enhances Monte Carlo Tree Search (MCTS) by incorporating Combinatorial Optimization, significantly improving performance in the board game "boop." and achieving a high win rate against both traditional MCTS algorithms and human players on the Board Game Arena platform.

Abstract

Games, including abstract board games, constitute a convenient ground to create, design, and improve new AI methods. In this field, Monte Carlo Tree Search is a popular algorithm family, aiming to build game trees and explore them efficiently. Combinatorial Optimization, on the other hand, aims to model and solve problems with an objective to optimize and constraints to satisfy, and is less common in Game AI. We believe however that both methods can be combined efficiently, by injecting Combinatorial Optimization into Monte Carlo Tree Search to help the tree search, leading to a novel combination of these two techniques. Tested on the board game boop., our method beats 96% of the time the Monte Carlo Tree Search algorithm baseline. We conducted an ablation study to isolate and analyze which injections and combinations of injections lead to such performances. Finally, we opposed our AI method against human players on the Board Game Arena platform, and reached a 373 ELO rating after 51 boop. games, with a 69% win rate and finishing ranked 56th worldwide on the platform over 5,316 boop. players.

Method

The authors used a methodology that involved integrating Combinatorial Optimization techniques into the Monte Carlo Tree Search (MCTS) algorithm to improve its performance in the context of the board game "boop." This integration was achieved through three specific injections: before the Selection step, during the Expansion step, and within the Playout step. The authors conducted experiments to compare their enhanced MCTS with traditional MCTS and other variants, demonstrating its superiority with a high win rate. They also performed an ablation study to determine the most critical aspects of their method and conducted games against human players on the Board Game Arena platform to assess the method's practical effectiveness.

Main Finding

The authors discovered that by integrating Combinatorial Optimization into Monte Carlo Tree Search (MCTS), they could significantly enhance the performance of the MCTS algorithm in the board game "boop." Their method, which involved injecting Combinatorial Optimization into the Selection, Expansion, and Playout steps of MCTS, resulted in a 96% win rate against traditional MCTS in AI-versus-AI games. Additionally, when tested against human players on the Board Game Arena platform, their AI achieved a 373 ELO rating and was ranked 56th out of 5,316 players. The ablation study revealed that the enhanced Expansion step was particularly important for the method's success when combined with the other injections. The authors also found that their AI performed better when playing as the second player, which they attributed to the heuristics function used in their model being more suited to defensive play in the early game.

Conclusion

The conclusion of the paper is that the integration of Combinatorial Optimization into Monte Carlo Tree Search (MCTS) significantly enhances the performance of the MCTS algorithm in the board game "boop." The authors' method, which includes injections of Combinatorial Optimization into the Selection, Expansion, and Playout steps of MCTS, outperforms traditional MCTS with a 96% win rate in AI-versus-AI games and achieves a 373 ELO rating on the Board Game Arena platform, ranking 56th out of 5,316 players. The ablation study indicates that the enhanced Expansion step is particularly crucial when combined with the other injections. The paper suggests that this approach can be beneficial in situations with limited computational resources and sets the stage for future research on multi-stage decision-making problems.

Keywords

Monte Carlo Tree Search, Combinatorial Optimization, Constraint Programming, Board Games, Artificial Intelligence, Game AI, ELO Rating, Heuristics, Playout Policy, Tree Policy, Expansion Policy, Selection Policy, Ablation Study, Android App, Limited Computing Resources, Multi-stage Decision-making, boop.