Answers.Body: <p>I had the same question and found this page, then I also started to look at the pseudo-code of <a href="https://www.science.org/doi/10.1126/science.aar6404" rel="nofollow noreferrer">Supplementary Materials</a>. The code of the computation of the UCB score is as followed:</p>
  <pre><code># The score for a node is based on its value, plus an exploration bonus based on
  # the prior.
  def ucb_score(config: AlphaZeroConfig, parent: Node, child: Node):
    pb_c = math.log((parent.visit_count + config.pb_c_base + 1) /
                    config.pb_c_base) + config.pb_c_init
    pb_c *= math.sqrt(parent.visit_count) / (child.visit_count + 1)
  
    prior_score = pb_c * child.prior
    value_score = child.value()
    return prior_score + value_score
  </code></pre>
  <p>I was very confused since it is different from the formula described in the paper, until I found the UCB formula in the paper of <a href="https://arxiv.org/pdf/1911.08265.pdf" rel="nofollow noreferrer">MuZero</a>:</p>
  <p><a href="https://i.sstatic.net/umit8.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/umit8.png" alt="enter image description here" /></a></p>
  <p>It is clear that the pseudocode of AlphaZero mistook the UCB formula of MuZero.</p>
  <p>As for the original question, the sum of all the visit count numbers of the childen is implemented as the visit count of the parent node, which is at least 1, since it is visited as it is expanded (evaluated), as you can see in the code of the search:</p>
  <pre><code># Core Monte Carlo Tree Search algorithm.
  # To decide on an action, we run N simulations, always starting at the root of
  # the search tree and traversing the tree according to the UCB formula until we
  # reach a leaf node.
  def run_mcts(config: AlphaZeroConfig, game: Game, network: Network):
    root = Node(0)
    evaluate(root, game, network)
    add_exploration_noise(config, root)
  
    for _ in range(config.num_simulations):
      node = root
      scratch_game = game.clone()
      search_path = [node]
  
      while node.expanded():
        action, node = select_child(config, node)
        scratch_game.apply(action)
        search_path.append(node)
  
      value = evaluate(node, scratch_game, network)
      backpropagate(search_path, value, scratch_game.to_play())
    return select_action(config, game, root), root
  </code></pre>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-07-18T03:07:08.823Z
Answers.LastActivityDate: 2023-07-18T03:07:08.823Z
Answers.UserDisplayName: leodeng
Answers.Body: <p>I looked at the Python pseudo-code attached to the Data S1 of the <a href="https://science.sciencemag.org/content/suppl/2018/12/05/362.6419.1140.DC1" rel="noreferrer">Supplementary Materials</a> of the AlphaZero paper. Here is my findings:</p>
  <ul>
  <li>Contrary to the paper, AlphaZero does not store <span class="math-container">$\{N(s, a), W(S, a), Q(s, a), P(s, a)\}$</span> statistics for each edge <span class="math-container">$(s,a)$</span>. Instead, AlphaZero stores <span class="math-container">$\{N(s), W(S), Q(s), P(s)\}$</span> statistics for each node <span class="math-container">$s$</span>.</li>
  <li>When a leaf node <span class="math-container">$S_L$</span> is expanded, it's visit count, value scores, and action policies are immediately updated in <span class="math-container">$\{N(s), W(S), Q(s), P(s)\}$</span>, so <span class="math-container">$N(s)$</span> is at least <span class="math-container">$1$</span>. This is why in the paper, the backprop step updates for all time steps <span class="math-container">$t \le L$</span> rather than <span class="math-container">$t &lt; L$</span>. It makes sense to update <span class="math-container">$s_L$</span> even though there is no corresponding <span class="math-container">$a_L$</span> to pair it with.</li>
  <li>Therefore, when a new leaf node is expanded, the value <span class="math-container">$U(s, a)$</span> of a child of that leaf node will be nonzero, since <span class="math-container">$\sqrt{\sum_b N(s,b)}$</span> is actually computed as <span class="math-container">$N(s_{parent})$</span> in the code, which is at least 1.</li>
  <li>Oddly enough, I think there might be a bug in the pseudocode, because at the beginning on the first iteration (starting at the root node), <span class="math-container">$U(s,a) = 0$</span> for all child nodes of the root node. This is because at the first iteration, <span class="math-container">$N(s_{root}) = 0$</span>. The value of all child nodes will be <span class="math-container">$0$</span>, and since the authors chose to break ties according to Python's <code>max</code> function, the algorithm simply chooses the first element it finds in case of a tie.</li>
  <li>After the first iteration, <span class="math-container">$N(s_{root}) &gt; 0$</span> and so <span class="math-container">$U(s,a) \neq 0$</span> and things proceed as normal since the backprop step will have updated the visit count of the root node. So this possible bug/unintuitive behavior only affects the first iteration. It is extremely minor and insignificant, and does not affect the outcome of the MCTS, which is probably why it went unnoticed.</li>
  </ul>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-31T20:24:23.490Z
