Monte Carlo Tree Search: Opponent moves before MCTS tree border

2
votes

The MCTS algorithm's steps are:

  1. Selection
  2. Expansion
  3. Simulation
  4. Backpropagation

My question concerns the third step, simulation. We have expanded our decision tree with a new node and simulate the remaining moves until the game ends. This simulation can be split in two parts:

  1. turns in which we utilize the policy from our decision tree
  2. turns in which set random moves for both players (or use a game-specific alternative default policy)

A visualization of the MCTS tree line that separates the two phases is in figure 1 of this publication: http://www.ru.is/faculty/yngvi/pdf/FinnssonB09a.pdf

I'm confused about the first part. To simulate the game, we first take our tree policy in the first node, then the opponent moves, then we take another tree policy move, and so on, until we reach the node that was created in step 2 of the algorithm. What moves do we let the opponent do in between our tree policy moves before we reach the tree line? A randomly moving opponent could do a move that prevents us from taking our next tree policy move. Or is there some other misunderstanding on my part?

1
algorithmartificial-intelligencemontecarlo

1 Answers

0
votes

The new node is at a bottom of a decision tree. This decision tree represents moves for both players. When you are at a node in the tree, the tree contains an exact sequence of moves that end in that position.

The remaining moves are simulated according to the playout-step.

In practice, a computer won't normally need to keep simulating the moves in phase one. Instead it will just cache the position at the node and can then start the playout simulation repeatedly from that point.