Recursive Monte-Carlo Tree Search

We introduce a recursive AlphaZero style Monte--Carlo tree search algorithm, "RMCTS". It first generates the search tree using prior policies, and then recursively re-estimates action values by using the regularized optimal posterior policies from ``Monte--Carlo tree search as regularized policy optimization'' (Grill et al., 2020) at each node of the search tree, starting from the leaves and working back up to the root. We find that RMCTS matches or exceeds the quality of AlphaZero's MCTS-UCB in a tiny fraction of the time.

We introduce Recursive Monte--Carlo Tree Search "RMCTS", a drop-in replacement for AlphaZero-style Monte--Carlo tree search. The main idea of RMCTS is to do regularized policy optimization at every node in the search tree, setting estimated action values to be the expected rewards following the posterior policy. By nature of this design, it is possible to explore the search tree in a breadth-first manner, thus massively parallelizing the neural network inferences at each level of the tree. Hence RMCTS is significantly faster than AlphaZero's MCTS. In this paper we compare RMCTS to MCTS by exploring their relative performance on three games; Dots-and-Boxes, and Connect-4, and Othello.