The Combinatorial Multi-Armed Bandit Problem and Its Application to Real-Time Strategy Games

Authors

  • Santiago Ontanon Drexel University

Keywords:

Monte Carlo Tree Search, RTS Games

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.

Downloads

Published

2021-06-30

How to Cite

Ontanon, S. (2021). The Combinatorial Multi-Armed Bandit Problem and Its Application to Real-Time Strategy Games. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 9(1), 58-64. Retrieved from https://ojs.aaai.org/index.php/AIIDE/article/view/12681