Answers.Body: <p>If I understand your question correctly, your goal is to figure out whether or not the quality of your neural network is improving as training progresses.</p>
  <p>The core issue seems to be that you do this by evaluating the playing strength of MCTS+DNN agents, but... the game of Tic-Tac-Toe is so simple, that an MCTS agent even with a completely random DNN (or no DNN at all) is likely already capable of optimal play. So, you cannot measure any improvement in playing strength.</p>
  <p>I would suggest one of the following two solutions:</p>
  <ol>
  <li><p>Instead of evaluating the playing strength of an MCTS+DNN agent, just evaluate the playing strength of a raw DNN without any search. You could simply make this agent play according to the policy head of the network (proportionally or by maximising over its outputs), and ignore the value head. A pure MCTS (without neural network) could be used as the opponent to evaluate against (or you could evaluate against past versions of your DNN).</p>
  </li>
  <li><p>If you do want to continue evaluating MCTS+DNN agents, you could try to severely constrain the amount of computation the MCTS part is allowed to use, such that the MCTS by itself can no longer guarantee optimal play. For example, you could let your MCTS run only, say, 10 or 20 iterations for every root state encountered.</p>
  </li>
  </ol>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-20T20:00:25.660Z
Answers.Text: No that is not the issue.
  I already have more complicated games to evaluate my setup on as well. For tic tac toe, I am already using so few MCTS steps that it isn't playing optimally, but all of that is besides the point. The issue I am having is that my MCTS algorithm is deterministic and since tic tac toe starts the same way each time (with an empty board) and since I reset my MCTS algorithm after each game, then the games ends out playing out in exactly the same way, so even if I ask two MCTS algorithm to play 20 games against each other, they just end up playing the same game 20 times.
Answers.UserDisplayName: Tue
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-21T10:10:35.653Z
Answers.Text: If you're already using so few iterations that it's playing suboptimally, I don't think it should be deterministic anymore. How many iterations are you using exactly? After running that number of iterations, how do you let your MCTS select its move to play? I assume picking whichever move maximises the visit count? In this case, you may have many ties, in which case it'd be very good to use random tie-breaking. The same holds during selection phase (PUCB1 equation): use random tie-breaking.
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-21T11:40:32.343Z
Answers.Text: It is deterministic since there is no element of a MCTS-NN algorithm that is random. This is regardless of whether the algorithm is playing optimally or suboptimally. For a normal MCTS algorithm without neural networks, the random element comes from the playout, where random moves are typically selected, but this randomness is removed with neural networks.
Answers.UserDisplayName: Tue
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-21T11:41:35.123Z
Answers.Text: So the problem I'm having isn't related to how well my algorithm is playing but merely to the deterministic nature of the algorithm. Meaning if I take a MCTS-NN algorithm and perform a deep copy of it and allow both copies to play a game of tic tac toe. Those two games are going to play out in exactly the same fashion no matter how good or bad the algorithms are, because there is no randomness involved.
Answers.UserDisplayName: Tue
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-21T12:00:57.420Z
Answers.Text: @Tue Usually in larger setups I'd still expect there to be some subtle random influences (e.g., random tie-breaking, randomness from multi-threading in parallelised MCTSes, and/or random variance in number of MCTS iterations you can manage to run in given time budget), but I can see why none of those may apply in your setting. My next recommendations would be: (i) just evaluate DNN by itself, with proportional sampling instead of argmax, as I mentioned in answer, or (ii) make your MCTS sample actions proportionally to visit counts, or
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-21T12:02:53.270Z
Answers.Text: (iii) instead of starting evaluating games from empty board, start one evaluation game from every possible opening move. Of course, the disadvantage of the last suggestion is that you no longer evaluate your agent's ability to select a good first move in the "real" (empty) starting state. Oh, and one more suggestion: (iv) run evaluation games against (multiple different) agents that do have some degree of randomness themselves (such as low-budget, untrained MCTSes with random playouts and low iteration counts).
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-20T17:05:31.620Z
Answers.LastActivityDate: 2023-02-20T17:05:31.620Z
Answers.UserDisplayName: Dennis Soemers
Answers.Body: <p>I have to answer since I can't comment yet. I have the exact same problem, all evaluation games make the same moves again and again.</p>
  <p>I currently pick a random first action for both players, but it feels like there should be a better solution. I guess I could reuse the MCTS but that seems like an even worse hack.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-06-18T14:31:52.040Z
