  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.
