5
$\begingroup$

In Monte Carlo Tree Search: What does one do when the Selection step selects a node that is a Terminal state, i.e. a won/lost state (it's by definition a leaf node)? Expansion/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?

I'm confused about this, could someone please point me in the right direction.

$\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$

The question is quite old, but honestly it's hard to find the answer, although now for me it seems obvious.

In the basic form, if you encounter a terminal leaf, you add visits and score depending on whether it's a win or lose, and back propagate 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 -inf, 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 very big positive score or inf, 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 like 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 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.

EDIT: It seems in literature it's called "MCTS Solver", to back propagate proven wins and loses.

$\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.