Answers.Body: <p>The LC0 authors studied the AlphaZero paper very carefully, ran their own experiments, and they came to the following conclusion. AlphaZero, despite calling it's algorithm Monte Carlo tree search (All Monte Carlo methods are by definition explicitly random), does not employ any explicit non-determinism after a certain number of moves (I believe this is 15 moves). </p>
  
  <p>There are two different parts to MCTS that could introduce randomness into move selection. </p>
  
  <ol>
  <li><p>During the search phase, AlphaZero assigns weights on which moves to explore based on 2 factors: the win probability as evaulated by the neural network, and also some sub-tree size statistics of the parent and child move sub-trees. The first factor ensures that more promising lines are evaluated first, and the second factor ensures that less promising lines are eventually searched. In a natural implementation of MCTS, it would use weighted random choices between these weighted possibilities. In reality, AlphaZero chooses between these completely deterministicly, by just choosing the max weight every time. It does this because the randomness in this step does not turn out to be helpful, and only distracts the engine from the more important variations, on average.</p></li>
  <li><p>During the moving phase, it can make a weighted choice between move candidates which already have deep and accurate evaluations calculated by the search phase. The idea is to make slightly suboptimal moves to try to introduce diversity in its play, so it doesn't play the same game every time. This is especially important during training, but also leads to more interesting match results. It turns out that AlphaZero only does this for the first 15 moves or so, after that it always chooses the best move. This determinism turns out to be essential for its extremely accurate endgame play, where tiny differences in evaluation turn out to be the difference between draws and wins. </p></li>
  </ol>
  
  <p>This is true during both training and evaluation. </p>
  
  <p>In other words, once it is out of the opening, its play is as deterministic as a traditional engine. </p>
  
  <p>However, note that it will have the same sort of multithreading and time control non-determinism as traditional engines. </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-07T21:13:30.443Z
