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?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
