Back to AI Research

AI Research

Dynamic Resource Allocation for Ensemble Determiniz... | AI Research

Key Takeaways

  • Dynamic Resource Allocation for Ensemble Determinization MCTS explores ways to improve how artificial intelligence plays games that involve hidden informatio...
  • 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.
Paper AbstractExpand

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.

Dynamic Resource Allocation for Ensemble Determinization MCTS explores ways to improve how artificial intelligence plays games that involve hidden information and randomness, such as card games. While standard Monte Carlo Tree Search (MCTS) excels in games with perfect information, it struggles when the game state is uncertain. This paper introduces dynamic strategies for Ensemble Determinization MCTS (ED-MCTS) to better manage computational resources, allowing the AI to adapt its search strategy based on the specific needs of the current game state.

Enhancing Resource Allocation

The researchers propose two primary ways to make the search process more efficient. First, they introduce a "Dynamic Number of Determinizations," which adjusts the number of parallel search trees used by the AI. If the AI finds that its current decision is unstable—meaning the lead between the best move and the runner-up is slim—it increases the number of trees to gain more clarity. Conversely, if the decision is stable, it reduces the number of trees to save resources.
Second, the authors implement "Dynamic Simulation Allocation." Instead of splitting the total simulation budget equally across all trees, the AI distributes simulations unevenly. It prioritizes trees that are "contested," where the best move is not yet clearly defined, and ignores trees that have already reached a confident conclusion. This ensures that the computational budget is spent where it is most likely to improve the AI's final decision.

Testing in Popular Tabletop Games

To validate these enhancements, the team tested their algorithms on three popular tabletop games: Jaipur, Lost Cities, and Splendor. These games were chosen because they feature different levels of hidden information and stochastic elements. By comparing their dynamic approach against a standard baseline (Sample Open Loop MCTS), the researchers sought to determine if these adjustments could lead to a statistically significant increase in the AI's strength.

Key Findings

The experiments revealed that the number of determinization trees significantly impacts performance, with a "moderate" number of trees (between 5 and 10) generally yielding the best results. The study also challenged some common assumptions in the field; for instance, they found that simple methods for aggregating results, such as counting visits or scores, often performed as well as or better than more complex voting mechanisms. Overall, the proposed dynamic enhancements demonstrated that allowing the algorithm to adapt its search strategy turn-by-turn leads to a stronger, more effective AI in high-uncertainty environments.

Comments (0)

No comments yet

Be the first to share your thoughts!