Answers.Body: <p>The supplementary material of the AlphaZero <a href="https://www.science.org/doi/10.1126/science.aar6404" rel="noreferrer">paper</a> states the following:</p>
  <blockquote>
  <p>Unless
  otherwise specified, the training and search algorithm and parameters are identical to AlphaGo
  Zero.</p>
  </blockquote>
  <p>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 <a href="https://www.nature.com/articles/nature24270" rel="noreferrer">paper</a> states the following:</p>
  <blockquote>
  <p>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.</p>
  </blockquote>
  <p>Thus, <strong>the subtree and statistics are retained</strong>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-08-20T09:25:46.727Z
Answers.Text: 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.
Answers.UserDisplayName: KarelPeeters
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-08-20T20:03:53.413Z
Answers.Text: 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.
Answers.UserDisplayName: julian
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-08-24T10:44:35.930Z
Answers.Text: 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).
Answers.UserDisplayName: KarelPeeters
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-10-11T00:21:41.323Z
Answers.Text: @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](https://arxiv.org/pdf/1902.10565.pdf).
Answers.UserDisplayName: dshin
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-10-11T11:28:08.530Z
Answers.Text: @dshin That makes sense, thanks for clarifying!
Answers.UserDisplayName: KarelPeeters
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-08-19T19:21:17.930Z
Answers.LastActivityDate: 2022-08-19T19:21:17.930Z
Answers.UserDisplayName: DeepQZero
Body: <p>This question is regarding the Monte Carlo Tree Search (MCTS) algorithm presented in the AlphaZero <a href="https://www.science.org/doi/10.1126/science.aar6404" rel="nofollow noreferrer">paper</a> (<a href="https://arxiv.org/abs/1712.01815" rel="nofollow noreferrer">arXiv</a>). 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 &amp; 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.</p>
  <p><strong>Question</strong>: Once the next round of 800 MCTS simulations starts, do we discard the statistics from the previous tree and thereby start with a &quot;fresh&quot; subtree, or do we keep the statistics gathered from the previous round of simulations?</p>
  <p>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 &quot;restarting&quot; but it is not clear whether they restart after every round of 800 MCTS simulations or after each game is complete.</p>
  
Tags: <reinforcement-learning><monte-carlo-tree-search><alphazero>
Title: Does the AlphaZero algorithm keep the subtree statistics after each move during MCTS?
UserDisplayName: julian
ThreadText: # Does the AlphaZero algorithm keep the subtree statistics after each move during MCTS?
  
  (Asked by: username_0 on 2022-08-19)
  
  This question is regarding the Monte Carlo Tree Search (MCTS) algorithm presented in the AlphaZero [paper](https://www.science.org/doi/10.1126/science.aar6404) ([arXiv](https://arxiv.org/abs/1712.01815)). 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.
  
  **Tags:** reinforcement-learning, monte-carlo-tree-search, alphazero
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2022-08-19. Score: 5 | Accepted answer
  
  The supplementary material of the AlphaZero [paper](https://www.science.org/doi/10.1126/science.aar6404) 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](https://www.nature.com/articles/nature24270) 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**.
  
  > **Comments:**
  > **username_2**: 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.  
  > **username_0**: 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.  
  > **username_2**: 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).  
  > **username_3**: @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](https://arxiv.org/pdf/1902.10565.pdf).  
  > **username_2**: @username_3 That makes sense, thanks for clarifying!  
  
  ---
  
  