An Efficient Node Selection Policy for Monte Carlo Tree Search with Neural Networks

Xiaotian Liu (), Yijie Peng (), Gongbo Zhang () and Ruihan Zhou ()
Additional contact information
Xiaotian Liu: PKU-Wuhan Institute for Artificial Intelligence, Guanghua School of Management, Peking University, Beijing 100871, China; and Xiangjiang Laboratory, Changsha 410000, China
Yijie Peng: PKU-Wuhan Institute for Artificial Intelligence, Guanghua School of Management, Peking University, Beijing 100871, China; and Xiangjiang Laboratory, Changsha 410000, China
Gongbo Zhang: PKU-Wuhan Institute for Artificial Intelligence, Guanghua School of Management, Peking University, Beijing 100871, China; and Xiangjiang Laboratory, Changsha 410000, China
Ruihan Zhou: PKU-Wuhan Institute for Artificial Intelligence, Guanghua School of Management, Peking University, Beijing 100871, China; and Xiangjiang Laboratory, Changsha 410000, China

INFORMS Journal on Computing, 2025, vol. 37, issue 4, 785-807

Abstract: Monte Carlo tree search (MCTS) has been gaining increasing popularity, and the success of AlphaGo has prompted a new trend of incorporating a value network and a policy network constructed with neural networks into MCTS, namely, NN-MCTS. In this work, motivated by the shortcomings of the widely used upper confidence bounds applied to trees (UCT) policy, we formulate the node selection problem in NN-MCTS as a multistage ranking and selection (R&S) problem and propose a node selection policy that efficiently allocates a limited search budget to maximize the probability of correctly selecting the best action at the root state. The value and policy networks in NN-MCTS further improve the performance of the proposed node selection policy by providing prior knowledge and guiding the selection of the final action, respectively. Numerical experiments on two board games and an OpenAI task demonstrate that the proposed method outperforms the UCT policy used in AlphaGo Zero and MuZero, implying the potential of constructing node selection policies in NN-MCTS with R&S procedures.

Keywords: Monte Carlo tree search; node selection policy; neural networks; ranking and selection (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2023.0307 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:37:y:2025:i:4:p:785-807

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().