Answers.Text: I'm good on everything except the third bullet point, which seems very counterintuitive and not how the authors described it in the paper. It sounds like you're saying that every time we run the PUCT algorithm, $\sqrt{\sum_b N(s, b)}$ uses the visit count of the parent node $s_{L-1}$ and in the denominator, $1 + N(s, a)$ is the visit count of the new leaf node $s_L$? I thought the whole point of the $U$ term in PUCT was to encourage exploration by selecting nodes that have been visited less, in which case the numerator should be counting the total number of visits to children of $s_{L-1}$.
Answers.UserDisplayName: sb3
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-31T20:26:37.077Z
Answers.Text: Yes, $\sqrt{\sum_b N(s,b)}$ is actually just the visit count of the parent, and $N(s,a)$ is just the visit count of the current node. If the current selection is looking at a leaf node, then yes the parent would be $s_{L-1}$ and current node would be $s_L$. I was surprised as well because this differs from the equation in the paper, but it's how it is coded.
Answers.UserDisplayName: user3667125
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-31T20:28:56.570Z
Answers.Text: To me, this defeats the purpose and intuition behind the PUCT algorithm. How are we encouraging exploration with the $U$ term if in the numerator, we are counting the visits to the parent node $s_{L-1}$? Or maybe it's only the denominator that matters for exploration?
Answers.UserDisplayName: sb3
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-31T20:29:58.177Z
Answers.Text: The denominator is what encourages exploration. All the sibling nodes have the same numerator (since they have the same parent), but the ones that are less visited have a smaller denominator, so the overall fraction is larger.
Answers.UserDisplayName: user3667125
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-31T20:31:45.207Z
Answers.Text: I guess it still does what it was intended to do, albeit not quite the way the algorithm is described in the paper. I wish this was clarified but, oh well.
Answers.UserDisplayName: sb3
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-31T20:40:47.800Z
Answers.Text: Follow up question. When starting with just the root node, since there is no parent, how will the denominator of the $U$ term be calculated? Is this where adding an epsilon comes into play? EDIT: Nvm, I think you answered this in the 4th bullet point.
Answers.UserDisplayName: sb3
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-31T20:46:03.370Z
Answers.Text: MCTS never does the selection phase on the root node. The root node is expanded (i.e. $(v, \pi_{s_0})$ is computed) upon initialization. So on the first iteration, MCTS begins by computing the selection phase over the children of the root node. So it starts with $s_1$, and we can compute $\sqrt{\sum_b N(s,b)}$ and $N(s,a)$ normally from there.
Answers.UserDisplayName: user3667125
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-31T22:37:46.133Z
Answers.Text: Last question. When self-play returns a tuple $(s_t, \pi_t, R_t)$ for the learn() step, I believe the stochastic policy $\pi_t$ that is returned is $\frac{N(s, \cdot)}{\sqrt{\sum_b N(s, b)}}$. Based on what we discussed above, is it safe to interpret this as the visit count to some arbitrary child node divided by the visit count to the parent node?
Answers.UserDisplayName: sb3
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-31T22:41:12.333Z
Answers.Text: By the way, I just realized that the sum of the visits to all children nodes of some parent node is inherently equivalent to the visit counts to that parent node. So I think the algorithm is implemented correctly after all!
Answers.UserDisplayName: sb3
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-31T23:18:48.537Z
Answers.Text: Yes to your question. And regarding the last comment -- $N(s_{parent}) = \sum_i N(s_{child_i}) + 1$. This is because when the parent node is just expanded  (the second bullet in my answer), the backprop step updates the visit count of that parent node, so $N(s_{parent})$ starts at value $1$. Then the visit count is incremented at each child visit. So that's why it always has a $+1$ in there. The only exception to this is the root node, which doesn't have the $+1$ term, which is why in my fourth bullet I think it's a bug.
Answers.UserDisplayName: user3667125
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-08T12:43:28.413Z
Answers.Text: @user3667125 I don't think it's a bug, when the Root Node has a visit count of 0, you aren't even going to loop over the children anyway, the Root Node is a leaf so the recursion ends right there. You're first going to expand the Root Node (Calling the NN on the Root Node for the first time, to give it a policy and initial Q). Then, the visit count will be 1, and on the next iteration you'll be able to select a child properly.
Answers.UserDisplayName: Nicholas Pipitone
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-30T23:58:29.103Z
Answers.LastActivityDate: 2020-12-31T00:19:17.020Z
Answers.LastEditDate: 2020-12-31T00:19:17.020Z
Answers.UserDisplayName: user3667125
Body: <p>From the AlphaGo Zero paper, during MCTS, statistics for each new node are initialized as such:</p>
  <blockquote>
  <p><span class="math-container">${N(s_L, a) = 0, W (s_L, a) = 0, Q(s_L, a) = 0, P (s_L, a) = p_a}$</span>.</p>
  </blockquote>
  <p>The PUCT algorithm for selecting the best child node is <span class="math-container">$a_t = argmax(Q(s,a) + U(s,a))$</span>, where <span class="math-container">$U(s,a) = c_{puct} P(s,a) \frac{\sqrt{\sum_b N(s,b)}}{1 + N(s, a)}$</span>.</p>
  <p>If we start from scratch with a tree that only contains the root node and no children have been visited yet, then this should evaluate to 0 for all actions <span class="math-container">$a$</span> that we can take from the root node. Do we then simply uniformly sample an action to take?</p>
  <p>Also, during the expand() step when we add an unvisited node <span class="math-container">$s_L$</span> to the tree, this node's children will also have not been visited, and we run into the same problem where PUCT will return 0 for all actions. Do we do the same uniform sampling here as well?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-30T07:51:05.643Z
