# How exactly are non-leaves in Monte Carlo tree search chosen?

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