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 gener- alization of value of computation as proposed by Rus- sell and Wefald, and use it for selecting nodes to sam- ple 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 intelli- gently find sets of fringe nodes with high BVPI, and quickly select nodes to sample from these sets. We ap- ply 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 gener- alization of value of computation as proposed by Rus- sell and Wefald, and use it for selecting nodes to sam- ple 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 intelli- gently find sets of fringe nodes with high BVPI, and quickly select nodes to sample from these sets. We ap- ply 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 gener- alization of value of computation as proposed by Rus- sell and Wefald, and use it for selecting nodes to sam- ple 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 intelli- gently find sets of fringe nodes with high BVPI, and quickly select nodes to sample from these sets. We ap- ply 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