# How to run a Monte Carlo Tree Search MCTS for stochastic environment?

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?

• 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. Aug 9, 2020 at 0:04
• 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. Aug 9, 2020 at 3:37
• 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. Aug 9, 2020 at 4:08