Injecting Combinatorial Optimization into MCTS: Application to the Board Game boop
This work addresses the challenge of enhancing game AI for abstract board games, specifically boop, by integrating combinatorial optimization into MCTS, representing an incremental improvement over existing methods.
The authors tackled the problem of improving AI performance in the board game boop by combining Monte Carlo Tree Search with Combinatorial Optimization, resulting in a method that beats a baseline MCTS algorithm 96% of the time and achieves a 373 ELO rating with a 69% win rate against human players.
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.