Combinatorial Multi-armed Bandits for Real-Time Strategy Games
This addresses a specific problem in real-time strategy games for AI researchers, but it is incremental as it builds on existing CMAB and MCTS methods.
The paper tackled the challenge of large branching factors in game tree search by proposing a naive sampling strategy based on Combinatorial Multi-armed Bandits for Monte Carlo Tree Search, showing that it outperforms other strategies as branching factors increase.
Games with large branching factors pose a significant challenge for game tree search algorithms. In this paper, we address this problem with a sampling strategy for Monte Carlo Tree Search (MCTS) algorithms called {\em naïve sampling}, based on a variant of the Multi-armed Bandit problem called {\em Combinatorial Multi-armed Bandits} (CMAB). We analyze the theoretical properties of several variants of {\em naïve sampling}, and empirically compare it against the other existing strategies in the literature for CMABs. We then evaluate these strategies in the context of real-time strategy (RTS) games, a genre of computer games characterized by their very large branching factors. Our results show that as the branching factor grows, {\em naïve sampling} outperforms the other sampling strategies.