1
$\begingroup$

I'm curious how you would apply Monte Carlo Tree Search to a game that has a random initial state. You generate a tree where the root node is the initial state, then you expand if the options from that state are not explored yet.

I'm also wondering how this works in 2 player games. After your opponent moves, does each state in the tree have a key to look up in a dictionary? Otherwise, the algorithm won't know what to do when there's a jump in a state between choosing your action on your turn and when your opponent moves, unless you also store your opponent's move in the tree.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

If the initial state is not always the same, but if your agent is allowed to observe what the initial state is before it has to start running the search algorithm, there's basically no problem; it has all the information it needs when it starts running the tree search. This is how we typically use MCTS (or any other tree searches): we first observe what the current state looks like, and then start running the tree search for this state.

If for whatever reason you already have to start running your tree search without being allowed to observe which initial state has been randomly drawn, you can easily just pretend that you actually do have a "dummy", deterministic initial state which you can observe right before the real initial state, and pretend that the random sampling of an initial state is actually a random event / random transition resulting from a "dummy action". Then you can handle this scenario in exactly the same way that you would any normal game that has non-deterministic transitions (such as games that involve dice): if you have access to explicit knowledge of which stochastic events are possible, and what their probabilities are, you can encode them as chance nodes. If you do not have such explicit knowledge available, you can use an "open-loop" MCTS. See also: https://ai.stackexchange.com/a/13919/1641

Presence of opponents / other players in the game is a different issue. MCTS and other game tree search algorithms were designed specifically for this, they have no problems handling that. In a tree search, you do not just have nodes for your own agent and the states in which it is allowed to act; you also have nodes for any opponents and any states in which they are allowed to act, and the tree search enables you to reason about what actions your opponents are likely to take.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Does that mean you keep in memory multiple trees with the root being different starting states? Also how does MCTS handle an opponent, because it plays in simulation there's going to be a jump in state not caused by the agent. Does this mean every state is stored in a dictionary so the agent can locate that subtree? What does MCTS do if it reaches a state not in it's tree? $\endgroup$
    – user8714896
    Feb 7, 2021 at 13:20
  • $\begingroup$ @user8714896 No, a single search tree is sufficient. If you're dealing with the first case from my answer (where you can observe the state you're actually starting in), any part of the search space that starts with a different initial state from the one you're really in is completely irrelevant, you don't even generate any search tree for any of those other cases. If you're dealing with the second case from my answer, you have a single tree, but multiple different cases below the root in the tree (i.e., different subtrees) $\endgroup$
    – Dennis Soemers ♦
    Feb 7, 2021 at 13:28
  • $\begingroup$ States in which the opponent picks the action have nodes in the search tree in exactly the same way that states in which your agent is the mover do. There's nothing special about them. Your agent can reason about what your opponent would like to do in those nodes, and simulate actions accordingly. When you've moved on to your next turn, you can either just start off with a brand new search tree, or reuse relevant parts of the previous search tree (by following the moves that you made as well as those that your opponent made, and discarding the other subtrees below the old root) $\endgroup$
    – Dennis Soemers ♦
    Feb 7, 2021 at 13:30

You must log in to answer this question.

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