Answers.LastActivityDate: 2019-05-07T21:13:30.443Z
Answers.UserDisplayName: Benjamin
Answers.Body: <p>I've noticed AlphaZero played 1.d4 and 1.Nf3 in <a href="http://www.chessgames.com/perl/chess.pl?tid=91944&amp;crosstable=1" rel="noreferrer">http://www.chessgames.com/perl/chess.pl?tid=91944&amp;crosstable=1</a>. Possibilities:</p>
  
  <ul>
  <li>Mutlithreading (any software engineer can tell you it's not deterministic)</li>
  <li>Monte Carlo Tree Search (the algorithm draws random paths, so it can't be deterministic)</li>
  </ul>
  
  <p>Please note while the model's parameters are "fixed" (your own words), the actual move might be different. We don't have the source code for AlphaZero, but multithreading and MCTS are likely two major casues.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-18T17:41:17.573Z
Answers.Text: What do  you mean multi-threading isn't deterministic? Isn't that dependent on how it is used. We may not know what thread finishes first, but for the most part people tend to (or at least try to) be careful about making sure that any inconsistencies with order that things are executed don't effect the final outcome of the program.
Answers.UserDisplayName: Benji Altman
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-18T21:58:30.850Z
Answers.Text: @BenjiAltman I wrote we don’t have source code. You are welcome to contribute for your own answer.
Answers.UserDisplayName: SmallChess
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-18T22:01:11.243Z
Answers.Text: I don't know nearly enough about this, but you said "any software engineer can tell you it's not deterministic" and I agree, however that doesn't mean that it would introduce randomness into the algorithm.
Answers.UserDisplayName: Benji Altman
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-18T22:28:30.843Z
Answers.Text: Any software engineer should be able to tell you that you shouldn't rely on multi-threaded algorithm if you need your algorithm to be deterministic, but one should also not rely on multi-threading if one needs the algorithm to be *non*-deterministic.
Answers.UserDisplayName: Acccumulation
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-18T23:42:04.553Z
Answers.Text: Multithreading in chess engines is almost never deterministic.
Answers.UserDisplayName: SmallChess
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-20T23:14:31.560Z
Answers.Text: @rec Correct. High performance applications such as chess don't wait for threads to finish (they are not business applications!), and therefore deterministic. For example, Stockfish running on multi-core is 100% non-deterministic.
Answers.UserDisplayName: SmallChess
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-21T16:45:29.423Z
Answers.Text: @rec That makes sense, thanks for the explanation!
Answers.UserDisplayName: Benji Altman
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-05-28T22:57:14.373Z
Answers.Text: To give a more concrete example, consider what happens if thread A must evaluate a position to a depth of 4 ply while thread B must evaluate the same position to a depth of 6 ply. If thread A evaluates the position first, it will do the expected 4 ply evaluation, but if thread B evaluates the position first then thread A will trust the deeper 6 ply evaluation. At no point does the engine do anything wrong, yet still there is a race condition.
Answers.UserDisplayName: James Hollis
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-17T13:04:27.903Z
Answers.LastActivityDate: 2017-12-17T13:04:27.903Z
Answers.UserDisplayName: SmallChess
Body: <p>My understanding is that Alpha Zero's algorithm was fixed after the "learning" phase, so would it come up with the same move for every position? Was the variability in the match entirely due to a Stockfish setting, or did Alpha Zero also display an element of randomness in its move selection?</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-16T07:31:06.683Z
Comments.Text: Monte Carlo tree search used by alpha zero sounds pretty random.
Comments.UserDisplayName: hoacin
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-16T07:33:24.697Z
Comments.Text: Monte Carlo is not a deterministic algorithm.
Comments.UserDisplayName: SmallChess
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-16T10:16:12.673Z
Comments.Text: My understanding is the mcst was used in the "learning" phase to train the neural net, while the algorithm was bedded down for the actual match. Seems like I'm missing a trick.
Comments.UserDisplayName: firtydank
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-16T11:55:20.757Z
Comments.Text: I think mcts was used all the time.
Comments.UserDisplayName: hoacin
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-18T22:03:42.060Z
Comments.Text: Another possible if someway unlikely source of variation is time. While the same time may be used on the same move there is always some ability to take a different about of time to do some computation, thus maybe it ran a bit faster one time over another and then the faster time it came up with a better answer because it got further then the slower time.
Comments.UserDisplayName: Benji Altman
Tags: <engines><computer-chess><alphazero>
Title: What was the source of randomness in the Alpha Zero vs Stockfish match?
ThreadText: # What was the source of randomness in the Alpha Zero vs Stockfish match?
  
  (Asked by: username_0 on 2017-12-16)
  
  My understanding is that Alpha Zero's algorithm was fixed after the "learning" phase, so would it come up with the same move for every position? Was the variability in the match entirely due to a Stockfish setting, or did Alpha Zero also display an element of randomness in its move selection?
  
  **Tags:** engines, computer-chess, alphazero
  
  > **Comments:**
  > **username_1**: Monte Carlo tree search used by alpha zero sounds pretty random.  
  > **username_2**: Monte Carlo is not a deterministic algorithm.  
  > **username_0**: My understanding is the mcst was used in the "learning" phase to train the neural net, while the algorithm was bedded down for the actual match. Seems like I'm missing a trick.  
  > **username_1**: I think mcts was used all the time.  
  > **username_3**: Another possible if someway unlikely source of variation is time. While the same time may be used on the same move there is always some ability to take a different about of time to do some computation, thus maybe it ran a bit faster one time over another and then the faster time it came up with a better answer because it got further then the slower time.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2017-12-17. Score: 6 | Accepted answer
  
  I've noticed AlphaZero played 1.d4 and 1.Nf3 in <http://www.chessgames.com/perl/chess.pl?tid=91944&crosstable=1>. Possibilities:
  
  * Mutlithreading (any software engineer can tell you it's not deterministic)
  * Monte Carlo Tree Search (the algorithm draws random paths, so it can't be deterministic)
  
  Please note while the model's parameters are "fixed" (your own words), the actual move might be different. We don't have the source code for AlphaZero, but multithreading and MCTS are likely two major casues.
  
  > **Comments:**
  > **username_3**: What do  you mean multi-threading isn't deterministic? Isn't that dependent on how it is used. We may not know what thread finishes first, but for the most part people tend to (or at least try to) be careful about making sure that any inconsistencies with order that things are executed don't effect the final outcome of the program.  
  > **username_2**: @username_3 I wrote we don’t have source code. You are welcome to contribute for your own answer.  
  > **username_3**: I don't know nearly enough about this, but you said "any software engineer can tell you it's not deterministic" and I agree, however that doesn't mean that it would introduce randomness into the algorithm.  
  > **username_5**: Any software engineer should be able to tell you that you shouldn't rely on multi-threaded algorithm if you need your algorithm to be deterministic, but one should also not rely on multi-threading if one needs the algorithm to be *non*-deterministic.  
  > **username_2**: Multithreading in chess engines is almost never deterministic.  
  > **username_2**: @rec Correct. High performance applications such as chess don't wait for threads to finish (they are not business applications!), and therefore deterministic. For example, Stockfish running on multi-core is 100% non-deterministic.  
  > **username_3**: @rec That makes sense, thanks for the explanation!  
  > **username_6**: To give a more concrete example, consider what happens if thread A must evaluate a position to a depth of 4 ply while thread B must evaluate the same position to a depth of 6 ply. If thread A evaluates the position first, it will do the expected 4 ply evaluation, but if thread B evaluates the position first then thread A will trust the deeper 6 ply evaluation. At no point does the engine do anything wrong, yet still there is a race condition.  
  
  ---
  
  ### Answer by username_4 on 2019-05-07. Score: 6
  
  The LC0 authors studied the AlphaZero paper very carefully, ran their own experiments, and they came to the following conclusion. AlphaZero, despite calling it's algorithm Monte Carlo tree search (All Monte Carlo methods are by definition explicitly random), does not employ any explicit non-determinism after a certain number of moves (I believe this is 15 moves).
  
  There are two different parts to MCTS that could introduce randomness into move selection.
  
  1. During the search phase, AlphaZero assigns weights on which moves to explore based on 2 factors: the win probability as evaulated by the neural network, and also some sub-tree size statistics of the parent and child move sub-trees. The first factor ensures that more promising lines are evaluated first, and the second factor ensures that less promising lines are eventually searched. In a natural implementation of MCTS, it would use weighted random choices between these weighted possibilities. In reality, AlphaZero chooses between these completely deterministicly, by just choosing the max weight every time. It does this because the randomness in this step does not turn out to be helpful, and only distracts the engine from the more important variations, on average.
  2. During the moving phase, it can make a weighted choice between move candidates which already have deep and accurate evaluations calculated by the search phase. The idea is to make slightly suboptimal moves to try to introduce diversity in its play, so it doesn't play the same game every time. This is especially important during training, but also leads to more interesting match results. It turns out that AlphaZero only does this for the first 15 moves or so, after that it always chooses the best move. This determinism turns out to be essential for its extremely accurate endgame play, where tiny differences in evaluation turn out to be the difference between draws and wins.
  
  This is true during both training and evaluation.
  
  In other words, once it is out of the opening, its play is as deterministic as a traditional engine.
  
  However, note that it will have the same sort of multithreading and time control non-determinism as traditional engines.
  
  
  ---
  
  