What is the appropriate way to deal with multiple paths to same state in MCTS?

Question

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?

Answer 1

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.

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 2

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.