Monte-Carlo Tree Search using Batch Value of Perfect Information

Shahaf S. Shperberg, Solomon Eyal Shimony, Ariel Felner
Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, PMLR R15:541-550, 2017.

Abstract

This paper focuses on the selection phase of Monte- Carlo Tree Search (MCTS). We define batch value of perfect information (BVPI) in game trees as a generalization of value of computation as proposed by Russell and Wefald, and use it for selecting nodes to sample in MCTS. We show that computing the BVPI is NP-hard, but it can be approximated in polynomial time. In addition, we propose methods that intelligently find sets of fringe nodes with high BVPI, and quickly select nodes to sample from these sets. We apply our new BVPI methods to partial game trees, both in a stand-alone set of tests, and as a component of a full MCTS algorithm. Empirical results show that our BVPI methods outperform existing node-selection methods for MCTS in different scenarios.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR15-shperberg17a, title = {{M}onte-{C}arlo Tree Search using Batch Value of Perfect Information}, author = {Shperberg, Shahaf S. and Shimony, Solomon Eyal and Felner, Ariel}, booktitle = {Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence}, pages = {541--550}, year = {2017}, editor = {Elidan, Gal and Kersting, Kristian}, volume = {R15}, series = {Proceedings of Machine Learning Research}, month = {11--15 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r15/main/assets/shperberg17a/shperberg17a.pdf}, url = {https://proceedings.mlr.press/r15/shperberg17a.html}, abstract = {This paper focuses on the selection phase of Monte- Carlo Tree Search (MCTS). We define batch value of perfect information (BVPI) in game trees as a generalization of value of computation as proposed by Russell and Wefald, and use it for selecting nodes to sample in MCTS. We show that computing the BVPI is NP-hard, but it can be approximated in polynomial time. In addition, we propose methods that intelligently find sets of fringe nodes with high BVPI, and quickly select nodes to sample from these sets. We apply our new BVPI methods to partial game trees, both in a stand-alone set of tests, and as a component of a full MCTS algorithm. Empirical results show that our BVPI methods outperform existing node-selection methods for MCTS in different scenarios.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Monte-Carlo Tree Search using Batch Value of Perfect Information %A Shahaf S. Shperberg %A Solomon Eyal Shimony %A Ariel Felner %B Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2017 %E Gal Elidan %E Kristian Kersting %F pmlr-vR15-shperberg17a %I PMLR %P 541--550 %U https://proceedings.mlr.press/r15/shperberg17a.html %V R15 %X This paper focuses on the selection phase of Monte- Carlo Tree Search (MCTS). We define batch value of perfect information (BVPI) in game trees as a generalization of value of computation as proposed by Russell and Wefald, and use it for selecting nodes to sample in MCTS. We show that computing the BVPI is NP-hard, but it can be approximated in polynomial time. In addition, we propose methods that intelligently find sets of fringe nodes with high BVPI, and quickly select nodes to sample from these sets. We apply our new BVPI methods to partial game trees, both in a stand-alone set of tests, and as a component of a full MCTS algorithm. Empirical results show that our BVPI methods outperform existing node-selection methods for MCTS in different scenarios. %Z Reissued by PMLR on 04 October 2026.
APA
Shperberg, S.S., Shimony, S.E. & Felner, A.. (2017). Monte-Carlo Tree Search using Batch Value of Perfect Information. Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R15:541-550 Available from https://proceedings.mlr.press/r15/shperberg17a.html. Reissued by PMLR on 04 October 2026.

Related Material