💻 computer science

Dynamic Resource Allocation for Ensemble Determinization MCTS

This paper proposes and validates two dynamic resource allocation strategies—adjusting the number of determinization trees and nonuniformly distributing simulation budgets—for Ensemble Determinization MCTS, demonstrating statistically significant performance improvements in high-uncertainty board games like Jaipur, Lost Cities, and Splendor.

Original authors: Jakub Kowalski, Adam CięĊkowski, Artur KrzyĊyński, Mark H. M. Winands

Published 2026-07-15

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Jakub Kowalski, Adam CięĊkowski, Artur KrzyĊyński, Mark H. M. Winands

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a massive, chaotic puzzle, but you can't see the whole picture. You only know a few pieces, and the rest are hidden under a foggy blanket. This is what playing a board game like Jaipur, Lost Cities, or Splendor feels like for a computer. There are hidden cards, random shuffles, and secret strategies. To make a good move, the computer uses a brainy trick called Monte Carlo Tree Search (MCTS).

Think of MCTS as a team of explorers. Instead of just one explorer guessing the path, the computer sends out a whole squad. In the version of MCTS used here, called Ensemble Determinization MCTS, the squad splits up. Each explorer imagines a different version of reality where the hidden cards are revealed in a specific way. They all run simulations (mental rehearsals) of the game, and then they vote on the best move.

The big question the authors asked was: How should we manage our team of explorers? Should we send out a fixed number of them every time? Should we give every explorer the exact same amount of time to think?

The paper suggests that the answer is "No, not always." Instead, the computer should be a smart manager that dynamically allocates resources. Here is how they tested two new management styles:

1. The "Flexible Team Size" Strategy

Imagine you are leading a group of detectives. If the clues are very confusing and the suspects look almost identical, you might need more detectives to be sure. But if the clues are crystal clear, maybe you don't need a huge crowd; a smaller team is fine.

The authors proposed a system where the computer changes the number of "explorer trees" (the detectives) on the fly.

The Rule: If the team is split and can't agree on a move (the "margin" between the best and second-best move is small), the computer adds more trees to get a clearer picture. If the team is super confident and agrees easily, it reduces the number of trees to save time.
The Result: In simulations, this worked wonders for Jaipur and Splendor. For example, in Jaipur, using this flexible team size boosted the win rate by 3.3 percentage points compared to a fixed team. In Splendor, it jumped by 5.1 percentage points.
The Catch: It didn't work as well for Lost Cities. In fact, for that game, the results were mixed or even slightly negative. The authors suggest this means the "right" number of detectives depends heavily on the specific game being played.

2. The "Smart Budget" Strategy

Now, imagine you have a total of 250,000 mental simulations (a "budget") to spend on a single turn. The old way was to split this budget equally among all the explorers. If you had 10 explorers, each got 25,000 simulations.

The authors asked: What if we give more time to the explorers who are struggling and less time to the ones who already know the answer?

The Rule: They tried several methods to decide who gets more time. One method, called "Across-tree UCB," treated the whole team as a single unit, focusing all the extra time on the moves that were most uncertain across the entire group. Another method, "Move Pruning," stopped wasting time on moves that were clearly bad.
The Result: This was a hit-or-miss game. The "Across-tree UCB" method was a star performer when combined with a "voting" system, improving Jaipur and Splendor scores. However, other methods, like trying to balance based on "win rate differences," actually made things worse, dropping scores by over 10 percentage points in some cases.
The Lesson: You can't just throw money (or simulations) at a problem. If you give extra time to the wrong explorers, you might confuse the whole team.

The Big Reveal: Don't Just Add It Up

The most interesting finding came when they tried to combine both strategies (changing the team size and the budget). You might think, "If Strategy A adds 3 points and Strategy B adds 2 points, combining them should add 5 points!"

But the computer didn't work like that. In Jaipur, the combined strategies only added 2.9 percentage points, even though the math predicted they should add 6.5. In Splendor, the gain was 2.1 points instead of the predicted 7.3.

The authors explain that these strategies sometimes get in each other's way. It's like having a flexible team size and a smart budget is great, but if you change the team size while you are trying to distribute the budget, the two systems might clash. The paper suggests that you can't just pick the best "size" and the best "budget" separately and expect them to work perfectly together; you have to test them as a package.

