678 / 2024-05-08 17:57:28

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

Monte Carlo Tree Search,Node Selection Policy,Neural Network,Ranking and Selection

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 Bound for Trees (UCT) policy, we formulate the node selection problem in NN-MCTS as a Ranking and Selection (R\&S) problem and provide a new node selection policy that efficiently allocates a limited search budget to maximize the probability of correctly selecting the best action at each node. The value network and policy network 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 methods.