3
$\begingroup$

When executing MCTS' expansion phase, where you create a number of child nodes, select one of the numbers, and simulate from that child, how can you efficiently and unbiasedly decide which child(ren) to generate?

One strategy is to always generate all possible children. I believe that this answer says that AlphaZero always generates all possible ($\sim 300$) children. If it were expensive to compute the children or if there were many of them, this might not be efficient.

One strategy is to generate a lazy stream of possible children. That is, generate one child and a promise to generate the rest. You could then randomly select one by flipping a coin: heads you take the first child, tails you keep going. This is clearly biased in favor of children earlier in the stream.

Another strategy is to compute how many $N$ children there are and provide a function to generate child $X < N$ (of type Nat -> State). You could then randomly select one by choosing uniformly in the range $[0, N)$. This may be harder to implement than the previous version because computing the number of children may be as hard as computing the children themselves. Alternatively, you could compute an upper-bound on the number of children and the function is partial (of type Nat -> Maybe State), but you'd be doing something like rejection sampling.

I believe that if the number of iterations of MCTS remaining, $X_t$, is larger than the number of children, $N$, then it doesn't matter what you do, because you'll find this node again the next iteration and expand one of the children. This seems to suggest that the only time it matters is when $X_t < N$ and in situations like AlphaZero, $N$ is so much smaller than $X_0$, that this basically never matters.

In cases where $X_0$ and $N$ are of similar size, then it seems like the number of iterations really needs to be changed into something like an amount of time and sometimes you spend your time doing playouts while other times you spend your time computing children.

Have I thought about this correctly?

Improve this question
$\endgroup$
1
$\begingroup$

The first thing to consider in this question is: what do we mean when we talk about "generating a child/node". Just creating a node for a tree data structure, and allocating some memory (initialised to nulls / zeros) for data like deeper children, visit counts, backpropagated scores, etc., is rarely a problem in terms of efficiency.

If you also include generating a game state to store in that node when you say "generating a node", that can be a whole lot more expensive, since it requires applying the effects of a move to the previous game state to generate the new game state (and, depending on implementation, probably also requires first copying that previous game state). But you don't have to do this generally. You can just generate nodes, and only actually put a game state in them if you later on reach them again through the MCTS Selection phase.

For example, you could say that AlphaZero does indeed generate all the nodes for all actions immediately, but they're generally "empty" nodes without game states. They do get "primed" with probabilities computed by the policy network, but that policy network doesn't require successor states inside those nodes; it's a function $\pi(s, a)$ of the current state $s$ (inside the previous node), and the action $a$ leading to the newly-generated node.

But if you're really sure that, for your particular problem domain, the generation of nodes itself already is inefficient, then...

[...] This is clearly biased in favor of children earlier in the stream.

Yes, you would get a significant bias with such a stream-based approach, probably wouldn't work well.

[...] This may be harder to implement than the previous version because computing the number of children may be as hard as computing the children themselves. [...]

Again I agree with your observation, I don't think there are many problems where this would be a feasible solution.

I believe that if the number of iterations of MCTS remaining, X_t, is larger than the number of children, N, then it doesn't matter what you do, because you'll find this node again the next iteration and expand one of the children.

This would only be correct for the children of the root node. For any nodes deeper in the tree, it is possible that MCTS never reaches them again even if $X_t > N$, because it could dedicate most of it search effort to different subtrees.

I think your solution would have to involve some sort of learned function (like the policy network in AlphaZero) which can efficiently compute a recommendation for a node to generate, only using the inputs that are already available before you pick a node to generate. In AlphaZero's policy network, those inputs would be the state $s$ in your current node, and the outward actions $a$ (each of which could lead to a node to be generated). This would often actually be very far from unbiased, but I imagine a strong, learned bias would likely be desireable anyway if you're in a situation where the mere generation of nodes is a legitimate concern for performance.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ "AlphaZero does indeed generate all the nodes for all actions immediately, but they're generally "empty" node " Not quite empty. They generate Q for each action, and that's because of specific architecture which generate all Q's for state. In general getting Q for action could be expensive, $\endgroup$ – mirror2image Jul 31 '19 at 5:44
  • 1
    $\begingroup$ @mirror2image I don't believe they generate $Q$ for every action. I don't have the paper in front of me, going by memory here, but... their network doesn't output $Q(s, a)$ for actions. It outputs $V(s)$ (value for a single state only, the current state), and $\pi(s, a)$ (the policy's "probability value") for every action available in $s$. Child nodes are only primed with $\pi(s, a)$ values because those are required by the Selection phase when it's in the current node $s$. Child nodes are not primed with $Q$-values (only once the selection phase picks a single child we need a $Q$ value). $\endgroup$ – Dennis Soemers♦ Jul 31 '19 at 8:15
  • 2
    $\begingroup$ Yes you correct, they generate V per state and p for each action. I mistake with different algorithm $\endgroup$ – mirror2image Jul 31 '19 at 9:27
1
$\begingroup$

Dennis' answer is very helpful. I also found section 5.5 of the MCTS survey very useful, in particular the widening discussion. Another useful reference was https://project.dke.maastrichtuniversity.nl/games/files/msc/Roelofs_thesis.pdf

Improve this answer
$\endgroup$

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.