Answers.Body: <p>I think I came up with an intuitively good solution. During the selection phase, if in the current state it's the opponent's turn to play then the winrate in the UCT formula becomes <code>1.0 - winrate</code> instead. This should make us invest more in good opponent moves rather than bad ones.</p>
  <p>I am implementing MCTS for Quoridor at the moment I ll update if it works better or not when I am done.</p>
  <p>Edit: Yup, this seems to be the way. Now the tree is symmetrical and we can also generate moves for the opponent as well.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-08-09T06:29:36.987Z
Answers.LastActivityDate: 2021-08-19T15:06:08.917Z
Answers.LastEditDate: 2021-08-19T15:06:08.917Z
Answers.UserDisplayName: Michael
Answers.Body: <p>The original (vanilla) MCTS use <strong>random</strong> rollouts.  In some games this is enough to produce a strong agent.  However, in most of the games, using a <strong>heuristic</strong> that finds the opponent's likely moves makes stronger agents.  There is another line of practice that uses <strong>Opponent Modeling</strong> to predict the opponent moves.  That is important in games where you have several opponent &quot;types&quot; or when an opponent can go for different goals.</p>
  <p>From my experience, a good heuristic can greatly improve the agent.  I have implemented UCT agents for Spades (the card game).  I made a vanilla UCT and one that uses a different (simpler) agent as heuristic.  The second UCT is stronger.</p>
  <p>Picture from <a href="https://en.wikipedia.org/wiki/Monte_Carlo_tree_search" rel="nofollow noreferrer">wiki:MCTS</a>
  <a href="https://i.sstatic.net/wZAqy.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/wZAqy.png" alt="Step of Monte Carlo tree search." /></a></p>
  <p>The four phases of MCTS:</p>
  <blockquote>
  <p><strong>Selection</strong>: Start from root R and select successive child nodes until a leaf node L is reached. The root is the current game state and a leaf is any node that has a potential child from which no simulation (playout) has yet been initiated. The section below says more about a way of biasing choice of child nodes that lets the game tree expand towards the most promising moves, which is the essence of Monte Carlo tree search.</p>
  </blockquote>
  <blockquote>
  <p><strong>Expansion</strong>: Unless L ends the game decisively (e.g. win/loss/draw) for either player, create one (or more) child nodes and choose node C from one of them. Child nodes are any valid moves from the game position defined by L.</p>
  </blockquote>
  <blockquote>
  <p><strong>Simulation</strong>: Complete one random playout from node C. This step is sometimes also called playout or rollout. A playout may be as simple as choosing uniform random moves until the game is decided (for example in chess, the game is won, lost, or drawn).</p>
  </blockquote>
  <blockquote>
  <p><strong>Backpropagation</strong>: Use the result of the playout to update information in the nodes on the path from C to R.</p>
  </blockquote>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-08-05T16:00:29.887Z
Answers.Text: Interesting input. I am not talking about the rollout phase though. I am talking about the tree itself. 
  
  
  For example, I believe AlphaGo prunes candidate moves in the tree by only considering moves deemed "worthy" from a neural network. That is, it doesn't fully expand each node based on all possible moves. 
  
  
  Hence it won't consider bad moves for the opponent, therefore avoiding our agent from dreaming that it will ever get to such states (where he would probably win).
Answers.UserDisplayName: Michael
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-08-06T16:03:49.540Z
Answers.Text: Added a picture from wiki that describe the four phases of a MCTS step.  What phase are you asking about?  I think you are talking about the Simulation phase, where the algorithm plays for all the players until it reaches a the game's end and can evaluate the score.
Answers.UserDisplayName: Cohensius
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-08-07T16:24:02.427Z
Answers.Text: No, I am talking about the selection phase and the moves we consider there on each expansion. Those moves could be all of the legal moves but maybe it should be only good moves to prevent the problem I discuss in my post.
Answers.UserDisplayName: Michael
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-08-07T20:51:56.613Z
Answers.Text: In the selection phase, MCTS choses the node to expand, those nodes are the agent's moves.  I think the problem you talking about is in the Simulation phase, where the algorithm guesses the opponents' moves.
Answers.UserDisplayName: Cohensius
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-08-07T20:55:32.717Z
Answers.Text: Wiki:MCTS explains the four phases well.  In the Selection phase we only choose a node, then expend it by 1 move (our move), then in the simulation phase we playout to the game's end (only here we consider opponents moves).
Answers.UserDisplayName: Cohensius
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-08-08T12:52:15.943Z
Answers.Text: To quote your answer `Child nodes are any valid moves from the game position defined by L.`. Some child nodes are caused by possible opponent moves on a state. These are the moves I am refering to.
Answers.UserDisplayName: Michael
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-08-08T13:39:24.007Z
Answers.Text: No, it is the agent turn to play, all the moves are her to play.  Selection phase will select one of her moves to expend. In the Simulation phase the agent will need to decide what the opponent might do in case we get to that state.
Answers.UserDisplayName: Cohensius
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-08-08T17:40:07.077Z
Answers.Text: Wait a second. That's what I asked in the beginning. You re saying that in the game tree all the edges correspond to moves from our agent? What about the enemy moves? We can't assume what the enemy will play and continue. We need to expand according to enemy moves as well. I believe that's what the coloring signifies in your picture; whose turn it is to play the next move.
Answers.UserDisplayName: Michael
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-08-05T12:51:09.613Z
Answers.LastActivityDate: 2021-08-07T20:58:09.763Z
Answers.LastEditDate: 2021-08-07T20:58:09.763Z
Answers.UserDisplayName: Cohensius
Body: <p>Suppose we have a two player game like Tic Tac Toe where the two players take turns to play their moves. It is my understanding that in the game tree that MCTS builds, consecutive levels in the tree correspond to different player's turns.</p>
  <p>So, for instance, in the root node it is Player1's turn to play, in the children of the root node it is Player2's turn to play, in the children of those children it is Player1's turn again, etc.</p>
  <p>Is that correct?</p>
  <p>If so, is it really prudent to treat nodes where it's the enemy's turn to play the same as those where we choose the next action (i.e. by averaging rollout results in backpropagation). Since, it's not us choosing the next action but the enemy, shouldn't we &quot;pick&quot; the minimum &quot;return&quot; (like in minimax) in those cases instead of the average like we do for nodes where we get to pick the next action?</p>
  <p>By picking I mean to only count the win ratio of that child node (i.e. the minimum win ratio).</p>
  <p>I suspect I am missing something (e.g. that might mess up exploration vs exploitation with UCT) but I can't put my finger on it.</p>
  <p>What do you guys think about this?</p>
  <p>Edit: Maybe a solution to this is only considering good moves for the opponent? But then again.. how do we define good? Heuristics?</p>
  