What About Time?

Finally, the authors tested these ideas not just by counting simulations, but by giving the computer a strict one-second time limit per turn (like a real game clock).

The flexible strategies still helped. In Lost Cities, a smart voting setup climbed from 47.6% to 54.6% wins under the time limit, turning a losing strategy into a winning one.
However, the ranking of the best strategies sometimes changed when switching from "count simulations" to "count seconds." This means that a strategy that looks great in a simulation might not be the best choice if you are racing against a clock.

The Bottom Line

The paper doesn't claim to have "solved" these games. Instead, it shows that dynamic resource allocation—being a flexible manager who adjusts the team size and budget based on how confused the team is—can significantly boost performance.

For Jaipur and Splendor: Being flexible is a clear win, boosting scores by 3 to 5 percentage points.
For Lost Cities: It's tricky; the benefits are smaller and less consistent.
The Warning: The paper explicitly rules out the idea that "more trees" or "more simulations" is always better. Sometimes, having a smaller, more focused team or stopping the search early on bad moves is the key to victory.

The authors conclude that while these dynamic tricks are powerful, they are highly dependent on the specific game. What works for Jaipur might fail for Lost Cities, so there is no single "magic setting" that works for every board game. The best approach is to test and tune these strategies for the specific game you are playing.

Technical Summary: Dynamic Resource Allocation for Ensemble Determinization MCTS

Problem Statement

Monte Carlo Tree Search (MCTS) is highly effective in deterministic, perfect-information games but faces significant challenges in environments characterized by uncertainty, randomness, and hidden information (imperfect information). While variants such as Ensemble Determinization MCTS (ED-MCTS) have been developed to handle these domains by instantiating multiple deterministic game states (determinizations), standard implementations often rely on static configurations. Specifically, the number of determinization trees and the allocation of the simulation budget across these trees are typically fixed constants. This static approach may be suboptimal, as the degree of uncertainty and the stability of the ensemble's decision can vary significantly depending on the game state, the opponent's strategy, and the specific line of play.

Methodology

The authors propose a framework for Dynamic Resource Allocation within ED-MCTS, introducing two primary axes of adaptation:

1. Dynamic Number of Determinizations

Instead of using a fixed number of trees ( $T$ ), the algorithm adjusts $T$ turn-by-turn based on the stability of the ensemble's decision.

Mechanism: The system monitors the "margin" between the winning move and the runner-up over a sliding window of turns ( $L$ ).
Adaptation Rules:
- Increase ( $L_\uparrow, M_\uparrow$ ): If the winning move's margin is small (i.e., the result could be altered by changing the output of at most $M_\uparrow$ trees) for $L_\uparrow$ consecutive turns, the number of trees is increased by 1 to improve confidence.
- Decrease ( $L_\downarrow, M_\downarrow$ ): If the margin is large (i.e., removing up to $M_\downarrow$ trees does not change the outcome) for $L_\downarrow$ consecutive turns, the number of trees is decreased by 1 to save computational resources.
Applicability: These rules are designed to be interpretable across different final move selection mechanisms (visits, score, voting, Borda).

2. Dynamic Simulation Allocation

Rather than distributing the total simulation budget ( $B$ ) uniformly across all $T$ trees, the budget is split non-uniformly based on the "contestedness" of each tree.

Contestedness Measure: For each tree, the algorithm compares the best root child against its strongest alternatives using one-sided confidence bounds (Hoeffding radius). A tree is considered "locked" if the lower bound of its best move exceeds the upper bound of all alternatives.
Allocation Policies Tested:
- Greedy: Allocates iterations to the currently most-contested unlocked tree.
- UCB (Win Rate Difference): Uses a high-level UCB formula on trees, prioritizing those where the difference between the top two moves is smallest (highest uncertainty).
- UCB (Visits Proportion): Prioritizes trees where the visit counts of the top two moves are similar ( $n_2/n_1 \approx 1$ ).
- Across-tree UCB: Treats the ensemble as a single bandit over root moves, summing statistics across all trees to select the most promising/uncertain move, then forcing that move in every tree.
- Move Pruning: Eliminates root moves whose upper confidence bound falls below the lower bound of the current best. Variants include "Freeze," which stops allocating budget to a tree once its decision is locked.

