4
$\begingroup$

This question is regarding the Monte Carlo Tree Search (MCTS) algorithm presented in the AlphaZero paper (arXiv). As described in the paper, each MCTS used 800 simulations to determine the next action. This process builds a search subtree downwards from the root note. During this process, statistics about the nodes (e.g. values & visit counts) are updated in backward passes upwards through the tree. After all 800 simulations are complete, the most promising child node is selected (i.e. the node with the most visits, normalized by temperature), and then 800 new MCTS simulations are started using the selected child node as the new root node.

Question: Once the next round of 800 MCTS simulations starts, do we discard the statistics from the previous tree and thereby start with a "fresh" subtree, or do we keep the statistics gathered from the previous round of simulations?

I have found several tutorials/blog posts/repositories that implement either of these options and are contradictory. Furthermore, the wording in the paper seems ambiguous as they speak of "restarting" but it is not clear whether they restart after every round of 800 MCTS simulations or after each game is complete.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
5
$\begingroup$

The supplementary material of the AlphaZero paper states the following:

Unless otherwise specified, the training and search algorithm and parameters are identical to AlphaGo Zero.

I didn't see any mention of whether or not the subtree was kept when reading the rest of the AlphaZero paper; therefore, we defer to the AlphaGo Zero algorithm. The appendix of the AlphaGo Zero paper states the following:

The search tree is reused at subsequent time steps: the child node corresponding to the played action becomes the new root node; the subtree below this child is retained along with all its statistics, while the remainder of the tree is discarded.

Thus, the subtree and statistics are retained.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Interesting, since keeping the subtree weakens the effect of the Dirichlet noise added for exploration. Another solution is to rebuild the tree from scratch each time but cache the neural net evaluations, that's the only expensive part anyway. $\endgroup$
    – Todd Sewell
    Aug 20, 2022 at 9:25
  • $\begingroup$ I wouldn't be able to say anything about Dirichlet noise but intuitively I think it makes sense to keep it. In fact, the only reason I asked the question is because I've seen online tutorials that don't keep it, which made me suspicious as I find that intuitively keeping it makes more sense. $\endgroup$
    – julian
    Aug 20, 2022 at 20:03
  • 1
    $\begingroup$ Both real-world A0 implementations I'm somewhat familiar with (KataGo and LeelaChessZero) don't reuse the tree but instead cache NN evaluations, specifically because some details of the algorithm are different for the root node of the tree (dirichlet noise, and newer features like first-play urgency and policy softmax temperature). $\endgroup$
    – Todd Sewell
    Aug 24, 2022 at 10:44
  • 1
    $\begingroup$ @ToddSewell I spoke with the author of KataGo recently, and confirmed that KataGo does in fact reuse the tree whenever the exploration elements (like Dirichlet noise) are deactivated. This is the case both during inference mode (i.e., outside of the self-play context), and also during the 75% of self-play turns that use so-called "fast search" - see Section 3.1 of the KataGo paper. $\endgroup$
    – dshin
    Oct 11, 2022 at 0:21
  • $\begingroup$ @dshin That makes sense, thanks for clarifying! $\endgroup$
    – Todd Sewell
    Oct 11, 2022 at 11:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .