Answers.Body: <p>Node in a tree must have a single parent, otherwise it violates a tree definition. Also the way I look at it, there are no "same" states when you do MCTS. Because you are keeping the history of how you got there. So the second time you visit the "same" state it'll have a different history path and a single parent. </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-30T15:44:47.647Z
Answers.Text: Imagine a game like chess, 2 different paths can reach the same state, and the best play for one of them is the same as for the other. So they kind of come together.
Answers.UserDisplayName: Miguel Saraiva
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-07T21:56:00.787Z
Answers.Text: It seems this touches on the distinction between a game tree and a game graph?  (My sense is, with a "graph", there's a single node for a given game state, where, traversing a tree, there may be multiple nodes having the same state, arrived at by different paths.)
Answers.UserDisplayName: DukeZhou
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-30T12:53:38.777Z
Answers.LastActivityDate: 2019-07-30T12:53:38.777Z
Answers.UserDisplayName: A_P
Answers.Body: <blockquote>
    <p>If the state appears twice in the tree, aren't we wasting a lot of resources thinking about it multiple times?</p>
  </blockquote>
  
  <p>You're right. Precisely the same problem was also noticed decades before MCTS existed, in the classic minimax-style tree search algorithms (alpha-beta search, etc.) that were used in games before MCTS. The solution is also mostly the same; <strong>transposition tables</strong>.</p>
  
  <p>In the case of MCTS, the statistics used by the algorithm that are normally associated with nodes (or their incoming edges) may instead be stored in entries of a transposition table. I mean stuff like visit counts and sums (or averages) of backpropagated scores.</p>
  
  <p>A brief description of how it would work, and references to more extensive relevant literature, can be found in subsubsection 5.2.4 of the <a href="http://mcts.ai/pubs/mcts-survey-master.pdf" rel="noreferrer">well-known 2012 Survey paper on MCTS</a>.</p>
  
  <p>This does require that you can efficiently (incrementally) compute hash values for the states you encounter, which may not always be easy (should usually be possible, depends on the details of your problem domain). Use of transpositions in MCTS is also not always guaranteed to actually improve performance. It does come with computational overhead, and in games where transpositions are very rare it may be more efficient to simply ignore them and use the regular tree structure.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-30T15:47:41.410Z
Answers.LastActivityDate: 2019-07-30T15:47:41.410Z
Answers.UserDisplayName: Dennis Soemers
Body: <p>Many games have multiple paths to the same states. What is the appropriate way to deal with this in MCTS? </p>
  
  <p>If the state appears once in the tree, but with multiple parents, then it seems to be difficult to define back propagation: do we only propagate back along the path that got us there "this" time? Or do we incorporate the information everywhere? Or maybe along the "first" path?</p>
  
  <p>If the state appears once in the tree, but with only one parent, then we ignored one of the paths, but it doesn't matter because by definition this is the same state?</p>
  
  <p>If the state appears twice in the tree, aren't we wasting a lot of resources thinking about it multiple times?</p>
  
Tags: <monte-carlo-tree-search>
Title: What is the appropriate way to deal with multiple paths to same state in MCTS?
UserDisplayName: Jay McCarthy
ThreadText: # What is the appropriate way to deal with multiple paths to same state in MCTS?
  
  (Asked by: username_0 on 2019-07-30)
  
  Many games have multiple paths to the same states. What is the appropriate way to deal with this in MCTS?
  
  If the state appears once in the tree, but with multiple parents, then it seems to be difficult to define back propagation: do we only propagate back along the path that got us there "this" time? Or do we incorporate the information everywhere? Or maybe along the "first" path?
  
  If the state appears once in the tree, but with only one parent, then we ignored one of the paths, but it doesn't matter because by definition this is the same state?
  
  If the state appears twice in the tree, aren't we wasting a lot of resources thinking about it multiple times?
  
  **Tags:** monte-carlo-tree-search
  
  ---
  
  ## 2 answers
  
  ### Answer by username_4 on 2019-07-30. Score: 9 | Accepted answer
  
  > If the state appears twice in the tree, aren't we wasting a lot of resources thinking about it multiple times?
  
  You're right. Precisely the same problem was also noticed decades before MCTS existed, in the classic minimax-style tree search algorithms (alpha-beta search, etc.) that were used in games before MCTS. The solution is also mostly the same; **transposition tables**.
  
  In the case of MCTS, the statistics used by the algorithm that are normally associated with nodes (or their incoming edges) may instead be stored in entries of a transposition table. I mean stuff like visit counts and sums (or averages) of backpropagated scores.
  
  A brief description of how it would work, and references to more extensive relevant literature, can be found in subsubsection 5.2.4 of the [well-known 2012 Survey paper on MCTS](http://mcts.ai/pubs/mcts-survey-master.pdf).
  
  This does require that you can efficiently (incrementally) compute hash values for the states you encounter, which may not always be easy (should usually be possible, depends on the details of your problem domain). Use of transpositions in MCTS is also not always guaranteed to actually improve performance. It does come with computational overhead, and in games where transpositions are very rare it may be more efficient to simply ignore them and use the regular tree structure.
  
  
  ---
  
  ### Answer by username_1 on 2019-07-30. Score: 1
  
  Node in a tree must have a single parent, otherwise it violates a tree definition. Also the way I look at it, there are no "same" states when you do MCTS. Because you are keeping the history of how you got there. So the second time you visit the "same" state it'll have a different history path and a single parent.
  
  > **Comments:**
  > **username_2**: Imagine a game like chess, 2 different paths can reach the same state, and the best play for one of them is the same as for the other. So they kind of come together.  
  > **username_3**: It seems this touches on the distinction between a game tree and a game graph?  (My sense is, with a "graph", there's a single node for a given game state, where, traversing a tree, there may be multiple nodes having the same state, arrived at by different paths.)  
  
  ---
  
  