Comments.Text: This is a very good question. Related to this is the backprop step (which influences the $N(s,b)$ statistic). The original paper states that the backprop step updates for all time steps $t \le L$, but it doesn't make sense to update $(s_L, a_L)$ because $s_L$ is the leaf node that we just expanded: what is $a_L$, do we uniformly pick an action at random? Or does the author mean to backprop for all time steps $t < L$ instead? This code (https://github.com/suragnair/alpha-zero-general/blob/master/MCTS.py) does backprop only on $t < L$, not $t \le L$.
Comments.UserDisplayName: user3667125
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-30T07:57:33.130Z
Comments.Text: Additionally, (to answer your question) the code above adds a small epsilon $\epsilon = 1e-8$ to $\sum_b N(s,b)$ so that $U(s,a) \neq 0$ and does the selection proportional to the prior $P(s,a)$, but I cannot verify if the AlphaZero authors do it this way as well, so I cannot submit that as an answer.
Comments.UserDisplayName: user3667125
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-30T19:28:14.743Z
Comments.Text: While I can't verify whether the original paper does this or not, backprop'ing $t<L$ and adding that epsilon seems reasonable. It makes no sense to use some other arbitrary sampling scheme when we have priors already.
Comments.UserDisplayName: sb3
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-30T23:03:10.310Z
Comments.Text: It's a bit more complicated, because AlphaZero's MCTS algorithm is a modified version of a true MCTS algorithm (AlphaZero doesn't actually use a true MCTS because it doesn't use Monte-Carlo simulations to roll out the entire game). The true MCTS algorithm does select a node at random, so it would make sense for AlphaZero to also select a $a_L$ at random if it stays true to MCTS. See https://www.analyticsvidhya.com/blog/2019/01/monte-carlo-tree-search-introduction-algorithm-deepmind-alphago/ for more info on how the true MCTS selects the first node.
Comments.UserDisplayName: user3667125
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-30T23:58:46.383Z
Comments.Text: I did some more research, and found the answer. See my post below.
Comments.UserDisplayName: user3667125
Tags: <deep-rl><monte-carlo-tree-search><alphazero>
Title: How does AlphaZero's MCTS work when starting from the root node?
UserDisplayName: sb3
ThreadText: # How does AlphaZero's MCTS work when starting from the root node?
  
  (Asked by: username_0 on 2020-12-30)
  
  From the AlphaGo Zero paper, during MCTS, statistics for each new node are initialized as such:
  
  > ${N(s\_L, a) = 0, W (s\_L, a) = 0, Q(s\_L, a) = 0, P (s\_L, a) = p\_a}$.
  
  The PUCT algorithm for selecting the best child node is $a\_t = argmax(Q(s,a) + U(s,a))$, where $U(s,a) = c\_{puct} P(s,a) \frac{\sqrt{\sum\_b N(s,b)}}{1 + N(s, a)}$.
  
  If we start from scratch with a tree that only contains the root node and no children have been visited yet, then this should evaluate to 0 for all actions $a$ that we can take from the root node. Do we then simply uniformly sample an action to take?
  
  Also, during the expand() step when we add an unvisited node $s\_L$ to the tree, this node's children will also have not been visited, and we run into the same problem where PUCT will return 0 for all actions. Do we do the same uniform sampling here as well?
  
  **Tags:** deep-rl, monte-carlo-tree-search, alphazero
  > **Comments:**
  > **username_1**: This is a very good question. Related to this is the backprop step (which influences the $N(s,b)$ statistic). The original paper states that the backprop step updates for all time steps $t \le L$, but it doesn't make sense to update $(s_L, a_L)$ because $s_L$ is the leaf node that we just expanded: what is $a_L$, do we uniformly pick an action at random? Or does the author mean to backprop for all time steps $t < L$ instead? This code (https://github.com/suragnair/alpha-zero-general/blob/master/MCTS.py) does backprop only on $t < L$, not $t \le L$.  
  > **username_1**: Additionally, (to answer your question) the code above adds a small epsilon $\epsilon = 1e-8$ to $\sum_b N(s,b)$ so that $U(s,a) \neq 0$ and does the selection proportional to the prior $P(s,a)$, but I cannot verify if the AlphaZero authors do it this way as well, so I cannot submit that as an answer.  
  > **username_0**: While I can't verify whether the original paper does this or not, backprop'ing $t<L$ and adding that epsilon seems reasonable. It makes no sense to use some other arbitrary sampling scheme when we have priors already.  
  > **username_1**: It's a bit more complicated, because AlphaZero's MCTS algorithm is a modified version of a true MCTS algorithm (AlphaZero doesn't actually use a true MCTS because it doesn't use Monte-Carlo simulations to roll out the entire game). The true MCTS algorithm does select a node at random, so it would make sense for AlphaZero to also select a $a_L$ at random if it stays true to MCTS. See https://www.analyticsvidhya.com/blog/2019/01/monte-carlo-tree-search-introduction-algorithm-deepmind-alphago/ for more info on how the true MCTS selects the first node.  
  > **username_1**: I did some more research, and found the answer. See my post below.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2020-12-30. Score: 6 | Accepted answer
  
  I looked at the Python pseudo-code attached to the Data S1 of the [Supplementary Materials](https://science.sciencemag.org/content/suppl/2018/12/05/362.6419.1140.DC1) of the AlphaZero paper. Here is my findings:
  
  * Contrary to the paper, AlphaZero does not store $\{N(s, a), W(S, a), Q(s, a), P(s, a)\}$ statistics for each edge $(s,a)$. Instead, AlphaZero stores $\{N(s), W(S), Q(s), P(s)\}$ statistics for each node $s$.
  * When a leaf node $S\_L$ is expanded, it's visit count, value scores, and action policies are immediately updated in $\{N(s), W(S), Q(s), P(s)\}$, so $N(s)$ is at least $1$. This is why in the paper, the backprop step updates for all time steps $t \le L$ rather than $t < L$. It makes sense to update $s\_L$ even though there is no corresponding $a\_L$ to pair it with.
  * Therefore, when a new leaf node is expanded, the value $U(s, a)$ of a child of that leaf node will be nonzero, since $\sqrt{\sum\_b N(s,b)}$ is actually computed as $N(s\_{parent})$ in the code, which is at least 1.
  * Oddly enough, I think there might be a bug in the pseudocode, because at the beginning on the first iteration (starting at the root node), $U(s,a) = 0$ for all child nodes of the root node. This is because at the first iteration, $N(s\_{root}) = 0$. The value of all child nodes will be $0$, and since the authors chose to break ties according to Python's `max` function, the algorithm simply chooses the first element it finds in case of a tie.
  * After the first iteration, $N(s\_{root}) > 0$ and so $U(s,a) \neq 0$ and things proceed as normal since the backprop step will have updated the visit count of the root node. So this possible bug/unintuitive behavior only affects the first iteration. It is extremely minor and insignificant, and does not affect the outcome of the MCTS, which is probably why it went unnoticed.
  
  > **Comments:**
  > **username_0**: I'm good on everything except the third bullet point, which seems very counterintuitive and not how the authors described it in the paper. It sounds like you're saying that every time we run the PUCT algorithm, $\sqrt{\sum_b N(s, b)}$ uses the visit count of the parent node $s_{L-1}$ and in the denominator, $1 + N(s, a)$ is the visit count of the new leaf node $s_L$? I thought the whole point of the $U$ term in PUCT was to encourage exploration by selecting nodes that have been visited less, in which case the numerator should be counting the total number of visits to children of $s_{L-1}$.  
  > **username_1**: Yes, $\sqrt{\sum_b N(s,b)}$ is actually just the visit count of the parent, and $N(s,a)$ is just the visit count of the current node. If the current selection is looking at a leaf node, then yes the parent would be $s_{L-1}$ and current node would be $s_L$. I was surprised as well because this differs from the equation in the paper, but it's how it is coded.  
  > **username_0**: To me, this defeats the purpose and intuition behind the PUCT algorithm. How are we encouraging exploration with the $U$ term if in the numerator, we are counting the visits to the parent node $s_{L-1}$? Or maybe it's only the denominator that matters for exploration?  
  > **username_1**: The denominator is what encourages exploration. All the sibling nodes have the same numerator (since they have the same parent), but the ones that are less visited have a smaller denominator, so the overall fraction is larger.  
  > **username_0**: I guess it still does what it was intended to do, albeit not quite the way the algorithm is described in the paper. I wish this was clarified but, oh well.  
  > **username_0**: Follow up question. When starting with just the root node, since there is no parent, how will the denominator of the $U$ term be calculated? Is this where adding an epsilon comes into play? EDIT: Nvm, I think you answered this in the 4th bullet point.  
  > **username_1**: MCTS never does the selection phase on the root node. The root node is expanded (i.e. $(v, \pi_{s_0})$ is computed) upon initialization. So on the first iteration, MCTS begins by computing the selection phase over the children of the root node. So it starts with $s_1$, and we can compute $\sqrt{\sum_b N(s,b)}$ and $N(s,a)$ normally from there.  
  > **username_0**: Last question. When self-play returns a tuple $(s_t, \pi_t, R_t)$ for the learn() step, I believe the stochastic policy $\pi_t$ that is returned is $\frac{N(s, \cdot)}{\sqrt{\sum_b N(s, b)}}$. Based on what we discussed above, is it safe to interpret this as the visit count to some arbitrary child node divided by the visit count to the parent node?  
  > **username_0**: By the way, I just realized that the sum of the visits to all children nodes of some parent node is inherently equivalent to the visit counts to that parent node. So I think the algorithm is implemented correctly after all!  
  > **username_1**: Yes to your question. And regarding the last comment -- $N(s_{parent}) = \sum_i N(s_{child_i}) + 1$. This is because when the parent node is just expanded  (the second bullet in my answer), the backprop step updates the visit count of that parent node, so $N(s_{parent})$ starts at value $1$. Then the visit count is incremented at each child visit. So that's why it always has a $+1$ in there. The only exception to this is the root node, which doesn't have the $+1$ term, which is why in my fourth bullet I think it's a bug.  
  > **username_3**: @user3667125 I don't think it's a bug, when the Root Node has a visit count of 0, you aren't even going to loop over the children anyway, the Root Node is a leaf so the recursion ends right there. You're first going to expand the Root Node (Calling the NN on the Root Node for the first time, to give it a policy and initial Q). Then, the visit count will be 1, and on the next iteration you'll be able to select a child properly.  
  
  ---
  
  ### Answer by username_2 on 2023-07-18. Score: 1
  
  I had the same question and found this page, then I also started to look at the pseudo-code of Supplementary Materials. The code of the computation of the UCB score is as followed:
  # The score for a node is based on its value, plus an exploration bonus based on
  # the prior.
  def ucb_score(config: AlphaZeroConfig, parent: Node, child: Node):
    pb_c = math.log((parent.visit_count + config.pb_c_base + 1) /
                    config.pb_c_base) + config.pb_c_init
    pb_c *= math.sqrt(parent.visit_count) / (child.visit_count + 1)
  
    prior_score = pb_c * child.prior
    value_score = child.value()
    return prior_score + value_score
  
  I was very confused since it is different from the formula described in the paper, until I found the UCB formula in the paper of MuZero:
  
  It is clear that the pseudocode of AlphaZero mistook the UCB formula of MuZero.
  As for the original question, the sum of all the visit count numbers of the childen is implemented as the visit count of the parent node, which is at least 1, since it is visited as it is expanded (evaluated), as you can see in the code of the search:
  # Core Monte Carlo Tree Search algorithm.
  # To decide on an action, we run N simulations, always starting at the root of
  # the search tree and traversing the tree according to the UCB formula until we
  # reach a leaf node.
  def run_mcts(config: AlphaZeroConfig, game: Game, network: Network):
    root = Node(0)
    evaluate(root, game, network)
    add_exploration_noise(config, root)
  
    for _ in range(config.num_simulations):
      node = root
      scratch_game = game.clone()
      search_path = [node]
  
      while node.expanded():
        action, node = select_child(config, node)
        scratch_game.apply(action)
        search_path.append(node)
  
      value = evaluate(node, scratch_game, network)
      backpropagate(search_path, value, scratch_game.to_play())
    return select_action(config, game, root), root
  
  
  ---
  
  