Answers.Body: <p>Indeed here the single deterministic neural network evaluates both the policy and value functions during its so-called Monte Carlo Tree Search (MCTS) which doesn't explicitly guarantee the usual strict admissibility in the heuristic function sense as in A*. In essence via <em>self-play</em> and <em>DRL/SL</em> techniques to improve both policy and value functions reducing biases, the learned policy function minimizes wasted exploration and the learned value function reduces the need for <em>exhaustive rollouts</em> which is the core MC aspect of the traditional MCTS, thus all these mechanisms keep the heuristic <em>approximately admissible</em> and ensure that the search for the optimal move is thorough and strategic.</p>
  <p>Therefore the MC in MCTS here doesn’t refer exclusively to random rollouts at the leaf nodes, but broadly refers to the stochasticity in how the search tree is explored and updated in the sense that based upon the policy's probabilities over moves from the deterministic network the subsequent tree search selects nodes based on these probabilities introducing MC-like stochastic sampling.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-23T08:27:12.120Z
Answers.Text: I think this is right. But it seems more like "greedy exploration" than "MC-like" to me, there is not even any sort of pseudo-randomness there.
Answers.UserDisplayName: Tomek Czajka
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-23T21:19:46.850Z
Answers.Text: I can feel you regarding AlphaGo Zero's 'deterministic' greedy exploration instead of the traditional MC-like random sampling, especially at production inference time. Bear in mind, during the self-play phase the learned policy and value functions are not stable, annealed Dirichlet noise is added to the prior probabilities of the policy to ensure exploration of less-promising moves particularly those haven't been thoroughly explored based on their visit counts of the MCTS tree, along with another annealed temperature parameter to encourage exploration at earlier stage. Hope it clarifies now.
Answers.UserDisplayName: cinch
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-23T00:10:36.237Z
Answers.LastActivityDate: 2024-12-23T00:10:36.237Z
Answers.UserDisplayName: cinch
Answers.Body: <p><strong>No, MCTS is a stochastic algorithm</strong>, but this only happens during training.</p>
  <p>During the &quot;learning&quot; part of MCTS, the search space is randomly sampled, so nodes that are chosen to be expanded are chosen randomly but guided by a neural network (usually a value network or similar), at beginning of learning all nodes are expanded randomly since the neural network has not learned anything, and only after certain learning iterations the neural network contains some useful knowledge and this makes node expansion less stochastic.</p>
  <p>Maybe what confuses you is that once the model has been learned, then the MCTS execution (inference) is deterministic, since the relevant parts of the search space have been explored and are well known.</p>
  <p>Specific to Alpha Go Zero, it does have a training phase, as any MCTS algorithm there is an exploration and exploitation phase, the exploration phase can be seen  as training, but to be even more clear, the Alpha Go Zero paper shows plots of ELO rating vs Training time, I don't think you can be more clear than this that there is a training step.</p>
  <p>Also note that during exploration, the model initially does not know anything about the game, and only by exploring states, initially randomly, it can actually learn how to play the game. In the paper there are clear uses of probability and randomness, which should tell you that the algorithm is stochastic.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-22T20:08:20.520Z
Answers.Text: I don't understand what you mean by "training". MCTS doesn't have a separate "training" phase. But in any case, my question isn't about MCTS in general -- that obviously does have a stochastic element. My question is about AlphaGo Zero's variant of MCTS which to my understanding is fully deterministic.
Answers.UserDisplayName: Tomek Czajka
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-22T20:18:58.003Z
Answers.Text: @TomekCzajka I see what you mean, I will update my answer, maybe training is not the correct term, but MCTS does have exploration and exploitation, and exploration can be seen as a training or learning phase. And what I am describing is how MCTS is used with neural networks which is similar to how Alpha {Go/Zero} MCTS works.
Answers.UserDisplayName: Dr. Snoopy
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-22T21:05:50.480Z
Answers.Text: Regarding the added paragraphs: There is no separate "exploration and exploitation phase" in MCTS. MCTS has exploration and exploitation terms in its policy, but these are not separate phases of the algorithm. The exploration and exploitation terms are both deterministic formulas.
  
  The "training" the AlphaGo Zero paper talks about is a wholly different thing. It's about training the value and policy *networks*. It's not something that happens inside the MCTS algorithm.
  
  You're confusing MCTS with the whole training loop.
