5
$\begingroup$

I'm confused regarding a specific detail of MCTS.

To illustrate my question, let's take the simple example of tic-tac-toe. After the selection phase, when a leaf node is reached, the tree is expanded in the so-called expansion phase. Let's say a particular leaf node has 6 children. Would the expansion phase expand all the children and run the simulation on them? Or would the expansion phase only pick a single child at random and run simulation, and only expand the other children if the selection policy arrives at them at some later point?

Alternatively, if both of these are accepted variants, what are the pros/cons of each one?

$\endgroup$
2
$\begingroup$

By far the most common (and likely also the most simple / straightforward) implementation is to expand exactly one node in the Expansion Phase; specifically, the node corresponding to the very first state selected (semi-)randomly by the Play-Out Phase. This is also pretty much the bare minimum you have to do if you want any form of tree growing at all (which you do).


Other variants are possible too, but are much less common. The variant you suggest in the question is to expand all the children of the final node encountered during the Selection Phase, and run a Play-Out for all of them. I am not familiar with any literature on such a strategy really, never tried that myself. Intuitively, I would expect it to perform very similarly, perhaps slightly worse. Essentially what this would do is that it moves the "behaviour" of the search algorithm slightly more towards Breadth-First Search behaviour, rather than Best-First search behaviour. You spend a bit less of your computation time in the Selection Phase, because every Selection Phase is followed up by for example 6 (or whatever branching factor you have) Play-Outs instead of just a single one. On average I'd expect this to be slightly worse, because the Selection Phase is the primary source of the "Best-First Search" behaviour of the algorithm. I certainly don't expect a change like this to cause a large difference in performance though, if any. It will also likely be domain-dependent; worse in some cases, better in other cases.


A different variant that I did once use myself is to expand every node in the complete line of play followed by the Play-Out phase. You can visualize this as a very "thin", but "deep" expansion, whereas your suggestion discussed above would be visualized as a "shallow" but "wide" expansion (and the conventional expansion strategy of a single node would be "thin" and "shallow").

For this strategy, it is much easier to clearly define the advantages and disadvantages that it has in comparison to the standard strategy. The main advantage is that you retain more information from your Play-Outs, you throw less information away. This is because the Backpropagation phase, after the Play-Out terminates, can only store information in nodes that exist. If you immediately expand the complete line of play followed in the Play-Out Phase, you can store the result (the evaluation in the terminal state) in all of those nodes. If you don't expand the complete Play-Out (e.g. only expand the very first node), you'll have to "skip" all of those nodes which you didn't expand yet (they don't exist), and you can't store results in there yet.

The main disadvantage of this approach is that it requires more memory, the tree grows a lot more quickly.

I would personally recommend this approach if you have very strict limitations on computation time, if you expect to be able to only run very few iterations of the MCTS algorithm. For example, I personally used this in my General Video Game AI agent; this is a real-time game where you have to make decisions every ~40 milliseconds. In such a low amount of time, you cannot run many MCTS simulations. This means that:

  1. You do not expect to run out of memory, even if you grow your tree very quickly, so the increased memory requirements become a non-issue.
  2. Due to the low expected number of iterations, it is extremely important to retain as much information as possible, not throw any information away. If we can't run many simulations, we want to make sure to squeeze every little bit of information we can out of each of them.

For contrast, if you're developing an agent to play a board game, and it has in the order of multiple minutes of thinking time per turn, the standard approach of only expanding a single node per Expansion Phase becomes a lot more appealing. If you're capable of running tens of thousands of iterations or more, it really doesn't hurt if you "forget" about a little bit of information deep down in the tree. The risk of running out of memory also becomes a lot more serious if you're running many iterations, so you don't want to grow the tree too quickly.

$\endgroup$
  • 1
    $\begingroup$ Excellent answer. Well formulated and clear. Your alternative variation at the end is fascinating. Quick followup: In the most common variation, nodes can have some children explored, some unexplored. Lets say I'm using UCT to balance exploration/exploitation. How would that work? I assume I would first look at unexplored nodes, and only apply confidence intervals once all children have been explored at least once. Is that correct? Thank you $\endgroup$ – chessprogrammer Sep 7 '18 at 19:12
  • 2
    $\begingroup$ @chessprogrammer Yes that's correct. Prioritize children that have not been visited yet, only really use the UCB1 equation in the Selection phase if all children already have a visit count of at least 1. $\endgroup$ – Dennis Soemers Sep 7 '18 at 19:29

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.