Dynamic Resource Allocation for Ensemble Determinization MCTS
2026-07-14 • Artificial Intelligence
Artificial Intelligence
AI summaryⓘ
The authors improved a type of game-playing algorithm called Ensemble Determinization Monte Carlo Tree Search (MCTS), which is useful for games with hidden information and randomness. They introduced two new ways to better use computing resources: one changes the number of game scenarios the algorithm considers based on search progress, and the other allocates more effort to promising scenarios. They tested these changes on three board games (Jaipur, Lost Cities, and Splendor) and found that some setups made the algorithm notably stronger. Their work helps make game-playing AI more efficient and effective in uncertain situations.
Monte Carlo Tree SearchEnsemble DeterminizationDynamic resource allocationSimulation budgetHidden information gamesRandomnessBoard games AIGame simulations
Authors
Jakub Kowalski, Adam Ciężkowski, Artur Krzyżyński, Mark H. M. Winands
Abstract
Simulation-based algorithms are especially suited for high-uncertainty environments such as adversarial board games with significant elements of randomness and hidden information. In particular, several Monte Carlo Tree Search (MCTS) variants are commonly used in such domains. In this paper, we propose a series of enhancements for Ensemble Determinization MCTS, introducing two axes for dynamic resource allocation. First, Dynamic Number of Determinizations, increases or decreases the number of currently used determinization trees depending on the behavior of so-far search. Second, Dynamic Simulation Allocation, splits the simulation budget nonuniformly across the determinization trees, using simulation-to-simulation decisions to choose the tree with potentially the best knowledge gain. As benchmark domains, we used three popular tabletop games: Jaipur, Lost Cities, and Splendor. Testing our proposed enhancements in iteration- and time-based settings showed that particular configurations yield a statistically significant increase in the algorithm's strength.