1
$\begingroup$

I think I understand the Monte Carlo Tree search. It goes through the tree until it reaches a leaf node, where it branches (creates a child node). However, the branching only occurs at the leaf nodes (right?). So, a branch never comes out from a non-leaf node. So how could one node have multiple branches (multiple child nodes) coming out of it? Here's a picture, for clarity: enter image description here

So wouldn't that process just keep getting repeated? It's not a leaf node, so the algorithm won't branch (create another child node)... so it has to pick the next node. And since it only has one option, it must pick that one. It just continues down, until it reaches the end. What's the point of that?

I'm probably missing something big here, but all the pages I've look at don't really explain this. It just magically repeats selection, expansion, simulation, and back-propagation, until it constructs a nice tree at the end. How?

EDIT: I figured it usually creates only one child node because of this taken of this source:

In its simplest and most memory efficient implementation, MCTS will add one child node per iteration.

Also, even if you create just two or three, would that really be enough to cover all the possible moves, especially if the branching factor is large? How would one determine how many child nodes to create?

$\endgroup$
  • $\begingroup$ What do you mean by "branches"? Have you read basic descriptions of MCTS? See, e.g., en.wikipedia.org/wiki/Monte_Carlo_tree_search. That description doesn't use the terminology "branches". Can you edit to clarify? $\endgroup$ – D.W. Feb 29 '16 at 6:33
  • $\begingroup$ However, the branching only occurs at the leaf nodes (right?). So, a branch never comes out from a non-leaf node. - FWIW, that sounds backwards to me. $\endgroup$ – 500 - Internal Server Error Feb 29 '16 at 17:11
  • $\begingroup$ @D.W. OK, added some stuff in paranthesis $\endgroup$ – APCoding Feb 29 '16 at 23:50
  • $\begingroup$ Thanks for the edit. That helps. Now, how did you conclude that you never create a child node of a non-leaf node ("a branch never comes out from a non-leaf node")? What source did you read, and where are you concluding that from? That sounds like a faulty conclusion to me, so to answer your question it seems like you're going to need to edit the question to explain why you drew that conclusion from the resources you were reading. For instance, that doesn't match the Wikipedia description, which says "create one or more child nodes" (emphasis added). $\endgroup$ – D.W. Mar 1 '16 at 1:25
  • $\begingroup$ @D.W. Thanks for the feedback! I added the source I looked at. Hope that makes it more clear. $\endgroup$ – APCoding Mar 1 '16 at 4:28
0
$\begingroup$

It sounds like you're reading a summary/overview. You might be reading too much into one sentence there. The sentence says "MCTS will add one child node per iteration". That doesn't mean each node will have only one child after the process finishes. You might have one iteration that adds one child of X, and a later iteration that adds another child of X, and an even later iteration that adds yet another child of X, and so on.

Similarly, nothing says that MCTS is limited to adding only two or three children per node.

$\endgroup$
  • $\begingroup$ Good answer, but: 1) How do you decide when to add a child node when traversing down the graph? and 2) How do you decide how many child nodes to create? $\endgroup$ – APCoding Mar 2 '16 at 1:37
  • $\begingroup$ @APCoding, those are excellent questions, but they're different questions, so they belong in a new question. But before you post a new question asking that, I recommend you first find a more thorough reference on MCTS and read that and see if you can figure it out on your own -- that will enable you to ask a more focused, informed question. Reading an overview/summary won't be enough; you need to read the detailed material, and you should do that before asking. $\endgroup$ – D.W. Mar 2 '16 at 1:57

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.