5
$\begingroup$

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?

Improve this question
$\endgroup$
6
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Miguel Saraiva Jul 30 '19 at 15:44
  • $\begingroup$ 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.) $\endgroup$ – DukeZhou♦ Nov 7 '19 at 21:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.