5
$\begingroup$

For MCTS there is an expansion phase where we make a move and list down all the next states. But this is complicated by the fact that for some games, after making the move, there is a stochastic change to the environment. Consider the game 2048, after I make a move, random tile is generated. So the state of the world after my next move is a mix of possibilities!

How does MCTS work in a stochastic environment? I am having trouble understanding how to keep track of the expansion, do I expand all stochastic possibilities and weight the return via their chance of happening?

Improve this question
$\endgroup$
3
  • $\begingroup$ MCTS has been used for two-player games like Go, so maybe you could consider the random move as simply the move of the opponent. $\endgroup$
    – Varun Vejalla
    Commented Aug 9, 2020 at 0:04
  • $\begingroup$ That is something I don't understand. In Go the player can have hundreds of different responses but you can use a metric to choose a branch (essentially, assuming your opponent plays optimally, but u r guess optimality with a heuristic). with random play you don't know which move will be played so you have to track through all possible moves. $\endgroup$
    – xiaodai
    Commented Aug 9, 2020 at 3:37
  • $\begingroup$ Yeah, I see your point. Maybe you could use random sequences (which are fixed for each tree search) of new tile positions? Of course, you would run into the complication of a new tile overlapping an existing tile in some iterations, so some way of countering that would need to be put in place. $\endgroup$
    – Varun Vejalla
    Commented Aug 9, 2020 at 4:08

1 Answer 1

Reset to default
4
$\begingroup$

I am having trouble understanding how to keep track of the expansion, do I expand all stochastic possibilities and weight the return via their chance of happening?

This is indeed one option you can take. This would be very similar in spirit to the idea of "Expectimax" as a variant of minimax for non-deterministic games, in the sense that you'll include explicit "chance nodes" in your tree. When running into such a chance node later on again during a Selection phase, of a later MCTS iteration, you can just select a path of the tree to follow based on a "dice roll". Importantly, note that this option is only actually available if you have explicit knowledge of exactly when chance events occur, which states they can lead to, and with which probabilities they lead to different states. We also assume that this is feasible, i.e. that you don't have a crazy high (or infinite) number of slightly different game states you could reach.

An alternative option is to use an "open-loop" variant of MCTS. Your nodes would no longer represent game states, but only be representative of the sequence of actions leading to them. You would no longer store any game states in any nodes, but always regenerate them from scratch when traversing the tree, starting from the root node. You would no longer have any explicit chance nodes, but instead have states being representative of larger sets of states that could possibly be reached by following the corresponding path from the root node. For more on this, see my answer to this other question. The advantage of this approach is that it does not require explicit knowledge of all the possible states you can reach due to chance events, do not need explicit knowledge of the probabilities, and can just sample instead of explicitly enumerating every possible outcome.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .