Answers.Body: <p>The diagram shows the 10 most visited game states/positions that AlphaZero calculated. It's actually looking at thousands of positions, but they're only showing the 10 positions that it comes back to the most. For your questions:</p>
  
  <p>1) AlphaZero's search algorithm is called Monte Carlo Tree Search (MCTS). The fundamentals of how it works when thinking at some game state:</p>
  
  <ul>
  <li>Pick a move. The way this move is picked is based off an algorithm favoring:
  
  <ul>
  <li>How good a move has performed in past random simulations of it.</li>
  <li>How infrequently it has been picked (a move played out less ==> more desirable).</li>
  </ul></li>
  <li>Follow this move to a new game state (i.e., the position that arises when you play the move).</li>
  <li>Repeat step 1, for some time limit or depth limit.</li>
  </ul>
  
  <p>The move that has the best average score in all its playouts is the one that AlphaZero picks. There's more involved than this, but the above is the general idea of MCTS. So something like 10^2 simulations for the root node means that AlphaZero performed the above algorithm 10^2 times for that position.</p>
  
  <p>The part where they mentioned "800 simulations" refers to when AlphaZero was learning (<em>before</em> its games with Stockfish). The way AlphaZero learns heuristics on its own (which allow it to accurately evaluate positions) is by playing itself over and over. So, I assume they mean that during this phase of playing itself, each time it thought on what to play in a position, it only performed 800 simulations from a position. The point of this was probably to have time to get more practice games in. Against Stockfish, playing extremely quickly is unnecessary, and AlphaZero may as well use the time it's been given to playout way more such simulations.</p>
  
  <p>2) Explained above.</p>
  
  <p>3) Yes, thousands of other moves are also considered, they just aren't shown in the diagram. Also, even if the 10 states shown were the only ones reached, you couldn't just average their scores out. The reason is that some game states are reached more often than others, and thus have a higher weight in the average calculation.</p>
  
  <ul>
  <li>To illustrate this, assume you only had two possible moves you could play in the beginning of a game: 1.e4 and 1.h4. Looking back at the MCTS algorithm I outlined, playouts/simulations on 1.e4 would happen more often since 1.e4 performs better. However, 1.h4 would also be picked once in a while due to how infrequently you look at it. So maybe you do 9 playouts on 1.e4 and get a score of 60%, while do 1 playout on 1.h4 and get a 0% score. Your odds of winning from the starting position are not (60% + 0%) / 2 = 30%, but rather (60% * 9 + 0% * 1) / 10 = 54%.</li>
  </ul>
  
  <p>4) Yes, only an illustrative sample is shown since they only wanted to show the 10 most visited game states. I'm sure AlphaZero continued the MCTS algorithm far past 34.Rce1.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-06T09:45:29.023Z