Answers.UserDisplayName: Tomek Czajka
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-22T21:08:56.567Z
Answers.Text: No, unfortunately you are wrong. Alpha Go Zero incorporates neural networks inside MCTS, so while the algorithm is exploring, the value and policy networks are being trained. You need data to train value and policy networks, and that data is generated using MCTS in an online fashion.
Answers.UserDisplayName: Dr. Snoopy
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-22T21:12:36.747Z
Answers.Text: AFAICT it's not true that the value and policy network (it's the same network) is being trained "while MCTS is exploring". What happens is that MCTS is run for a position (this is the only part my question is talking about), and *then*, after MCTS is done, the neural network is trained based on its outputs.
Answers.UserDisplayName: Tomek Czajka
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-22T21:19:29.683Z
Answers.Text: Sure, these things happen on steps, MCTS is run for a position, and this part incorporates stochasticity, since there is sampling of move probabilities, the paper is very clear in this aspect, it literally says: "and a move is played by sampling the search probabilities π_t."
Answers.UserDisplayName: Dr. Snoopy
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-22T21:24:20.957Z
Answers.Text: The sampling of a move is done after MCTS is done. The probabilities are computed based on the outputs of the MCTS algorithm. AFAICT the training loops looks like this:
  1. Run many iterations of MCTS to generate a value and move frequencies (I think this all happens deterministically -- hence my question).
  2. Based on move frequencies generated by MCTS, calculate a probability distrubution. 3. Sample a random move from that distribution and make that move. 4. Go back to 1. Then during game play only what they call "MCTS" is run, and there is no stochasticity involved, contradicting the name.
Answers.UserDisplayName: Tomek Czajka
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-22T21:27:07.110Z
Answers.Text: No, in the exploration phase of MCTS there is stochasticity, since sampling is used to generate moves, it is very typical in RL and other methods including MCTS that exploration is made by using randomness. You should read the self-play paragraph in the Methods section of the Alpha Go Zero paper which describes this. They add Dirichlet noise to prior probabilities to encourage exploration.
Answers.UserDisplayName: Dr. Snoopy
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-22T21:36:19.023Z
Answers.Text: Even in vanilla MCTS, there is no stochasticity in the exploration term. You take the maximum move score so far + an exploration term based on the number of times a move was taken. A deterministic formula. You can resolve ties randomly, but in AlphaGo Zero there are no ties there because the formula involves network output which is a floating point number, unlikely to get ties there. The stochasticity comes not from the tree policy (including the exploration term!), but from the *simulation* policy when you're already out of the tree. But AlphaGo Zero does not actually do such simulations.
Answers.UserDisplayName: Tomek Czajka
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-22T21:38:12.680Z
Answers.Text: You were asking about AlphaGo Zero, and I just pointed you to the stochastic exploration in the self-play in the paper, and there is an specific stochastic term that is not deterministic and makes exploration stochastic. This happens inside MCTS.
Answers.UserDisplayName: Dr. Snoopy
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-22T21:38:30.127Z
Answers.Text: The Dirichlet noise is another thing, but that's added once *before* any MCTS iterations are run at all. It would be weird if the MC part was referring to that. Especially since there is no Dirichlet noise during actual gameplay, and the same MCTS is used and they still refer to it as "MCTS". That's not what MC stands for in the original MCTS algorithm. The original algorithm is stochastic all the time, including during gameplay.
Answers.UserDisplayName: Tomek Czajka
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-22T21:42:19.143Z
Answers.Text: Sorry, I think the problem is that you completely misunderstand how MCTS works, you even made the (very wrong claim) that in vanilla MCTS the exploration is deterministic, which makes no sense. Or possibly you don't understand what makes a term stochastic.
Answers.UserDisplayName: Dr. Snoopy
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-22T18:20:08.770Z
Answers.LastActivityDate: 2024-12-22T20:54:43.070Z
Answers.LastEditDate: 2024-12-22T20:54:43.070Z
Answers.UserDisplayName: Dr. Snoopy
Body: <p>AlphaGo Zero utilizes an algorithm it calls &quot;Monte Carlo Tree Search&quot; in the papers, but it seems like the algorithm is fully deterministic since it doesn't utilize random playouts in the leaves of the tree, it just calls the value function that is a deterministic neural network. Is this correct? Isn't it therefore a giant misnomer to call it a &quot;Monte Carlo&quot; algorithm?</p>
  
