Answers.Body: <p><strong>Question 1</strong>: I don't think they ran AlphaGo or AlphaGoZero in training mode during tournament matches because the computing power required for this is really large. I don't recall if this is described in the <a href="https://www.youtube.com/watch?v=WXuK6gekU1Y" rel="nofollow noreferrer">documentary</a> but see this quote from the <a href="https://arxiv.org/pdf/1712.01815.pdf" rel="nofollow noreferrer">AlphaZero paper</a> (page 4):</p>
  <blockquote>
  <p>using 5,000 first-generation TPUs (15) to generate self-play games and 64 second-generation TPUs to train the neural networks.</p>
  </blockquote>
  <p><strong>Question 2</strong>: From my first answer, I assume the network is run in inference mode, i.e., taking the observation of the environment as input and outputting the action (next move) according to the strongest strategy of the network. Then the AlphaGo does not learn anything as it does not evaluate whether the taken action is better than the strategy because these are the same. The way that the network learns during training/exploration is by comparing the random action that is taken to the best action known by the network.</p>
  <hr />
  <p>You are correct in your understanding of self-play and exploration. This is done in RL to explore actions that might not have been taken yet to explore actions that might be better than the best-known strategy.</p>
  <p>But during inference, you would want to greedily take the best-known actions because an action taken at random would most likely be way worse.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-19T08:11:32.200Z
Answers.Text: I think you are right for 1 and 2, that the NN was not being trained. However, my understanding is that MCTS was still used to improve on the NN policies, so it is not as cut and dry as this answer implies.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-19T08:45:08.927Z
Answers.Text: That is true and an important note which I did not consider. MCTS is used in AlphaGo and AlphaZero and described in the respective papers. Although its use is quite limited compared to traditional alpha-beta search engines, such as the Stockfish chess engine.
Answers.UserDisplayName: Lars
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-22T18:50:11.567Z
Answers.Text: Many thanks for your contribution! So in the "inference mode", AlphaGo will only choose the "best move"? What if there are two equally best move with the same value?
Answers.UserDisplayName: High GPA
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-24T07:09:03.733Z
Answers.Text: To my knowledge, I don't think there can be two moves with equal value unless your discount factor is 0, or close to it. With a discount factor of 0, the agent will not consider the value of the future moves which can be determined from the immediate action the agent is about to take. But hypothetically speaking, it would probably be a random selection between actions of equal value.
Answers.UserDisplayName: Lars
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-26T08:08:16.130Z
Answers.Text: @Lars Note that the Go board is symmetric so there are some scenarios that two or more moves are absolutely symmetric. If those symmetric moves are not of same value, then the algorithm has a problem. So, in my humble opinion, my question still hold: when two moves have exactly the same value, which move will be chosen?
Answers.UserDisplayName: High GPA
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-26T11:41:12.173Z
Answers.Text: Actually, I did not consider the symmetry property. You are correct that when the board and stones are symmetrical then two or more moves can have identical values. Moreover, because the value is the same, the possible actions in the future will also be the same regardless of which move is selected. So if they have the highest value of all available moves then it does not matter which of the moves is selected.
Answers.UserDisplayName: Lars
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-11-28T12:16:17.213Z
Answers.Text: @GPA: for ML purposes, you want to parameterize your scoring method using the minimal amount of trainable weights. A scoring algorithm that is asymmetric uses more weights than a symmetric one, so it's definitely worse.
Answers.UserDisplayName: MSalters
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-19T07:59:39.303Z
Answers.LastActivityDate: 2022-01-19T07:59:39.303Z
Answers.UserDisplayName: Lars
Answers.Body: <p>AlphaGo/AlphaZero has 3 main sources of randomness during competitive mode:</p>
  <ol>
  <li><p><strong>Move temperature</strong>: The MCTS process outputs a probability distribution P over all candidate moves. The agent chooses a move by sampling from the probability distribution proportional to P^(1/T) for some move temperature T. Typical configurations start T at some value near 1 and decay it quickly to 0 over the course of the game (the limit of P^(1/T) as T approaches 0 is the argmax function). This mechanism helps to ensure, for example, that the agent will not always play the same first move as first player.</p>
  </li>
  <li><p><strong>Symmetries</strong>: The game of go has 8-fold symmetry. Before querying the neural network, the agent randomly chooses one of the 8 symmetry transforms of the game and applies it to the board. It then applies the inverse transform to the neural network’s (policy) output. A perfect neural network should exhibit perfect 8-fold symmetry, but in reality the neural network is imperfect and exhibits asymmetrical biases (e.g., it wants to play an atari in board state S, but if you rotate S by 90 degrees, it no longer wants to play an atari). So this operation leads to random deviations in its move choices.</p>
  </li>
  <li><p><strong>Tree parallelization</strong>: MCTS is made multithreaded via a mechanism known as <em>tree parallelization</em>. The move distribution that MCTS outputs is dependent on the order in which the different threads interleave with each other, which is effectively random.</p>
  </li>
  </ol>
  <p>It is worth noting that any human could easily defeat any deterministic AI in any deterministic game. Simply pit two instances of the AI against each other, memorize the deterministic sequence of moves, and then use those exact same moves against a single copy of the AI. Because of this possibility, game playing agents typically are willing to sacrifice a small amount of playing strength for randomness. Move temperature in particular can be justified for this reason. The other two sources of randomness can be seen as byproducts of engineering optimizations.</p>
  <p>In other answers/comments, others have correctly noted that single-threaded MCTS is a deterministic algorithm (if executed purely on CPU). Given a game state, it will always output the same move distribution, absent the symmetry mechanism described above.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-04-05T15:10:20.373Z
