Not All Possible Worlds Are Equal: Adaptive MCTS for Games with Hidden Information

In games involving incomplete information and randomness, the classic Monte Carlo Tree Search falls short: the tree is built on assumptions about the opponent’s hidden cards. A standard technique—Ensemble Determinization MCTS—generates several “possible worlds” (determinizations) and runs a search in each one. The problem is that all these worlds are usually allocated the same computational budget, even though their informativeness can differ by orders of magnitude.

The paper arXiv:2607.13007 proposes two mechanisms that break this assumption.

Dynamic Number of Determinizations changes the number of active trees on the fly. If the current search stabilizes, the number of trees decreases; if the results are contradictory, it increases. It’s a simple idea: don’t fix the number of hypotheses in advance, but rather react to what the search reveals.

Dynamic Simulation Allocation distributes simulations unevenly. Instead of dividing the budget equally among all determinization trees, the algorithm uses a “simulation-by-simulation” approach to direct resources toward the tree with the greatest potential for knowledge gain. Essentially, it’s a multi-armed bandit problem applied to the possible worlds themselves.

The benchmarks are three popular board games: Jaipur, Lost Cities, and Splendor. All three involve hidden information and randomness, making them a good stress test for determinization approaches. Testing was conducted in two modes: by number of iterations and by time—and in both cases, certain configurations yielded a statistically significant increase in the algorithm’s performance.

What’s important here for practitioners: Both mechanisms are not new architectures but rather extensions of the existing Ensemble MCTS. This means they can be integrated into existing code without rewriting the core. However, the paper does not provide a one-size-fits-all solution: “particular configurations” means that the performance gain depends on parameter tuning, and transferability of settings across domains is not guaranteed.

The broader implication extends beyond board games. Any system that evaluates hypotheses about a hidden state—whether it’s planning under uncertainty, modeling agent behavior, or robust search in partially observable environments—faces the same choice: to allocate resources equally or adaptively. This work shows that adaptivity pays off, but the cost is additional budget management logic and the need for domain-specific tuning.

Source: cs.AI updates on arXiv.org