Experimental Setup

The proposed enhancements were evaluated on three popular tabletop games with varying degrees of hidden information and randomness:

Jaipur: A fast-paced card game with high hidden information and stochastic card draws.
Lost Cities: A card game involving hidden hands and randomized draw decks, requiring long-term planning under uncertainty.
Splendor: A strategy game with less hidden information but significant stochasticity in card deck composition.

Baselines and Metrics:

Opponent: Sample Open Loop MCTS (SOLMCTS), a standard baseline for nondeterministic environments.
Evaluation: Win rates were measured under both fixed simulation budgets (250k simulations per turn) and fixed time budgets (1 second per turn).
Move Selection: The study compared aggregation methods (visits, score, voting, Borda) to determine how dynamic allocation interacts with final decision-making.

Key Results

1. Move Selection and Static Baselines

Ensemble methods (multiple trees) consistently outperformed a single determinized tree ( $T=1$ ).
Optimal Tree Count: A moderate number of trees (5–10) generally yielded the best results, demonstrating a non-monotonic depth–breadth trade-off.
Aggregation: Contrary to some prior literature suggesting majority voting is superior, the visits and score aggregation methods often performed as well as or better than voting in these specific domains. The Borda method generally underperformed.

2. Dynamic Number of Determinizations

Game Dependence: The effectiveness of dynamic tree adjustment was highly game-specific.
- Jaipur & Splendor: Significant improvements were observed (e.g., +3.3% in Jaipur, +5.1% in Splendor) when using the voting mechanism.
- Lost Cities: Results were mixed, with most configurations showing no statistically significant gain or slight degradation.
Conclusion: Dynamic tree adjustment acts as a useful adaptive refinement rather than a universal replacement for a well-tuned static count.

3. Dynamic Simulation Allocation

Sensitivity: Performance gains were highly sensitive to the interaction between the allocation policy and the aggregation rule.
Across-tree UCB: This policy showed the clearest positive pattern, particularly when combined with voting, improving win rates in Jaipur and Splendor.
Negative Interactions: Tree-level UCB variants performed poorly when combined with summed-visits aggregation, often reducing win rates by over 10 percentage points. This suggests that biasing iteration counts per tree can distort the final vote in visit-summed systems.
Move Pruning: Showed mild benefits in specific configurations but did not provide consistent improvements across all games.

4. Combined and Time-Based Results

Non-Additivity: Combining dynamic tree counts and dynamic allocation did not yield additive gains. In many cases, the combined improvement was significantly lower than the sum of individual improvements, and in some instances, dynamic allocation hindered the gains from dynamic tree counts.
Time-Based Performance: The dynamic configurations maintained their advantage under wall-clock time limits. Notably, in Lost Cities, a combined voting configuration improved win rates from 47.6% to 54.6%, turning a below-parity baseline into a clear win.
Ranking Shifts: The ranking of mechanisms changed between fixed-iteration and fixed-time settings, indicating that configurations tuned for iteration counts may not be optimal for time-constrained deployment.

Significance and Claims

The paper claims that dynamic resource allocation is a viable and beneficial strategy for enhancing Ensemble Determinization MCTS, but with important caveats:

Contextual Utility: The gains are highly game-dependent and aggregation-dependent. There is no single "best" configuration that applies universally across all imperfect information games.
Adaptive Refinement: The proposed methods serve best as adaptive refinements to a static ED-MCTS baseline rather than a complete overhaul.
Evaluation Necessity: The authors emphasize that mechanism selection must be validated under the specific deployment budget (time vs. iterations) and in conjunction with the chosen aggregation method, as interactions between these factors are complex and non-linear.
Limitations: The study is limited to three specific board games and a specific simulation budget. The authors note that the optimal ensemble size and aggregation rules are likely specific to the game's heuristic evaluation functions and structure.

The work contributes a set of interpretable, dynamic mechanisms that allow ED-MCTS to self-regulate its computational resources based on the immediate uncertainty of the game state, offering statistically significant strength increases in specific, well-chosen configurations.