Answers.LastActivityDate: 2023-04-05T15:55:00.960Z
Answers.LastEditDate: 2023-04-05T15:55:00.960Z
Answers.UserDisplayName: dshin
Answers.Body: <p>The core mechanics of AlphaZero during selfplay and real tournament games are the same: something similar to <a href="https://en.wikipedia.org/wiki/Monte_Carlo_tree_search" rel="nofollow noreferrer">Monte Carlo Tree Search</a> is done but guided by the current neural network instead of random simulations. The network is only doing inference, it's not learning <em>during</em> a tree search. There's a great summary diagram <a href="https://medium.com/applied-data-science/alphago-zero-explained-in-one-diagram-365f5abf67e0" rel="nofollow noreferrer">here</a>.</p>
  <p>The differences between selfplay and tournaments are:</p>
  <ul>
  <li><p>Selfplay tree searches games get some additional (Dirichlet) noise injected to encourage exploration of different moves and positions. This does not happen during tournament games since that would likely make play weaker.</p>
  </li>
  <li><p>During selfplay moves are selected randomly, but weighed according to how good the tree search thinks certain moves are. This means the entire training process spends most of its time looking at good moves, but still occasionally plays bad moves to keep some variety. During tournaments AlphaZero just plays what it thinks is the best move.</p>
  </li>
  <li><p>Selfplay games are kept in a large buffer with millions of positions, on which the next neural network is trained. This is the only point at which actual network training is happening.</p>
  </li>
  <li><p>Selfplay tree searches only look at ~800 nodes per position, which probably only takes a few milliseconds to calculate. Tournament games take a lot longer, <a href="https://en.wikipedia.org/wiki/AlphaZero#Chess_2" rel="nofollow noreferrer">3h per game + 15s per move</a>. This means the tree search visits hundreds of thousands, likely millions of positions for each move, making tournament play a lot stronger than selfplay.</p>
  </li>
  </ul>
  <p>These are the only differences between selfplay and tournament games. One thing to note is that after selfplay/training is done, AlphaZero is just an immutable neural network with some tree search code around it. There is no <em>learning</em> happening during a tournament, or any additional randomness injected into the process. Instead, to ensure a diversity of games, an <a href="https://www.chessprogramming.org/Opening_Book" rel="nofollow noreferrer">Opening Book</a> is used.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-24T13:16:58.403Z