Tags: <terminology><monte-carlo-tree-search><alphazero>
Title: AlphaGo Zero MCTS a misnomer?
UserDisplayName: Tomek Czajka
ThreadText: # AlphaGo Zero MCTS a misnomer?
  
  (Asked by: username_0 on 2024-12-19)
  
  AlphaGo Zero utilizes an algorithm it calls "Monte Carlo Tree Search" in the papers, but it seems like the algorithm is fully deterministic since it doesn't utilize random playouts in the leaves of the tree, it just calls the value function that is a deterministic neural network. Is this correct? Isn't it therefore a giant misnomer to call it a "Monte Carlo" algorithm?
  
  **Tags:** terminology, monte-carlo-tree-search, alphazero
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2024-12-23. Score: 1
  
  Indeed here the single deterministic neural network evaluates both the policy and value functions during its so-called Monte Carlo Tree Search (MCTS) which doesn't explicitly guarantee the usual strict admissibility in the heuristic function sense as in A\*. In essence via *self-play* and *DRL/SL* techniques to improve both policy and value functions reducing biases, the learned policy function minimizes wasted exploration and the learned value function reduces the need for *exhaustive rollouts* which is the core MC aspect of the traditional MCTS, thus all these mechanisms keep the heuristic *approximately admissible* and ensure that the search for the optimal move is thorough and strategic.
  
  Therefore the MC in MCTS here doesn’t refer exclusively to random rollouts at the leaf nodes, but broadly refers to the stochasticity in how the search tree is explored and updated in the sense that based upon the policy's probabilities over moves from the deterministic network the subsequent tree search selects nodes based on these probabilities introducing MC-like stochastic sampling.
  
  > **Comments:**
  > **username_0**: I think this is right. But it seems more like "greedy exploration" than "MC-like" to me, there is not even any sort of pseudo-randomness there.  
  > **username_1**: I can feel you regarding AlphaGo Zero's 'deterministic' greedy exploration instead of the traditional MC-like random sampling, especially at production inference time. Bear in mind, during the self-play phase the learned policy and value functions are not stable, annealed Dirichlet noise is added to the prior probabilities of the policy to ensure exploration of less-promising moves particularly those haven't been thoroughly explored based on their visit counts of the MCTS tree, along with another annealed temperature parameter to encourage exploration at earlier stage. Hope it clarifies now.  
  
  ---
  
  ### Answer by username_2 on 2024-12-22. Score: -1
  
  **No, MCTS is a stochastic algorithm**, but this only happens during training.
  
  During the "learning" part of MCTS, the search space is randomly sampled, so nodes that are chosen to be expanded are chosen randomly but guided by a neural network (usually a value network or similar), at beginning of learning all nodes are expanded randomly since the neural network has not learned anything, and only after certain learning iterations the neural network contains some useful knowledge and this makes node expansion less stochastic.
  
  Maybe what confuses you is that once the model has been learned, then the MCTS execution (inference) is deterministic, since the relevant parts of the search space have been explored and are well known.
  
  Specific to Alpha Go Zero, it does have a training phase, as any MCTS algorithm there is an exploration and exploitation phase, the exploration phase can be seen as training, but to be even more clear, the Alpha Go Zero paper shows plots of ELO rating vs Training time, I don't think you can be more clear than this that there is a training step.
  
  Also note that during exploration, the model initially does not know anything about the game, and only by exploring states, initially randomly, it can actually learn how to play the game. In the paper there are clear uses of probability and randomness, which should tell you that the algorithm is stochastic.
  
  > **Comments:**
  > **username_0**: I don't understand what you mean by "training". MCTS doesn't have a separate "training" phase. But in any case, my question isn't about MCTS in general -- that obviously does have a stochastic element. My question is about AlphaGo Zero's variant of MCTS which to my understanding is fully deterministic.  
  > **username_2**: @username_0 I see what you mean, I will update my answer, maybe training is not the correct term, but MCTS does have exploration and exploitation, and exploration can be seen as a training or learning phase. And what I am describing is how MCTS is used with neural networks which is similar to how Alpha {Go/Zero} MCTS works.  
  > **username_0**: Regarding the added paragraphs: There is no separate "exploration and exploitation phase" in MCTS. MCTS has exploration and exploitation terms in its policy, but these are not separate phases of the algorithm. The exploration and exploitation terms are both deterministic formulas.  The "training" the AlphaGo Zero paper talks about is a wholly different thing. It's about training the value and policy *networks*. It's not something that happens inside the MCTS algorithm.  You're confusing MCTS with the whole training loop.  
  > **username_2**: No, unfortunately you are wrong. Alpha Go Zero incorporates neural networks inside MCTS, so while the algorithm is exploring, the value and policy networks are being trained. You need data to train value and policy networks, and that data is generated using MCTS in an online fashion.  
  > **username_0**: AFAICT it's not true that the value and policy network (it's the same network) is being trained "while MCTS is exploring". What happens is that MCTS is run for a position (this is the only part my question is talking about), and *then*, after MCTS is done, the neural network is trained based on its outputs.  
  > **username_2**: Sure, these things happen on steps, MCTS is run for a position, and this part incorporates stochasticity, since there is sampling of move probabilities, the paper is very clear in this aspect, it literally says: "and a move is played by sampling the search probabilities π_t."  
  > **username_0**: The sampling of a move is done after MCTS is done. The probabilities are computed based on the outputs of the MCTS algorithm. AFAICT the training loops looks like this: 1. Run many iterations of MCTS to generate a value and move frequencies (I think this all happens deterministically -- hence my question). 2. Based on move frequencies generated by MCTS, calculate a probability distrubution. 3. Sample a random move from that distribution and make that move. 4. Go back to 1. Then during game play only what they call "MCTS" is run, and there is no stochasticity involved, contradicting the name.  
  > **username_2**: No, in the exploration phase of MCTS there is stochasticity, since sampling is used to generate moves, it is very typical in RL and other methods including MCTS that exploration is made by using randomness. You should read the self-play paragraph in the Methods section of the Alpha Go Zero paper which describes this. They add Dirichlet noise to prior probabilities to encourage exploration.  
  > **username_0**: Even in vanilla MCTS, there is no stochasticity in the exploration term. You take the maximum move score so far + an exploration term based on the number of times a move was taken. A deterministic formula. You can resolve ties randomly, but in AlphaGo Zero there are no ties there because the formula involves network output which is a floating point number, unlikely to get ties there. The stochasticity comes not from the tree policy (including the exploration term!), but from the *simulation* policy when you're already out of the tree. But AlphaGo Zero does not actually do such simulations.  
  > **username_2**: You were asking about AlphaGo Zero, and I just pointed you to the stochastic exploration in the self-play in the paper, and there is an specific stochastic term that is not deterministic and makes exploration stochastic. This happens inside MCTS.  
  > **username_0**: The Dirichlet noise is another thing, but that's added once *before* any MCTS iterations are run at all. It would be weird if the MC part was referring to that. Especially since there is no Dirichlet noise during actual gameplay, and the same MCTS is used and they still refer to it as "MCTS". That's not what MC stands for in the original MCTS algorithm. The original algorithm is stochastic all the time, including during gameplay.  
  > **username_2**: Sorry, I think the problem is that you completely misunderstand how MCTS works, you even made the (very wrong claim) that in vanilla MCTS the exploration is deterministic, which makes no sense. Or possibly you don't understand what makes a term stochastic.  
  
  ---
  
  