Search papers, labs, and topics across Lattice.
This paper enhances Ensemble Determinization Monte Carlo Tree Search (MCTS) by introducing dynamic resource allocation strategies that adaptively adjust the number of determinization trees and the distribution of simulation budgets based on ongoing search performance. The proposed methods, Dynamic Number of Determinizations and Dynamic Simulation Allocation, allow the algorithm to optimize its search efficiency in high-uncertainty environments, such as adversarial board games. Experimental results across three tabletop games鈥擩aipur, Lost Cities, and Splendor鈥攄emonstrate a statistically significant improvement in algorithmic strength with specific configurations of these enhancements.
Dynamic resource allocation in MCTS can significantly boost performance in adversarial environments by intelligently managing simulation resources.
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.