Tags: <game-ai><monte-carlo-tree-search><minimax>
Title: How does one handle different player turns in MCTS?
UserDisplayName: Michael
ThreadText: # How does one handle different player turns in MCTS?
  
  (Asked by: username_0 on 2021-08-04)
  
  Suppose we have a two player game like Tic Tac Toe where the two players take turns to play their moves. It is my understanding that in the game tree that MCTS builds, consecutive levels in the tree correspond to different player's turns.
  
  So, for instance, in the root node it is Player1's turn to play, in the children of the root node it is Player2's turn to play, in the children of those children it is Player1's turn again, etc.
  
  Is that correct?
  
  If so, is it really prudent to treat nodes where it's the enemy's turn to play the same as those where we choose the next action (i.e. by averaging rollout results in backpropagation). Since, it's not us choosing the next action but the enemy, shouldn't we "pick" the minimum "return" (like in minimax) in those cases instead of the average like we do for nodes where we get to pick the next action?
  
  By picking I mean to only count the win ratio of that child node (i.e. the minimum win ratio).
  
  I suspect I am missing something (e.g. that might mess up exploration vs exploitation with UCT) but I can't put my finger on it.
  
  What do you guys think about this?
  
  Edit: Maybe a solution to this is only considering good moves for the opponent? But then again.. how do we define good? Heuristics?
  
  **Tags:** game-ai, monte-carlo-tree-search, minimax
  
  ---
  
  ## 2 answers
  
  ### Answer by username_0 on 2021-08-09. Score: 0 | Accepted answer
  
  I think I came up with an intuitively good solution. During the selection phase, if in the current state it's the opponent's turn to play then the winrate in the UCT formula becomes `1.0 - winrate` instead. This should make us invest more in good opponent moves rather than bad ones.
  
  I am implementing MCTS for Quoridor at the moment I ll update if it works better or not when I am done.
  
  Edit: Yup, this seems to be the way. Now the tree is symmetrical and we can also generate moves for the opponent as well.
  
  
  ---
  
  ### Answer by username_1 on 2021-08-05. Score: 1
  
  The original (vanilla) MCTS use **random** rollouts. In some games this is enough to produce a strong agent. However, in most of the games, using a **heuristic** that finds the opponent's likely moves makes stronger agents. There is another line of practice that uses **Opponent Modeling** to predict the opponent moves. That is important in games where you have several opponent "types" or when an opponent can go for different goals.
  
  From my experience, a good heuristic can greatly improve the agent. I have implemented UCT agents for Spades (the card game). I made a vanilla UCT and one that uses a different (simpler) agent as heuristic. The second UCT is stronger.
  
  Picture from [wiki:MCTS](https://en.wikipedia.org/wiki/Monte_Carlo_tree_search)
  [![Step of Monte Carlo tree search.](https://i.sstatic.net/wZAqy.png)](https://i.sstatic.net/wZAqy.png)
  
  The four phases of MCTS:
  
  > **Selection**: Start from root R and select successive child nodes until a leaf node L is reached. The root is the current game state and a leaf is any node that has a potential child from which no simulation (playout) has yet been initiated. The section below says more about a way of biasing choice of child nodes that lets the game tree expand towards the most promising moves, which is the essence of Monte Carlo tree search.
  
  > **Expansion**: Unless L ends the game decisively (e.g. win/loss/draw) for either player, create one (or more) child nodes and choose node C from one of them. Child nodes are any valid moves from the game position defined by L.
  
  > **Simulation**: Complete one random playout from node C. This step is sometimes also called playout or rollout. A playout may be as simple as choosing uniform random moves until the game is decided (for example in chess, the game is won, lost, or drawn).
  
  > **Backpropagation**: Use the result of the playout to update information in the nodes on the path from C to R.
  
  > **Comments:**
  > **username_0**: Interesting input. I am not talking about the rollout phase though. I am talking about the tree itself.    For example, I believe AlphaGo prunes candidate moves in the tree by only considering moves deemed "worthy" from a neural network. That is, it doesn't fully expand each node based on all possible moves.    Hence it won't consider bad moves for the opponent, therefore avoiding our agent from dreaming that it will ever get to such states (where he would probably win).  
  > **username_1**: Added a picture from wiki that describe the four phases of a MCTS step.  What phase are you asking about?  I think you are talking about the Simulation phase, where the algorithm plays for all the players until it reaches a the game's end and can evaluate the score.  
  > **username_0**: No, I am talking about the selection phase and the moves we consider there on each expansion. Those moves could be all of the legal moves but maybe it should be only good moves to prevent the problem I discuss in my post.  
  > **username_1**: In the selection phase, MCTS choses the node to expand, those nodes are the agent's moves.  I think the problem you talking about is in the Simulation phase, where the algorithm guesses the opponents' moves.  
  > **username_1**: Wiki:MCTS explains the four phases well.  In the Selection phase we only choose a node, then expend it by 1 move (our move), then in the simulation phase we playout to the game's end (only here we consider opponents moves).  
  > **username_0**: To quote your answer `Child nodes are any valid moves from the game position defined by L.`. Some child nodes are caused by possible opponent moves on a state. These are the moves I am refering to.  
  > **username_1**: No, it is the agent turn to play, all the moves are her to play.  Selection phase will select one of her moves to expend. In the Simulation phase the agent will need to decide what the opponent might do in case we get to that state.  
  > **username_0**: Wait a second. That's what I asked in the beginning. You re saying that in the game tree all the edges correspond to moves from our agent? What about the enemy moves? We can't assume what the enemy will play and continue. We need to expand according to enemy moves as well. I believe that's what the coloring signifies in your picture; whose turn it is to play the next move.  
  
  ---
  
  