Answers.LastActivityDate: 2023-06-18T14:31:52.040Z
Answers.UserDisplayName: PWE
Answers.Body: <p>MCTS bandit phase chooses an action via UCB(1) algorithm. For a given <span class="math-container">$Q(s,a)$</span> and the visit counts of non-leaf node, it chooses an action branch in the tree to descend via:</p>
  <p><span class="math-container">$$ a = \arg \max_{a'}\left[Q(s,a') + c \sqrt{\frac{\log N}{N(s,a')}}\right]$$</span></p>
  <p>The <span class="math-container">$c$</span> parameter is the exploration temperature. If <span class="math-container">$c \gg Q$</span> then the second term always wins and the algorithm should be randomly exploring the whole game tree, without any value-based preference. So, one possible problem could be that your <span class="math-container">$c$</span> is too low.</p>
  <p>Another possible problem is a pretty common misconception about the way MCTS works.  It could be that for a single actual in-game move you are performing one MCTS search step. That's not how it is supposed to work - MCTS can be considered as an <em>online</em> &quot;improvement&quot; algorithm for <em>offline</em> learned value function - one should be performing multiple MCTS searches and build a reasonably large search tree for every in-game move one performs. Quoting <a href="https://en.wikipedia.org/wiki/Monte_Carlo_tree_search" rel="nofollow noreferrer">Wikipedia</a>:</p>
  <blockquote>
  <p>Rounds of search are repeated as long as the time allotted to a move remains. Then the move with the most simulations made (i.e. the highest denominator) is chosen as the final answer.</p>
  </blockquote>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-20T14:06:10.363Z
Answers.Text: I think you are talking about something slightly different here.  The value of c or the number of mcts search steps are irrelevant here. The problem is that before each game I reset the MCTS algorithm, and since the actions are chosen as argmax as you also have in your equation, then the MCTS will always arrive at exactly the same best action as it did in the previous game since the algorithm is deterministic and my initial configuration is the same for each game.
  
  Based on your reply I'm guessing that I'm not supposed to reset the MCTS algorithm before each game.
Answers.UserDisplayName: Tue
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-20T14:09:25.247Z
Answers.Text: @Tue your $Q$ should change though, shouldn't it? Or it just could be that MCTS just perfectly explores the game tree (you said it was tic-tac toe?) then the same perfect game would be played.
Answers.UserDisplayName: Kostya
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-20T14:21:59.713Z
Answers.Text: Yes my Q will change, as the game progresses, but it will change in exactly the same way in the next game I play since I have once again reset the MCTS algorithm.
Answers.UserDisplayName: Tue
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-20T14:42:51.007Z
Answers.Text: @Tue You mentioned the "neural network prior". I assumed you train it or something? The randomness usually comes from the noise in the value estimation in the leaf nodes.
Answers.UserDisplayName: Kostya
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-20T14:54:51.473Z
Answers.Text: Yes, I train the neural network prior to playing it against a previous version, but that also doesn't matter, a neural network is generally also deterministic especially in eval mode. However, I guess that is one difference between MCTSNN methods and MCTS methods. For MCTS methods you generally perform a random playout until you reach a terminal node, which introduces randomness even when starting from exactly the same position, while for MCTSNN you do not have this randomness since you do not do a random playout, but rather let a neural network determine prior policies, and value.
Answers.UserDisplayName: Tue
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-20T17:00:31.897Z
Answers.Text: Yes, you are exactly right. The "classic" MCTS randomness comes from random rollouts. While the exploration in the NN-driven MCTS should come from the NN noise. https://ai.stackexchange.com/a/27234/20538 ... Actually. The AlphaGo paper mentions extra exploration Dirichlet noise added on top of s0 prior - could that help your case?
Answers.UserDisplayName: Kostya
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-20T20:04:17.103Z
Answers.Text: No the Direchlet noise is still deterministic, it just skews the probabilities, which only matters during training where the action is chosen stochastically based on those probabilities.
Answers.UserDisplayName: Tue
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-20T21:02:46.270Z
Answers.Text: "Dirichlet noise" means that you generate a random sample from a (centered) Dirichlet distribution (e.g. `numpy.random.dirichlet`) and add it to your prior. I don't understand how you can call that "deterministic".
Answers.UserDisplayName: Kostya
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-20T21:25:44.310Z
Answers.Text: You are right, I had the idea that adding Dirichlet noise was just a skewing of the probability distributions, but it seems to have a random element to it (I haven't added Direchlet noise to my version yet). However, I believe that AlphaGo only uses Dirichlet noise during self-training and not actually when playing. It isn't completely clear, but if you look in their paper: https://gwern.net/doc/reinforcement-learning/model/alphago/2017-silver.pdf they only mention the noise under self-play. I could definitely be wrong on this though
Answers.UserDisplayName: Tue
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-20T21:49:48.503Z
Answers.Text: It seems that you are right there. Check the "Evaluation" section in the appendix: authors state that for evaluation they set the temperature parameter $\tau = 0$ which basically means that the play is deterministic. In the "Play" section in the appendix they state that the moves are chosen from a stochastic policy with potentially nonzero $\tau$. So, it seems ultimately, that the temperature is the answer to your question ;) If you agree, I could try summarizing that in my answer
Answers.UserDisplayName: Kostya
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-21T11:36:22.610Z
Answers.Text: I agree on the evaluation section, but the play section I read slightly differently. I believe that they are merely referring to what they have written previously, namely that tau is ~0 except for the first 30 moves in each self-play game. But even with Tau ~0 they still have a random element in their self-play from the Direchlet noise.
  So my takeway from this is that they only have random elements in self-play where they have tau=1 for the first 30 moves to give extra randomness, and on top of that they have Direchlet noise for all moves.
Answers.UserDisplayName: Tue
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-20T12:19:56.590Z
Answers.LastActivityDate: 2023-02-20T13:59:18.783Z
Answers.LastEditDate: 2023-02-20T13:59:18.783Z
Answers.UserDisplayName: Kostya
Body: <p>I am currently training a self-playing Monte-Carlo-Tree-Search (MCTS) algorithm with a neural network prior, and it seems to be working pretty well.
  However one problem I have is when I compare my new iteration of the player against the previous version to see whether the new one is an improvement over the previous one.</p>
  <p>Ideally I want to compare the two players to play 20 games of Tic Tac Toe with each being the first player in 10 of them. But what ends up happening is that each of those 10 games play out identically (because the MCTS in each player is reset at the beginning of each game, and since they are playing to win, they both take the play with highest probability, rather than randomly drawing actions based on the probabilities, so each player is making exactly the same decisions as they did in the previous game).</p>
  <p>So I understand why this isn't working, however I'm not sure what people commonly do to fix this problem?
  I could choose to not reset the MCTS between each game?, but that also feels like a weird fix, since the players are then still learning as the games are played, and game 10 would be quite different from game 1, but maybe that is just how people normally do this?</p>
  
Tags: <reinforcement-learning><monte-carlo-tree-search>
Title: MCTS players keep replaying identical games
UserDisplayName: Tue
ThreadText: # MCTS players keep replaying identical games
  
  (Asked by: username_0 on 2023-02-19)
  
  I am currently training a self-playing Monte-Carlo-Tree-Search (MCTS) algorithm with a neural network prior, and it seems to be working pretty well.
  However one problem I have is when I compare my new iteration of the player against the previous version to see whether the new one is an improvement over the previous one.
  
  Ideally I want to compare the two players to play 20 games of Tic Tac Toe with each being the first player in 10 of them. But what ends up happening is that each of those 10 games play out identically (because the MCTS in each player is reset at the beginning of each game, and since they are playing to win, they both take the play with highest probability, rather than randomly drawing actions based on the probabilities, so each player is making exactly the same decisions as they did in the previous game).
  
  So I understand why this isn't working, however I'm not sure what people commonly do to fix this problem?
  I could choose to not reset the MCTS between each game?, but that also feels like a weird fix, since the players are then still learning as the games are played, and game 10 would be quite different from game 1, but maybe that is just how people normally do this?
  
  **Tags:** reinforcement-learning, monte-carlo-tree-search
  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_1 on 2023-02-20. Score: 1
  
  If I understand your question correctly, your goal is to figure out whether or not the quality of your neural network is improving as training progresses.
  
  The core issue seems to be that you do this by evaluating the playing strength of MCTS+DNN agents, but... the game of Tic-Tac-Toe is so simple, that an MCTS agent even with a completely random DNN (or no DNN at all) is likely already capable of optimal play. So, you cannot measure any improvement in playing strength.
  
  I would suggest one of the following two solutions:
  
  1. Instead of evaluating the playing strength of an MCTS+DNN agent, just evaluate the playing strength of a raw DNN without any search. You could simply make this agent play according to the policy head of the network (proportionally or by maximising over its outputs), and ignore the value head. A pure MCTS (without neural network) could be used as the opponent to evaluate against (or you could evaluate against past versions of your DNN).
  2. If you do want to continue evaluating MCTS+DNN agents, you could try to severely constrain the amount of computation the MCTS part is allowed to use, such that the MCTS by itself can no longer guarantee optimal play. For example, you could let your MCTS run only, say, 10 or 20 iterations for every root state encountered.
  
  > **Comments:**
  > **username_0**: No that is not the issue. I already have more complicated games to evaluate my setup on as well. For tic tac toe, I am already using so few MCTS steps that it isn't playing optimally, but all of that is besides the point. The issue I am having is that my MCTS algorithm is deterministic and since tic tac toe starts the same way each time (with an empty board) and since I reset my MCTS algorithm after each game, then the games ends out playing out in exactly the same way, so even if I ask two MCTS algorithm to play 20 games against each other, they just end up playing the same game 20 times.  
  > **username_1**: If you're already using so few iterations that it's playing suboptimally, I don't think it should be deterministic anymore. How many iterations are you using exactly? After running that number of iterations, how do you let your MCTS select its move to play? I assume picking whichever move maximises the visit count? In this case, you may have many ties, in which case it'd be very good to use random tie-breaking. The same holds during selection phase (PUCB1 equation): use random tie-breaking.  
  > **username_0**: It is deterministic since there is no element of a MCTS-NN algorithm that is random. This is regardless of whether the algorithm is playing optimally or suboptimally. For a normal MCTS algorithm without neural networks, the random element comes from the playout, where random moves are typically selected, but this randomness is removed with neural networks.  
  > **username_0**: So the problem I'm having isn't related to how well my algorithm is playing but merely to the deterministic nature of the algorithm. Meaning if I take a MCTS-NN algorithm and perform a deep copy of it and allow both copies to play a game of tic tac toe. Those two games are going to play out in exactly the same fashion no matter how good or bad the algorithms are, because there is no randomness involved.  
  > **username_1**: @username_0 Usually in larger setups I'd still expect there to be some subtle random influences (e.g., random tie-breaking, randomness from multi-threading in parallelised MCTSes, and/or random variance in number of MCTS iterations you can manage to run in given time budget), but I can see why none of those may apply in your setting. My next recommendations would be: (i) just evaluate DNN by itself, with proportional sampling instead of argmax, as I mentioned in answer, or (ii) make your MCTS sample actions proportionally to visit counts, or  
  > **username_1**: (iii) instead of starting evaluating games from empty board, start one evaluation game from every possible opening move. Of course, the disadvantage of the last suggestion is that you no longer evaluate your agent's ability to select a good first move in the "real" (empty) starting state. Oh, and one more suggestion: (iv) run evaluation games against (multiple different) agents that do have some degree of randomness themselves (such as low-budget, untrained MCTSes with random playouts and low iteration counts).  
  
  ---
  
  ### Answer by username_2 on 2023-06-18. Score: 0
  
  I have to answer since I can't comment yet. I have the exact same problem, all evaluation games make the same moves again and again.
  
  I currently pick a random first action for both players, but it feels like there should be a better solution. I guess I could reuse the MCTS but that seems like an even worse hack.
  
  
  ---
  
  ### Answer by username_3 on 2023-02-20. Score: 0
  
  MCTS bandit phase chooses an action via UCB(1) algorithm. For a given $Q(s,a)$ and the visit counts of non-leaf node, it chooses an action branch in the tree to descend via:
  
  $$ a = \arg \max\_{a'}\left[Q(s,a') + c \sqrt{\frac{\log N}{N(s,a')}}\right]$$
  
  The $c$ parameter is the exploration temperature. If $c \gg Q$ then the second term always wins and the algorithm should be randomly exploring the whole game tree, without any value-based preference. So, one possible problem could be that your $c$ is too low.
  
  Another possible problem is a pretty common misconception about the way MCTS works. It could be that for a single actual in-game move you are performing one MCTS search step. That's not how it is supposed to work - MCTS can be considered as an *online* "improvement" algorithm for *offline* learned value function - one should be performing multiple MCTS searches and build a reasonably large search tree for every in-game move one performs. Quoting [Wikipedia](https://en.wikipedia.org/wiki/Monte_Carlo_tree_search):
  
  > Rounds of search are repeated as long as the time allotted to a move remains. Then the move with the most simulations made (i.e. the highest denominator) is chosen as the final answer.
  
  > **Comments:**
  > **username_0**: I think you are talking about something slightly different here.  The value of c or the number of mcts search steps are irrelevant here. The problem is that before each game I reset the MCTS algorithm, and since the actions are chosen as argmax as you also have in your equation, then the MCTS will always arrive at exactly the same best action as it did in the previous game since the algorithm is deterministic and my initial configuration is the same for each game.  Based on your reply I'm guessing that I'm not supposed to reset the MCTS algorithm before each game.  
  > **username_3**: @username_0 your $Q$ should change though, shouldn't it? Or it just could be that MCTS just perfectly explores the game tree (you said it was tic-tac toe?) then the same perfect game would be played.  
  > **username_0**: Yes my Q will change, as the game progresses, but it will change in exactly the same way in the next game I play since I have once again reset the MCTS algorithm.  
  > **username_3**: @username_0 You mentioned the "neural network prior". I assumed you train it or something? The randomness usually comes from the noise in the value estimation in the leaf nodes.  
  > **username_0**: Yes, I train the neural network prior to playing it against a previous version, but that also doesn't matter, a neural network is generally also deterministic especially in eval mode. However, I guess that is one difference between MCTSNN methods and MCTS methods. For MCTS methods you generally perform a random playout until you reach a terminal node, which introduces randomness even when starting from exactly the same position, while for MCTSNN you do not have this randomness since you do not do a random playout, but rather let a neural network determine prior policies, and value.  
  > **username_3**: Yes, you are exactly right. The "classic" MCTS randomness comes from random rollouts. While the exploration in the NN-driven MCTS should come from the NN noise. https://ai.stackexchange.com/a/27234/20538 ... Actually. The AlphaGo paper mentions extra exploration Dirichlet noise added on top of s0 prior - could that help your case?  
  > **username_0**: No the Direchlet noise is still deterministic, it just skews the probabilities, which only matters during training where the action is chosen stochastically based on those probabilities.  
  > **username_3**: "Dirichlet noise" means that you generate a random sample from a (centered) Dirichlet distribution (e.g. `numpy.random.dirichlet`) and add it to your prior. I don't understand how you can call that "deterministic".  
  > **username_0**: You are right, I had the idea that adding Dirichlet noise was just a skewing of the probability distributions, but it seems to have a random element to it (I haven't added Direchlet noise to my version yet). However, I believe that AlphaGo only uses Dirichlet noise during self-training and not actually when playing. It isn't completely clear, but if you look in their paper: https://gwern.net/doc/reinforcement-learning/model/alphago/2017-silver.pdf they only mention the noise under self-play. I could definitely be wrong on this though  
  > **username_3**: It seems that you are right there. Check the "Evaluation" section in the appendix: authors state that for evaluation they set the temperature parameter $\tau = 0$ which basically means that the play is deterministic. In the "Play" section in the appendix they state that the moves are chosen from a stochastic policy with potentially nonzero $\tau$. So, it seems ultimately, that the temperature is the answer to your question ;) If you agree, I could try summarizing that in my answer  
  > **username_0**: I agree on the evaluation section, but the play section I read slightly differently. I believe that they are merely referring to what they have written previously, namely that tau is ~0 except for the first 30 moves in each self-play game. But even with Tau ~0 they still have a random element in their self-play from the Direchlet noise. So my takeway from this is that they only have random elements in self-play where they have tau=1 for the first 30 moves to give extra randomness, and on top of that they have Direchlet noise for all moves.  
  
  ---
  
  