Answers.Body: <p>To understand how AlphaGo Zero performs parallel simulations think of each simulation as a separate agent that interacts with the search tree. Each agent starts from the root node and selects an action according to the statistics in the tree, such as:</p>
  <p>(1) mean action value (Q),
  (2) visit count (N), and;
  (3) prior probability (P).</p>
  <p>The agent then follows the action to the next node and repeats the process until it reaches a leaf node. At the leaf node, the agent evaluates the state using the neural network and propagates the value back to the root node, updating the statistics along the way.</p>
  <p>However, since there are multiple agents running in parallel, they may not have access to the most updated statistics in the tree. For example, one agent may select an action that another agent has already explored and updated its value. To avoid this problem, AlphaGo Zero uses a <a href="https://github.com/initial-h/AlphaZero_Gomoku_MPI" rel="nofollow noreferrer">virtual loss mechanism</a> that temporarily reduces the Q value of a node when an agent visits it. This discourages other agents from selecting the same node until the first agent finishes its evaluation and restores the Q value. This way, each agent can explore different parts of the tree without waiting for each other.</p>
  <p><a href="https://web.stanford.edu/%7Esurag/posts/alphazero.html" rel="nofollow noreferrer">Pseudo code</a> of the parallel search engine</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-09-26T16:46:12.123Z
Answers.LastActivityDate: 2023-09-26T16:46:12.123Z
Answers.UserDisplayName: DSarkar
Answers.Body: <ol>
  <li>you have a board in front of you</li>
  <li>you pick N most likely moves from the optimal policy (likely = doing this move you are more likely to win)</li>
  <li>you create N threads</li>
  <li>in each thread, you simulate doing one of these moves, and in parallel, you can go on with this reasoning recursively</li>
  </ol>
  <p>Once you reach the terminal node, or you finished you time budget, you use the V function to approximate the result, and you back-propagate the information using usual methods</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-09-26T11:44:00.467Z
Answers.LastActivityDate: 2023-09-26T11:44:00.467Z
Answers.UserDisplayName: Alberto
Body: <p>I am trying to better understand the article &quot;Mastering the Game of Go without Human Knowledge&quot; (<a href="https://faculty.washington.edu/jwilker/559/2018/go.pdf" rel="nofollow noreferrer">link</a>) and I'm confused about the parallel implementation of Monte-Carlo-Tree-Search.</p>
  <p>On page 25 under &quot;Search Algorithm&quot;, the authors say (emphasis mine)</p>
  <blockquote>
  <p>AlphaGo Zero uses a much simpler variant of the asynchronous policy and
  value MCTS algorithm (APV-MCTS)</p>
  </blockquote>
  <blockquote>
  <p>Multiple simulations are executed <strong>in parallel</strong> on separate search threads.</p>
  </blockquote>
  <p>On page 26 under &quot;Select&quot;,</p>
  <blockquote>
  <p>an action is selected according to the statistics in the search tree</p>
  </blockquote>
  <p>There are some math details on how an action is selected based on (among other things) the mean action value (Q).</p>
  <p>I find this confusing because the choice of action at each simulation depends on the statistics of the previous simulations (the value of Q).</p>
  <p>How can simulations be run in parallel given that the choice of action in each simulation depends on the value obtained by the end of the last simulation?</p>
  
Tags: <monte-carlo-tree-search><alphago-zero>
Title: How does Alpha Go Zero MCTS work in parallel?
UserDisplayName: martinkunev
ThreadText: # How does Alpha Go Zero MCTS work in parallel?
  
  (Asked by: username_0 on 2023-09-25)
  
  I am trying to better understand the article "Mastering the Game of Go without Human Knowledge" ([link](https://faculty.washington.edu/jwilker/559/2018/go.pdf)) and I'm confused about the parallel implementation of Monte-Carlo-Tree-Search.
  
  On page 25 under "Search Algorithm", the authors say (emphasis mine)
  
  > AlphaGo Zero uses a much simpler variant of the asynchronous policy and
  > value MCTS algorithm (APV-MCTS)
  
  > Multiple simulations are executed **in parallel** on separate search threads.
  
  On page 26 under "Select",
  
  > an action is selected according to the statistics in the search tree
  
  There are some math details on how an action is selected based on (among other things) the mean action value (Q).
  
  I find this confusing because the choice of action at each simulation depends on the statistics of the previous simulations (the value of Q).
  
  How can simulations be run in parallel given that the choice of action in each simulation depends on the value obtained by the end of the last simulation?
  
  **Tags:** monte-carlo-tree-search, alphago-zero
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2023-09-26. Score: 2 | Accepted answer
  
  To understand how AlphaGo Zero performs parallel simulations think of each simulation as a separate agent that interacts with the search tree. Each agent starts from the root node and selects an action according to the statistics in the tree, such as:
  
  (1) mean action value (Q),
  (2) visit count (N), and;
  (3) prior probability (P).
  
  The agent then follows the action to the next node and repeats the process until it reaches a leaf node. At the leaf node, the agent evaluates the state using the neural network and propagates the value back to the root node, updating the statistics along the way.
  
  However, since there are multiple agents running in parallel, they may not have access to the most updated statistics in the tree. For example, one agent may select an action that another agent has already explored and updated its value. To avoid this problem, AlphaGo Zero uses a [virtual loss mechanism](https://github.com/initial-h/AlphaZero_Gomoku_MPI) that temporarily reduces the Q value of a node when an agent visits it. This discourages other agents from selecting the same node until the first agent finishes its evaluation and restores the Q value. This way, each agent can explore different parts of the tree without waiting for each other.
  
  [Pseudo code](https://web.stanford.edu/%7Esurag/posts/alphazero.html) of the parallel search engine
  
  
  ---
  
  ### Answer by username_2 on 2023-09-26. Score: 0
  
  1. you have a board in front of you
  2. you pick N most likely moves from the optimal policy (likely = doing this move you are more likely to win)
  3. you create N threads
  4. in each thread, you simulate doing one of these moves, and in parallel, you can go on with this reasoning recursively
  
  Once you reach the terminal node, or you finished you time budget, you use the V function to approximate the result, and you back-propagate the information using usual methods
  
  
  ---
  
  