Monte-Carlo Tree Search using Batch Value of Perfect Information

Shahaf S. Shperberg, Solomon Eyal Shimony, Ariel FelnerUAI 2017

Introduction

Monte-Carlo Tree Search (MCTS) has revolutionized artificial intelligence in complex gaming domains, from Go to real-time strategy games. At its core, MCTS relies on a selection policy to navigate the search tree, typically balancing exploration and exploitation via algorithms like UCT (Upper Confidence Bound for Trees). However, standard selection policies often focus on minimizing cumulative regret during the search rather than simple regret—the goal of identifying the single best move at the root. This paper introduces Batch Value of Perfect Information (BVPI), a novel selection criterion designed to optimize move selection by evaluating the potential impact of sampling groups of nodes simultaneously.

The BVPI Framework

Traditional Value of Information (VOI) approaches in search are often "blinkered," evaluating nodes in isolation. In many scenarios, a single additional rollout on a leaf node is insufficient to change the preferred action at the root, leading to a VOI of zero and stalling the search. BVPI overcomes this by calculating the expected gain in utility if perfect information were obtained for a batch of leaf nodes.

Figure 1: A search tree illustrating nodes with probabilistic value distributions. BVPI evaluates how information about these distributions can shift the optimal decision at the root.

While calculating the optimal set of nodes to maximize BVPI is NP-hard, the authors propose a deterministic approximation. To make this practical for real-time applications, they introduce C-VIBES (Conspiracy-based Value of Information Batch Efficient Selection). This method leverages "conspiracy numbers" to identify minimal sets of nodes that, if their values were updated, would collectively flip the current best move at the root.

Experimental Evaluation

The effectiveness of BVPI and C-VIBES was tested across two challenging domains: the stochastic Canadian Traveler Problem (CTP) and large-scale StarCraft Battles.

In the CTP domain, C-VIBES reduced path costs by over 15% compared to standard UCT. In StarCraft, C-VIBES achieved a dominant 77% win rate against UCT. A key finding was the algorithm's efficiency: C-VIBES with 3,000 rollouts outperformed UCT with 45,000 rollouts while running ten times faster. This efficiency is driven by the algorithm's ability to focus computational resources on "pivotal" node groups rather than uniform exploration.

Figure 6: Performance comparison across CTP and StarCraft. The data highlights that while "Full Tree" BVPI calculations are computationally prohibitive (timing out on larger trees), the Conspiracy-based approach (C-VIBES) maintains high performance with minimal overhead.

Conclusion

By shifting the focus from individual node rollouts to high-impact batches, BVPI and the C-VIBES algorithm provide a more robust framework for decision-making in complex, stochastic environments. The research demonstrates that metareasoning—thinking about where to search—can be significantly more valuable than simply increasing the volume of the search. Future work will look toward automating cost-benefit estimations and refining Bayesian updates to further enhance selection accuracy.

Summary updated

BibTeX
@inproceedings{shperberg2017monte,
  author = {Shahaf S. Shperberg and Solomon Eyal Shimony and Ariel Felner},
  title = {{Monte-Carlo Tree Search using Batch Value of Perfect Information}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2017},
}
Figure