7
$\begingroup$

All sources I can find provide a similar explanation to each phase.

In the Selection Phase, we start at the root and choose child nodes until reaching a leaf. Once the leaf is reached (assuming the game is not terminated), we enter the Expansion Phase.

In the Expansion Phase, we expand any number of child nodes and select one of the expanded nodes. Then, we enter the Play-Out Phase.

Here is my confusion. If we choose to only expand a single node, the nodes that were not expanded will never be considered in future selections as we only select child nodes until a leaf is reached during the Selection Phase. Is this correct? If not, what am I misunderstanding about the Selection Phase?

$\endgroup$
0

1 Answer 1

2
$\begingroup$

If we choose to only expand a single node, the nodes that were not expanded will never be considered in future selections as we only select child nodes until a leaf is reached during the Selection Phase. Is this correct?

No this is not correct.

If not, what am I misunderstanding about the Selection Phase?

The selection phase does not end only when you reach a node that has no expanded nodes. It ends when you reach a node that has any unexpanded nodes. At which point you typically pick one or more nodes you have not yet expanded at that point in the tree, expand them and collect one or more rollout results for them. Variations are possible such as choosing to whether to expand or continue selecting stochastically, or expanding all child nodes at the same time using value estimates to initialise them - the latter is what AlphaZero does.

$\endgroup$
1
  • $\begingroup$ "pick one or more nodes" ... From my reading on MCTS the "picking" is conducted by the Tree Policy which is the argmax of action-values (in some form). The problem when one only expands one node at a time is: how is the argmax supposed to be computed? You at the very least need a placeholder for ALL the action-values of child nodes for the Tree Policy to choose from. Hence it makes sense to always expand all nodes from a selected node in theory (practically there are reasons not to do this e.g. memory usage) $\endgroup$
    – Johan
    Sep 13, 2019 at 10:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .