AAAI Publications, Ninth Artificial Intelligence and Interactive Digital Entertainment Conference

Font Size: 
The Combinatorial Multi-Armed Bandit Problem and Its Application to Real-Time Strategy Games
Santiago Ontanon

Last modified: 2013-11-13

Abstract


Game tree search in games with large branching factors is a notoriously hard problem. In this paper, we address this problem with a new sampling strategy for Monte Carlo Tree Search (MCTS) algorithms, called "Naive Sampling", based on a variant of the Multi-armed Bandit problem called the "Combinatorial Multi-armed Bandit" (CMAB) problem. We present a new MCTS algorithm based on Naive Sampling called NaiveMCTS, and evaluate it in the context of real-time strategy (RTS) games. Our results show that as the branching factor grows, NaiveMCTS performs significantly better than other algorithms.

Full Text: PDF