Answers.Text: Thanks! Great answer. Ok, I understand that, during the games against SF, AZ performed 10^6 simulations per played position/state, e.g. after 29...Qf8... Regarding Q1, What is unclear for me is 1/"Pick a move" is one MCTS and "Repeat step 1" will be another MCTS or 2/ is your example only one MCTS?
Answers.UserDisplayName: Kortchnoi
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-06T10:15:22.177Z
Answers.Text: To be more precise in the 2nd case: is your example one MCTS with 2 simulations?
Answers.UserDisplayName: Kortchnoi
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-06T17:30:37.447Z
Answers.Text: @Kortchnoi The MCTS is a recursive algorithm. This means that in order to run, it calls itself X number of times (where X is how deep it runs the playout simulation from the starting position). The steps I listed from "pick a move" until "repeat step 1" is all part of one MCTS simulation, no matter how many times the algorithm recursively iterates down the game tree. Another simulation only starts when the algorithm has finished searching and then a new playout simulation begins again from the starting position.
Answers.UserDisplayName: Inertial Ignorance
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-06T17:33:10.627Z
Answers.Text: Think of it like this. You want to know what to play on the first move. You pick 1.e4 via the algorithm, since in the past it has done well in the simulations you've performed mentally, and at the same time you haven't done too many simulations on it. Now in the new position after 1.e4, you need to pick a move for Black to play. You do the same algorithm, and let's say you get 1...c5. Now it's White's turn to play so you do the same algorithm. Etc, until you reach some depth limit or someone wins the game (or draws). This is all one simulation from the starting position.
Answers.UserDisplayName: Inertial Ignorance
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-06T17:34:49.547Z
Answers.Text: The result of the simulation affects the score of 1.e4. Also though, all the moves played in the simulation (such as 1...c5) also have their scores affected.
Answers.UserDisplayName: Inertial Ignorance
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-06T19:01:13.273Z
Answers.Text: Thank you very much. I guess I see. Let's start a MCTS on the first move.  1.e4 c5 2.Cf3 ... until I reach some depth limit would be simulation 1; 1.e4 c5 2.c3... until I reach some depth limit would be simulation 2; 1.e4 d5 2.exd5... until I reach some depth limit would be simulation 3; 1.d4 d5 2.Cf3... until I reach some depth limit would be simulation 4.  etc... Am I right?
Answers.UserDisplayName: Kortchnoi
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-06T19:02:11.203Z
Answers.Text: Then if I 1.e4 c5 is played I start a MCTS on move 2 with many simulations...
Answers.UserDisplayName: Kortchnoi
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-06T19:49:42.073Z
Answers.Text: Yes exactly. Each MCTS is just a bunch of those simulations run from the position you're thinking on.
Answers.UserDisplayName: Inertial Ignorance
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-06T05:51:14.837Z
Answers.LastActivityDate: 2019-01-06T05:51:14.837Z
Answers.UserDisplayName: Inertial Ignorance
Body: <p>I am aware of related questions and great answers on the same topic such as <a href="https://chess.stackexchange.com/questions/19353/understanding-alphazero">Understanding AlphaZero</a>. My questions are related to the following figure on <strong>AlphaZero's search procedure</strong>  </p>
  
  <p><a href="https://i.sstatic.net/nnVOx.jpg" rel="noreferrer"><img src="https://i.sstatic.net/nnVOx.jpg" alt="enter image description here"></a></p>
  
  <p>This figure comes from the <a href="http://science.sciencemag.org/content/362/6419/1140" rel="noreferrer">Science paper</a> on AlphaZero (Fig. 4, page 4). The search is illustrated for a position from the very nice game 1 AlphaZero (white) and Stockfish (black) after 29. ... Qf8. The rest of note of the figure is as follows</p>
  
  <blockquote>
    <p>The internal state of AlphaZero's MCTS is summarized after 10^2,
    ..., 10^6 simulations. Each summary shows the 10 most visited states.
    The estimated value is shown in each state, from white's perspective,
    scaled to the range [0, 100]. The visit count of each state, relative
    to the root state of that tree, is proportional to the thickness of
    the border circle. AlphaZero considers 30.c6 but eventually plays
    30.d5.</p>
  </blockquote>
  
  <p>I would appreciate some insights regarding the following questions. (Important to note that I am a mere chess player with no knowledge on computer science. I still find this fascinating)</p>
  
  <ol>
  <li>What does represent the 10^2, ..., 10^6 simulations? I am very
  confused because in the Supplementary Material they note that
  ``During training, each MCTS used 800 simulations''. </li>
  <li>What does it mean that each MCTS used 800 simulations?</li>
  <li>I assume that the value of 60 in the red circle in the 10^2
  simulations represents a 60% expected score for white, which is the
      average of all position evaluations. However, the simple average of the 9 moves shown is equal to 61.2. I guess that other moves also considered and simulated. Am I right here? </li>
  <li>I assume that for simulations 10^3 to 10^6, they only present an
  illustrative sample of the branches. The simulation 10^5 is not
      shown after 34.Rce1 or stopped after 34.Rce1? I guess that each
      simulation goes until an expected score of 100%.</li>
  </ol>
  
