Combinatorial Multi-armed Bandits for Real-Time Strategy Games

10/13/2017
by   Santiago Ontañón, et al.
0

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 naïve sampling, based on a variant of the Multi-armed Bandit problem called Combinatorial Multi-armed Bandits (CMAB). We analyze the theoretical properties of several variants of 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, naïve sampling outperforms the other sampling strategies.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset