Answers.Body: <p>Thanks to @Phonon covering my previous answers in details. I'd like to add one more point: <strong>time control</strong>.</p>
  
  <p>The only deterministic time control is by <strong>number of nodes</strong>, but this is uncommon. The much more common time control - <strong>fixed number of seconds</strong> or <strong>game time</strong> are generally not deterministic. </p>
  
  <p>Let's try an example. Run stockfish on your terminal. Type:</p>
  
  <blockquote>
    <p>go movetime 20000</p>
  </blockquote>
  
  <p>This command instructs the engine to make a move after 20 seconds. My results:</p>
  
  <pre><code>info depth 23 seldepth 32 multipv 1 score cp 6 upperbound nodes 24325860 nps 1216171 hashfull 999 tbhits 0 time 20002 pv g1f3 d7d5
  bestmove g1f3 ponder d7d5
  </code></pre>
  
  <p>The move was 1.Nf3. Next, I killed my Stockfish, started a new one. Again, 20 seconds. I got:</p>
  
  <pre><code>info depth 23 seldepth 32 multipv 1 score cp 20 nodes 26185280 nps 1309067 hashfull 999 tbhits 0 time 20003 pv d2d4
  bestmove d2d4 ponder g8f6
  </code></pre>
  
  <p>It's 1.d4! Same position, both 20 seconds search!</p>
  
  <p>Do you see? Both 20 seconds for the move, but due to fluctuation in the Linux operating system my second run had deeper search (26185280 > 24325860).</p>
  
  <p>Please note this little experiment wasn't even multithreaded (number of threads = 1). Multithreading would make things even more non-deterministic.</p>
  
  <p>Stockfish was given one minute per move in the Google AlphaZero match. Number of threads was 64. Stockfish's decisions in the match <strong>couldn't</strong> possibly be deterministic.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-21T15:20:41.590Z
Answers.Text: Indeed, very instructive example and remark.
Answers.UserDisplayName: user929304
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-21T15:28:59.530Z
Answers.Text: nice! cool idea to showcase even the 1 thread case.
Answers.UserDisplayName: Ellie
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-24T06:09:47.630Z
Answers.Text: Thanks for the answer. Stupid follow-up question: what's a node (in the context of chess-playing engines)?
Answers.UserDisplayName: Allure
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-25T00:16:19.027Z
Answers.Text: @user3727079 The nodes are the vertices (unique positions) in the game [tree](https://en.wikipedia.org/wiki/Tree_(data_structure)). For instance if the root node is the starting position, then it has 20 child nodes, which are the 20 unique legal positions that are one-ply away from the root.
Answers.UserDisplayName: Ellie
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-21T14:52:03.953Z
Answers.LastActivityDate: 2017-12-21T15:21:26.857Z
Answers.LastEditDate: 2017-12-21T15:21:26.857Z
Answers.UserDisplayName: SmallChess
Answers.Body: <p>Regarding the AlphaZero vs Stockfish match, this question has already been covered <a href="https://chess.stackexchange.com/questions/19437/what-was-the-source-of-randomness-in-the-alpha-zero-vs-stockfish-match">here</a> by <a href="https://chess.stackexchange.com/users/825/smallchess">SmallChess</a>.</p>
  
  <p>AlphaZero aside (which employs a <a href="https://en.wikipedia.org/wiki/Monte_Carlo_tree_search" rel="noreferrer">specialised Monte Carlo</a><sup>1</sup> routine in its exploration of the lines of play), which is made to be <a href="https://en.wikipedia.org/wiki/Simple_random_sample" rel="noreferrer">non-deterministic</a> by construction, for the usual heuristics based chess engines, such as Stockfish and others (though there are other engines that have MC-based routines, AFAIK <a href="https://en.chessbase.com/post/rybka-s-monte-carlo-analysis" rel="noreferrer">Rybka used to have such feature</a>), the source of randomness is generally just a consequence of technical aspects in the implementation, rather than intentional randomness being introduced algorithmically in the engine's decision making. Abstractly speaking, one reason for that is the fact that the engines aren't running in a purely sequential manner (executing one task after the other). Instead, to render the engines more efficient, they perform parallel searches in various branches of the tree of possible moves. They do so via what is called <em><a href="https://en.wikipedia.org/wiki/Multithreading_(computer_architecture)" rel="noreferrer">multi-threading</a></em> (or <em>-processing</em> but that is a bit different). So multiple threads of the CPUs are <em>concurrently</em> executing operations to search the tree (and cache the evaluations of visited positions), so imagine each thread being assigned a subtree. The problem with this kind of implementation is that the overall execution of the threads becomes highly dependent on all sorts of conditions (waiting times, RAM swaps, ...), so in the end a principal variation may be chosen without having allowed all other threads to finish their search. </p>
  
  <p>This indeed happens often because the engine is set to make a decision under a certain amount of time, so time management alters the behaviour. You can also revert this statement by saying: knowing the algorithm and implementing deterministic threading routines are not sufficient to reliably predict the state of the program after any time t. Of course if one always allows all threads to finish their search, and there haven't been concurrency issues during that execution (for instance a thread trying to access a certain cache that isn't accessible), then the behaviour will indeed be fully reproducible given everything else is the same<sup>2</sup>. </p>
  
  <hr>
  
  <p><sup><sup>1</sup>: Together with the fact that through additional training (for instance self-play) its neural network keeps evolving (re-adjusted parameters), or if you will its evaluation function doesn't have a constant, fixed definition (unlike heuristics based engines). </sup></p>
  
  <p><sup><sup>2</sup>: Even then, as you said, at the opening level, with an opening book, there are sometimes intentional random decisions made by the engine as to which variation to choose. Similarly, outside of the opening phase, there can be moments where multiple variations have close to equal evaluations (within the resolution chosen for the Eval), then based on the design, it may end up choosing one randomly. Finally, at the level of engine settings you have to be careful as well, for instance the depth of search and ponder times chosen for each engine (and whether they can further calculate during each other's ponder times). </sup></p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-21T14:11:49.103Z
Answers.LastActivityDate: 2017-12-21T14:11:49.103Z
Answers.UserDisplayName: Ellie
Body: <p>If I get two engines to play against each other with the same colours, will the same game result every time? If not, where does the randomness in engine play come from? (Neglecting the opening book, where if I'm not mistaken the book can tell the engine to pick between two moves at random since they're equally good.)</p>
  
  <p>I'm assuming that there is randomness because in the Alphazero vs. Stockfish match, we didn't get the same game happening many times in a row. However I don't understand why. Presumably the only way to do this is to get the engine to play a subpar move some of the time, which sounds like seppuku. </p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-21T07:56:08.980Z
Comments.Text: AlphaZero learns by playing, so after each game it's model is updated.
Comments.UserDisplayName: ferit
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-21T10:44:32.100Z
Comments.Text: Adding small random value to evaluation is one of possible ways. I think stockfish is doing that.
Comments.UserDisplayName: hoacin
Tags: <engines>
Title: Randomness in engine play
ThreadText: # Randomness in engine play
  
  (Asked by: username_0 on 2017-12-21)
  
  If I get two engines to play against each other with the same colours, will the same game result every time? If not, where does the randomness in engine play come from? (Neglecting the opening book, where if I'm not mistaken the book can tell the engine to pick between two moves at random since they're equally good.)
  
  I'm assuming that there is randomness because in the Alphazero vs. Stockfish match, we didn't get the same game happening many times in a row. However I don't understand why. Presumably the only way to do this is to get the engine to play a subpar move some of the time, which sounds like seppuku.
  
  **Tags:** engines
  
  > **Comments:**
  > **username_1**: AlphaZero learns by playing, so after each game it's model is updated.  
  > **username_2**: Adding small random value to evaluation is one of possible ways. I think stockfish is doing that.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_5 on 2017-12-21. Score: 11 | Accepted answer
  
  Regarding the AlphaZero vs Stockfish match, this question has already been covered [here](https://chess.stackexchange.com/questions/19437/what-was-the-source-of-randomness-in-the-alpha-zero-vs-stockfish-match) by [username_3](https://chess.stackexchange.com/users/825/smallchess).
  
  AlphaZero aside (which employs a [specialised Monte Carlo](https://en.wikipedia.org/wiki/Monte_Carlo_tree_search)1 routine in its exploration of the lines of play), which is made to be [non-deterministic](https://en.wikipedia.org/wiki/Simple_random_sample) by construction, for the usual heuristics based chess engines, such as Stockfish and others (though there are other engines that have MC-based routines, AFAIK [Rybka used to have such feature](https://en.chessbase.com/post/rybka-s-monte-carlo-analysis)), the source of randomness is generally just a consequence of technical aspects in the implementation, rather than intentional randomness being introduced algorithmically in the engine's decision making. Abstractly speaking, one reason for that is the fact that the engines aren't running in a purely sequential manner (executing one task after the other). Instead, to render the engines more efficient, they perform parallel searches in various branches of the tree of possible moves. They do so via what is called *[multi-threading](https://en.wikipedia.org/wiki/Multithreading_(computer_architecture))* (or *-processing* but that is a bit different). So multiple threads of the CPUs are *concurrently* executing operations to search the tree (and cache the evaluations of visited positions), so imagine each thread being assigned a subtree. The problem with this kind of implementation is that the overall execution of the threads becomes highly dependent on all sorts of conditions (waiting times, RAM swaps, ...), so in the end a principal variation may be chosen without having allowed all other threads to finish their search.
  
  This indeed happens often because the engine is set to make a decision under a certain amount of time, so time management alters the behaviour. You can also revert this statement by saying: knowing the algorithm and implementing deterministic threading routines are not sufficient to reliably predict the state of the program after any time t. Of course if one always allows all threads to finish their search, and there haven't been concurrency issues during that execution (for instance a thread trying to access a certain cache that isn't accessible), then the behaviour will indeed be fully reproducible given everything else is the same2.
  
  ---
  
  1: Together with the fact that through additional training (for instance self-play) its neural network keeps evolving (re-adjusted parameters), or if you will its evaluation function doesn't have a constant, fixed definition (unlike heuristics based engines).
  
  2: Even then, as you said, at the opening level, with an opening book, there are sometimes intentional random decisions made by the engine as to which variation to choose. Similarly, outside of the opening phase, there can be moments where multiple variations have close to equal evaluations (within the resolution chosen for the Eval), then based on the design, it may end up choosing one randomly. Finally, at the level of engine settings you have to be careful as well, for instance the depth of search and ponder times chosen for each engine (and whether they can further calculate during each other's ponder times).
  
  
  ---
  
  ### Answer by username_3 on 2017-12-21. Score: 8
  
  Thanks to @Phonon covering my previous answers in details. I'd like to add one more point: time control.
  The only deterministic time control is by number of nodes, but this is uncommon. The much more common time control - fixed number of seconds or game time are generally not deterministic. 
  Let's try an example. Run stockfish on your terminal. Type:
  
  go movetime 20000
  
  This command instructs the engine to make a move after 20 seconds. My results:
  info depth 23 seldepth 32 multipv 1 score cp 6 upperbound nodes 24325860 nps 1216171 hashfull 999 tbhits 0 time 20002 pv g1f3 d7d5
  bestmove g1f3 ponder d7d5
  
  The move was 1.Nf3. Next, I killed my Stockfish, started a new one. Again, 20 seconds. I got:
  info depth 23 seldepth 32 multipv 1 score cp 20 nodes 26185280 nps 1309067 hashfull 999 tbhits 0 time 20003 pv d2d4
  bestmove d2d4 ponder g8f6
  
  It's 1.d4! Same position, both 20 seconds search!
  Do you see? Both 20 seconds for the move, but due to fluctuation in the Linux operating system my second run had deeper search (26185280 > 24325860).
  Please note this little experiment wasn't even multithreaded (number of threads = 1). Multithreading would make things even more non-deterministic.
  Stockfish was given one minute per move in the Google AlphaZero match. Number of threads was 64. Stockfish's decisions in the match couldn't possibly be deterministic.
  
  > **Comments:**
  > **username_4**: Indeed, very instructive example and remark.  
  > **username_5**: nice! cool idea to showcase even the 1 thread case.  
  > **username_0**: Thanks for the answer. Stupid follow-up question: what's a node (in the context of chess-playing engines)?  
  > **username_5**: @user3727079 The nodes are the vertices (unique positions) in the game [tree](https://en.wikipedia.org/wiki/Tree_(data_structure)). For instance if the root node is the starting position, then it has 20 child nodes, which are the 20 unique legal positions that are one-ply away from the root.  
  
  ---
  
  