5
$\begingroup$

In Monte Carlo tree search, what should we do when the selection step selects a terminal state (i.e. a won or lost state), which is, by definition, a leaf node? Expansion and simulation is not in order, as it's game over, but does the tree (score/visits) need to be updated (backpropagation)? Won't this particular node be selected continuously?

$\endgroup$
  • 1
    $\begingroup$ the way I understand it, once a terminal state is reached, the algorithm backs up irrespective of the simulation state. however, i am not very confident. i am willing to be corrected :-) $\endgroup$ – okkhoy May 18 '17 at 14:21
4
$\begingroup$

In the basic form, if you encounter a terminal leaf, you add visits and score depending on whether it is a win or loss, and backpropagate accordingly. The same as if you made a simulation step, but in this case the "simulation" is instant.

But you can improve that: If the leaf is losing, you can give it a very large negative score or even $-\infty$, so in the next selection step it surely won't be chosen, unless other moves are as bad. But if it is a winning leaf, you not only can give it a very big positive score or $\infty$, but also add a negative score for the immediate parent, so the parent won't be chosen, as it is obviously a losing state for him. This way we can save some simulations. I had encountered that situation many times in my game and Monte Carlo tree searches.

Suppose the parent has $200$ unexplored children, $10$ of which are immediate wins for the opponent. Your search may explore $100$ non-winning children and have a score of 80/100. But then it encounters the terminate child. After that, normally, it would have $80/101$, so, still, a big chance to be chosen in the next iteration. And it would take many iterations to see that this is not a good move, as it would need to get like $80/150$ or more. But if we cancel out the score or give it a negative one like $-1/101$, then we ensure it won't be chosen.

It seems in literature it's called "MCTS solver", to backpropagate proven wins and losses.

| improve this answer | |
$\endgroup$

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.