I play around with Monte Carlo tree search and tic-tac-toe. For now I have followed the Wikipedia article. There is one place, where I am stuck, the selection phase. The given procedure is the following:

  1. Selection: Start from the root and choose child nodes based on their number of $w$, number of playouts $n$ and the number of playouts of the parent $N$ such that one picks the child which maximizes $$w/n + c \sqrt{\frac{\ln(N)}{n}} \,.$$

    Repeat that process until one has found a leaf.

  2. Expansion. Unless that leaf is a terminal node in the game, create one or multiple child nodes. Choose one of them.

  3. Simulation. From the chosen child, play the game until a terminal node is reached.

  4. Backpropagation. Propagate the number of playouts and wins to the root of the tree.

It all sounds fine. I start with a tree consisting of just the root, and that happens to be a non-terminal root. So I just add all the child states that my game offers. Then I uniformly sample from them (random policy) and continue down until the game is over. Backpropagation goes back to the root.

The problem is in the next step where I now have expanded children from the previous expansions. These have $n=0$ playouts because they were not chosen. This makes the given condition undefined. There are multiple ways to work around that, but none make any sense to me.

  • I could just initialize them with $n = 1$. But then the sums of $n$ would not match the parent playout count $N$. This doesn't seem right.
  • If I just insert one of the children into a leaf, it won't be a leaf in the next round. Therefore I will not do an expansion there. This happens on all the levels. This means that my tree will never broaden, but I only play one random trajectory again and again.
  • If I do expand all of them, but only sample from those with $n = 0$ until all have $n \ge 1$, I will expand all nodes on the first level before taking any of them again. This happens again for every level. I don't exactly explore the whole tree, but it feels like I would be exploring a bit too much.
  • If there are children with $n = 0$ and others with $n \ge 1$, I could just choose the argmax from the explored ones with say 90 % chance and randomly sample the others with say 10 %. This sounds like it might work, but I cannot take that from the explanations that I've read so far.

So how do I treat children which I have expanded but still have $n = 0$?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.