Answers.Text: I think MCTS is inherently random, unless you have some statement about that being fixed in some way by Deep Mind for tournament play?
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-24T14:17:54.190Z
Answers.Text: @NeilSlater Pure MCTS is indeed random, since it uses random simulations as the evaluation function. AlphaZero instead uses one of the outputs of the neural network as the value estimate. This makes AlphaZero with a fixed node budget fully deterministic, except for maybe some implementation details (multithreading, GPU batch processing, ...).
Answers.UserDisplayName: KarelPeeters
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-24T14:20:48.233Z
Answers.Text: MCTS also makes random choices earlier than rollout (Selection and Expansion phases). I don't think AlphaZero's truncated rollout fully removes randomness.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-24T14:28:46.127Z
Answers.Text: @NeilSlater There is some varierty in MCTS details, but the vanilla one also has deterministic selection and expansion (which is not actually a distinct step IMO). Regardless, from the [AlphaGo paper](https://www.nature.com/articles/nature24270.pdf), in the description of figure 2, it's pretty clear that selection is deterministically based only on previous neural network outputs.
Answers.UserDisplayName: KarelPeeters
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-23T21:57:21.843Z
Answers.LastActivityDate: 2022-01-26T09:12:52.400Z
Answers.LastEditDate: 2022-01-26T09:12:52.400Z
Answers.UserDisplayName: KarelPeeters
Body: <p>Alphago and AlphaGo zero use random play to generate data and use the data to train DNN. &quot;Random play&quot; means that there is a positive probability for AlphaGo to play some suboptimal moves based on the current DNN; this is for exploring and learning purposes (please correct me if my understanding is wrong).</p>
  <p><strong>In the real tournament, does AlphaGo still play the random moves?</strong> Is the random play feature only used in the training phase?</p>
  <p>If AlphaGo does not play a random move in the real competition, then I think AlphaGo is not learning in that competition. Human players do similar &quot;random play&quot;: they usually play some random moves or strange moves in minor contests, just to test out new strategies; in major tournaments, they will be more serious and play less unprepared moves.</p>
  <p>So, a related and broader question is: does AlphaGo learn from the game it is playing with the human in real-time?</p>
  <p>I think the second question is less important because AlphaGo's learning curve is extremely flat compared to humans: AlphaGo learns epsilon from one single game while human can learn a lot.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-01-23T22:24:00.350Z
Comments.Text: Please, **ask only one question per post**, even if they are related!
Comments.UserDisplayName: nbro
Tags: <deep-rl><alphazero><alphago-zero><alphago>
Title: Does AlphaGo play random moves in a real competition?
UserDisplayName: High GPA
ThreadText: # Does AlphaGo play random moves in a real competition?
  
  (Asked by: username_0 on 2022-01-18)
  
  Alphago and AlphaGo zero use random play to generate data and use the data to train DNN. "Random play" means that there is a positive probability for AlphaGo to play some suboptimal moves based on the current DNN; this is for exploring and learning purposes (please correct me if my understanding is wrong).
  
  **In the real tournament, does AlphaGo still play the random moves?** Is the random play feature only used in the training phase?
  
  If AlphaGo does not play a random move in the real competition, then I think AlphaGo is not learning in that competition. Human players do similar "random play": they usually play some random moves or strange moves in minor contests, just to test out new strategies; in major tournaments, they will be more serious and play less unprepared moves.
  
  So, a related and broader question is: does AlphaGo learn from the game it is playing with the human in real-time?
  
  I think the second question is less important because AlphaGo's learning curve is extremely flat compared to humans: AlphaGo learns epsilon from one single game while human can learn a lot.
  
  **Tags:** deep-rl, alphazero, alphago-zero, alphago
  > **Comments:**
  > **username_1**: Please, **ask only one question per post**, even if they are related!  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_2 on 2022-01-19. Score: 2
  
  **Question 1**: I don't think they ran AlphaGo or AlphaGoZero in training mode during tournament matches because the computing power required for this is really large. I don't recall if this is described in the [documentary](https://www.youtube.com/watch?v=WXuK6gekU1Y) but see this quote from the [AlphaZero paper](https://arxiv.org/pdf/1712.01815.pdf) (page 4):
  
  > using 5,000 first-generation TPUs (15) to generate self-play games and 64 second-generation TPUs to train the neural networks.
  
  **Question 2**: From my first answer, I assume the network is run in inference mode, i.e., taking the observation of the environment as input and outputting the action (next move) according to the strongest strategy of the network. Then the AlphaGo does not learn anything as it does not evaluate whether the taken action is better than the strategy because these are the same. The way that the network learns during training/exploration is by comparing the random action that is taken to the best action known by the network.
  
  ---
  
  You are correct in your understanding of self-play and exploration. This is done in RL to explore actions that might not have been taken yet to explore actions that might be better than the best-known strategy.
  
  But during inference, you would want to greedily take the best-known actions because an action taken at random would most likely be way worse.
  
  > **Comments:**
  > **username_3**: I think you are right for 1 and 2, that the NN was not being trained. However, my understanding is that MCTS was still used to improve on the NN policies, so it is not as cut and dry as this answer implies.  
  > **username_2**: That is true and an important note which I did not consider. MCTS is used in AlphaGo and AlphaZero and described in the respective papers. Although its use is quite limited compared to traditional alpha-beta search engines, such as the Stockfish chess engine.  
  > **username_0**: Many thanks for your contribution! So in the "inference mode", AlphaGo will only choose the "best move"? What if there are two equally best move with the same value?  
  > **username_2**: To my knowledge, I don't think there can be two moves with equal value unless your discount factor is 0, or close to it. With a discount factor of 0, the agent will not consider the value of the future moves which can be determined from the immediate action the agent is about to take. But hypothetically speaking, it would probably be a random selection between actions of equal value.  
  > **username_0**: @Lars Note that the Go board is symmetric so there are some scenarios that two or more moves are absolutely symmetric. If those symmetric moves are not of same value, then the algorithm has a problem. So, in my humble opinion, my question still hold: when two moves have exactly the same value, which move will be chosen?  
  > **username_2**: Actually, I did not consider the symmetry property. You are correct that when the board and stones are symmetrical then two or more moves can have identical values. Moreover, because the value is the same, the possible actions in the future will also be the same regardless of which move is selected. So if they have the highest value of all available moves then it does not matter which of the moves is selected.  
  > **username_4**: @GPA: for ML purposes, you want to parameterize your scoring method using the minimal amount of trainable weights. A scoring algorithm that is asymmetric uses more weights than a symmetric one, so it's definitely worse.  
  
  ---
  
  ### Answer by username_5 on 2023-04-05. Score: 1
  
  AlphaGo/AlphaZero has 3 main sources of randomness during competitive mode:
  
  1. **Move temperature**: The MCTS process outputs a probability distribution P over all candidate moves. The agent chooses a move by sampling from the probability distribution proportional to P^(1/T) for some move temperature T. Typical configurations start T at some value near 1 and decay it quickly to 0 over the course of the game (the limit of P^(1/T) as T approaches 0 is the argmax function). This mechanism helps to ensure, for example, that the agent will not always play the same first move as first player.
  2. **Symmetries**: The game of go has 8-fold symmetry. Before querying the neural network, the agent randomly chooses one of the 8 symmetry transforms of the game and applies it to the board. It then applies the inverse transform to the neural network’s (policy) output. A perfect neural network should exhibit perfect 8-fold symmetry, but in reality the neural network is imperfect and exhibits asymmetrical biases (e.g., it wants to play an atari in board state S, but if you rotate S by 90 degrees, it no longer wants to play an atari). So this operation leads to random deviations in its move choices.
  3. **Tree parallelization**: MCTS is made multithreaded via a mechanism known as *tree parallelization*. The move distribution that MCTS outputs is dependent on the order in which the different threads interleave with each other, which is effectively random.
  
  It is worth noting that any human could easily defeat any deterministic AI in any deterministic game. Simply pit two instances of the AI against each other, memorize the deterministic sequence of moves, and then use those exact same moves against a single copy of the AI. Because of this possibility, game playing agents typically are willing to sacrifice a small amount of playing strength for randomness. Move temperature in particular can be justified for this reason. The other two sources of randomness can be seen as byproducts of engineering optimizations.
  
  In other answers/comments, others have correctly noted that single-threaded MCTS is a deterministic algorithm (if executed purely on CPU). Given a game state, it will always output the same move distribution, absent the symmetry mechanism described above.
  
  
  ---
  
  ### Answer by username_6 on 2022-01-23. Score: 1
  
  The core mechanics of AlphaZero during selfplay and real tournament games are the same: something similar to [Monte Carlo Tree Search](https://en.wikipedia.org/wiki/Monte_Carlo_tree_search) is done but guided by the current neural network instead of random simulations. The network is only doing inference, it's not learning *during* a tree search. There's a great summary diagram [here](https://medium.com/applied-data-science/alphago-zero-explained-in-one-diagram-365f5abf67e0).
  
  The differences between selfplay and tournaments are:
  
  * Selfplay tree searches games get some additional (Dirichlet) noise injected to encourage exploration of different moves and positions. This does not happen during tournament games since that would likely make play weaker.
  * During selfplay moves are selected randomly, but weighed according to how good the tree search thinks certain moves are. This means the entire training process spends most of its time looking at good moves, but still occasionally plays bad moves to keep some variety. During tournaments AlphaZero just plays what it thinks is the best move.
  * Selfplay games are kept in a large buffer with millions of positions, on which the next neural network is trained. This is the only point at which actual network training is happening.
  * Selfplay tree searches only look at ~800 nodes per position, which probably only takes a few milliseconds to calculate. Tournament games take a lot longer, [3h per game + 15s per move](https://en.wikipedia.org/wiki/AlphaZero#Chess_2). This means the tree search visits hundreds of thousands, likely millions of positions for each move, making tournament play a lot stronger than selfplay.
  
  These are the only differences between selfplay and tournament games. One thing to note is that after selfplay/training is done, AlphaZero is just an immutable neural network with some tree search code around it. There is no *learning* happening during a tournament, or any additional randomness injected into the process. Instead, to ensure a diversity of games, an [Opening Book](https://www.chessprogramming.org/Opening_Book) is used.
  
  > **Comments:**
  > **username_3**: I think MCTS is inherently random, unless you have some statement about that being fixed in some way by Deep Mind for tournament play?  
  > **username_6**: @NeilSlater Pure MCTS is indeed random, since it uses random simulations as the evaluation function. AlphaZero instead uses one of the outputs of the neural network as the value estimate. This makes AlphaZero with a fixed node budget fully deterministic, except for maybe some implementation details (multithreading, GPU batch processing, ...).  
  > **username_3**: MCTS also makes random choices earlier than rollout (Selection and Expansion phases). I don't think AlphaZero's truncated rollout fully removes randomness.  
  > **username_6**: @NeilSlater There is some varierty in MCTS details, but the vanilla one also has deterministic selection and expansion (which is not actually a distinct step IMO). Regardless, from the [AlphaGo paper](https://www.nature.com/articles/nature24270.pdf), in the description of figure 2, it's pretty clear that selection is deterministically based only on previous neural network outputs.  
  
  ---
  
  