Dynamic Resource Allocation for Ensemble Determinization MCTS

Monte Carlo Tree Search (MCTS) is highly effective for perfect-information games, but its performance degrades in environments with hidden information or randomness. Ensemble Determinization MCTS (ED-MCTS) addresses this by creating multiple 'determinized' versions of the game state. This paper investigates whether performance can be improved by dynamically allocating computational resources—specifically the number of determinization trees and the distribution of simulations across them—rather than using static, pre-set values.

The authors propose two primary dynamic enhancements to ED-MCTS:

1. Dynamic Number of Determinizations: The algorithm monitors the stability of the search. If the winning move's margin over the runner-up is small, the algorithm increases the number of trees to improve confidence. Conversely, if the result is stable, it reduces the number of trees to save resources.
2. Dynamic Simulation Allocation: Instead of splitting the simulation budget equally among all trees, the algorithm uses 'local contestedness' measures. It prioritizes trees where the best move is not yet clearly separated from alternatives, using techniques like UCB-based allocation or move pruning to focus computation on the most uncertain branches.

The researchers tested these methods on three tabletop games—Jaipur, Lost Cities, and Splendor—comparing them against a standard Sample Open Loop MCTS (SOLMCTS) baseline.

The experiments demonstrate a clear non-monotonic trade-off between search depth and breadth. Using a single determinization tree consistently underperforms compared to an ensemble approach. By dynamically adjusting the number of trees and focusing simulations on contested areas, the proposed ED-MCTS variants achieved significant win-rate improvements over the baseline, with gains of up to 13.2 percentage points in Jaipur and 12.7 in Splendor. The results suggest that tailoring the search effort to the specific uncertainty of the current game state is more efficient than uniform resource distribution.