# Combinatorial Multi-armed Bandits for Real-Time Strategy Games

arXiv: https://arxiv.org/abs/1710.04805 · HTML: https://mlsanity.com/paper/1710.04805/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Oct 2017.

## Built on by (most cited first, 7 of 7)

- [Gym-μRTS: Toward Affordable Full Game Real-time Strategy Games Research with Deep Reinforcement Learning](https://mlsanity.com/paper/2105.13807/) (2021)
- [Choosing Well Your Opponents: How to Guide the Synthesis of Programmatic Strategies](https://mlsanity.com/paper/2307.04893/) (2023)
- [Searching for Programmatic Policies in Semantic Spaces](https://mlsanity.com/paper/2405.05431/) (2024)
- [Player Modeling via Multi-Armed Bandits](https://mlsanity.com/paper/2102.05264/) (2021)
- [Split Moves for Monte-Carlo Tree Search](https://mlsanity.com/paper/2112.07761/) (2021)
- [InnateCoder: Learning Programmatic Options with Foundation Models](https://mlsanity.com/paper/2505.12508/) (2025)
- [Visualising Multiplayer Game Spaces](https://mlsanity.com/paper/2202.05773/) (2022)

## Abstract (arXiv)

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"ive 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"ive 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"ive sampling outperforms the other sampling strategies.