Tags: <engines><alphazero>
Title: AlphaZero’s search procedure
ThreadText: # AlphaZero’s search procedure
  
  (Asked by: username_0 on 2019-01-05)
  
  I am aware of related questions and great answers on the same topic such as [Understanding AlphaZero](https://chess.stackexchange.com/questions/19353/understanding-alphazero). My questions are related to the following figure on **AlphaZero's search procedure**
  
  [![enter image description here](https://i.sstatic.net/nnVOx.jpg)](https://i.sstatic.net/nnVOx.jpg)
  
  This figure comes from the [Science paper](http://science.sciencemag.org/content/362/6419/1140) on AlphaZero (Fig. 4, page 4). The search is illustrated for a position from the very nice game 1 AlphaZero (white) and Stockfish (black) after 29. ... Qf8. The rest of note of the figure is as follows
  
  > The internal state of AlphaZero's MCTS is summarized after 10^2,
  > ..., 10^6 simulations. Each summary shows the 10 most visited states.
  > The estimated value is shown in each state, from white's perspective,
  > scaled to the range [0, 100]. The visit count of each state, relative
  > to the root state of that tree, is proportional to the thickness of
  > the border circle. AlphaZero considers 30.c6 but eventually plays
  > 30.d5.
  
  I would appreciate some insights regarding the following questions. (Important to note that I am a mere chess player with no knowledge on computer science. I still find this fascinating)
  
  1. What does represent the 10^2, ..., 10^6 simulations? I am very
     confused because in the Supplementary Material they note that
     ``During training, each MCTS used 800 simulations''.
  2. What does it mean that each MCTS used 800 simulations?
  3. I assume that the value of 60 in the red circle in the 10^2
     simulations represents a 60% expected score for white, which is the
     average of all position evaluations. However, the simple average of the 9 moves shown is equal to 61.2. I guess that other moves also considered and simulated. Am I right here?
  4. I assume that for simulations 10^3 to 10^6, they only present an
     illustrative sample of the branches. The simulation 10^5 is not
     shown after 34.Rce1 or stopped after 34.Rce1? I guess that each
     simulation goes until an expected score of 100%.
  
  **Tags:** engines, alphazero
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-01-06. Score: 5 | Accepted answer
  
  The diagram shows the 10 most visited game states/positions that AlphaZero calculated. It's actually looking at thousands of positions, but they're only showing the 10 positions that it comes back to the most. For your questions:
  
  1) AlphaZero's search algorithm is called Monte Carlo Tree Search (MCTS). The fundamentals of how it works when thinking at some game state:
  
  * Pick a move. The way this move is picked is based off an algorithm favoring:
    + How good a move has performed in past random simulations of it.
    + How infrequently it has been picked (a move played out less ==> more desirable).
  * Follow this move to a new game state (i.e., the position that arises when you play the move).
  * Repeat step 1, for some time limit or depth limit.
  
  The move that has the best average score in all its playouts is the one that AlphaZero picks. There's more involved than this, but the above is the general idea of MCTS. So something like 10^2 simulations for the root node means that AlphaZero performed the above algorithm 10^2 times for that position.
  
  The part where they mentioned "800 simulations" refers to when AlphaZero was learning (*before* its games with Stockfish). The way AlphaZero learns heuristics on its own (which allow it to accurately evaluate positions) is by playing itself over and over. So, I assume they mean that during this phase of playing itself, each time it thought on what to play in a position, it only performed 800 simulations from a position. The point of this was probably to have time to get more practice games in. Against Stockfish, playing extremely quickly is unnecessary, and AlphaZero may as well use the time it's been given to playout way more such simulations.
  
  2) Explained above.
  
  3) Yes, thousands of other moves are also considered, they just aren't shown in the diagram. Also, even if the 10 states shown were the only ones reached, you couldn't just average their scores out. The reason is that some game states are reached more often than others, and thus have a higher weight in the average calculation.
  
  * To illustrate this, assume you only had two possible moves you could play in the beginning of a game: 1.e4 and 1.h4. Looking back at the MCTS algorithm I outlined, playouts/simulations on 1.e4 would happen more often since 1.e4 performs better. However, 1.h4 would also be picked once in a while due to how infrequently you look at it. So maybe you do 9 playouts on 1.e4 and get a score of 60%, while do 1 playout on 1.h4 and get a 0% score. Your odds of winning from the starting position are not (60% + 0%) / 2 = 30%, but rather (60% \* 9 + 0% \* 1) / 10 = 54%.
  
  4) Yes, only an illustrative sample is shown since they only wanted to show the 10 most visited game states. I'm sure AlphaZero continued the MCTS algorithm far past 34.Rce1.
  
  > **Comments:**
  > **username_0**: Thanks! Great answer. Ok, I understand that, during the games against SF, AZ performed 10^6 simulations per played position/state, e.g. after 29...Qf8... Regarding Q1, What is unclear for me is 1/"Pick a move" is one MCTS and "Repeat step 1" will be another MCTS or 2/ is your example only one MCTS?  
  > **username_0**: To be more precise in the 2nd case: is your example one MCTS with 2 simulations?  
  > **username_1**: @username_0 The MCTS is a recursive algorithm. This means that in order to run, it calls itself X number of times (where X is how deep it runs the playout simulation from the starting position). The steps I listed from "pick a move" until "repeat step 1" is all part of one MCTS simulation, no matter how many times the algorithm recursively iterates down the game tree. Another simulation only starts when the algorithm has finished searching and then a new playout simulation begins again from the starting position.  
  > **username_1**: Think of it like this. You want to know what to play on the first move. You pick 1.e4 via the algorithm, since in the past it has done well in the simulations you've performed mentally, and at the same time you haven't done too many simulations on it. Now in the new position after 1.e4, you need to pick a move for Black to play. You do the same algorithm, and let's say you get 1...c5. Now it's White's turn to play so you do the same algorithm. Etc, until you reach some depth limit or someone wins the game (or draws). This is all one simulation from the starting position.  
  > **username_1**: The result of the simulation affects the score of 1.e4. Also though, all the moves played in the simulation (such as 1...c5) also have their scores affected.  
  > **username_0**: Thank you very much. I guess I see. Let's start a MCTS on the first move.  1.e4 c5 2.Cf3 ... until I reach some depth limit would be simulation 1; 1.e4 c5 2.c3... until I reach some depth limit would be simulation 2; 1.e4 d5 2.exd5... until I reach some depth limit would be simulation 3; 1.d4 d5 2.Cf3... until I reach some depth limit would be simulation 4.  etc... Am I right?  
  > **username_0**: Then if I 1.e4 c5 is played I start a MCTS on move 2 with many simulations...  
  > **username_1**: Yes exactly. Each MCTS is just a bunch of those simulations run from the position you're thinking on.  
  
  ---
  
  