3
$\begingroup$

I'm trying to find the time complexity of Monte Carlo Tree Search (MCTS). Googling doesn't help, so I'm trying to see how far I get calculating it myself.

It does four steps for n iterations, or before the time runs out. So we'll have

O(n*(selection+expansion+simulation+backpropagation))

Expansion just adds a child to the currently selected node. Assuming you're not using a singly linked list or something like that to store tree children, this can happen in constant time, so we can exclude it:

O(n*(selection+simulation+backpropagation))

Given the branching factor b, and d as the depth of our tree, I'm assuming the selection phase runs in O(b*d), because at each level, the selection phase goes to all the children of the previous node.

So our time complexity becomes

O(n*(b*d+simulation+backpropagation))

Backpropagation takes time proportional to the depth of the tree as well, so that becomes:

O(n*(b*d+simulation+d))

But now I'm not sure how to add the simulation phase to this. It'll be proportional to the depth of the tree, but for each iteration, the running time depends heavily on the implementation as far as I know.

What's monte carlo tree search

Monte Carlo Tree Search (MCTS) is a tree search algorithm that tries to find the best path down a decision tree, mostly used for game playing. In games with a high branching factor, it can often go deeper than algorithms like Minimax, even with Alpha-Beta pruning, because it only looks into nodes that look promising. For a certain number of iterations (or a certain amount of time), the algorithm goes through these four phases:

Selection Starting at the root node, go down the tree until you find a node that is not fully expanded, or a leaf node. At each level, select the child that looks most promising. There are many ways of making this selection, but most implementations (including mine) use UCB1.

expansion Expand the selected child by looking at one of its unexplored children.

simulation Simulate a "rollout" from the newly discovered child. Again, there are many ways to do this, but many implementations just take a random child until it reaches an end node. Take note of whether the simulation resulted in a success or a failure (win or loss in the case of a game).

backpropagation update the information about this node, and all nodes along the path back to the root. Most implementations store two values at each node: the number of times it was part of a selection path that lead to a success, and the total number of times it was part of a selection path. These values are used during the selection phase.

After you've run this for as long as you can, the child node of the root that looks most promising is the action to take next. enter image description here

$\endgroup$
  • $\begingroup$ Simulation takes $O(D)$, where $D$ is the depth of the tree (in one of the other phases you use the bound $D = O(\log_b t)$, though it doesn't hold in general). $\endgroup$ – Yuval Filmus Jan 11 '16 at 16:21
  • $\begingroup$ You're right, So can I assume that the running time of MCTS is O(n*(\b*d+d+d)), and so would the running time become O(n*(b+2)*d)? And that would be equivalent to O(nbd), right? Sorry, I'm not good at complexity analysis, but eager to learn. $\endgroup$ – bigblind Jan 11 '16 at 16:52
  • $\begingroup$ Yes, that sounds reasonable. $\endgroup$ – Yuval Filmus Jan 11 '16 at 17:01
  • $\begingroup$ Nice to see more and more people showing interest in Monte Carlo Tree Search. Your reasoning sounds reasonable, but be aware that n, b and/or d themselves might be (grow) exponential(ly), depending on what problem you're trying to solve. $\endgroup$ – Auberon Jan 13 '16 at 1:53
  • $\begingroup$ We're comparing different algorithms on the game Gipf. Most moves have 42 possible actions, causing b to be around 4. I'm not sure how much I can say about d. I could probably come up with a lower bound for it. Since tyou can end up in the same state after a couple of moves, d could be said to be infinite. $\endgroup$ – bigblind Jan 13 '16 at 3:30
1
$\begingroup$

According to http://stanford.edu/~rezab/classes/cme323/S15/projects/montecarlo_search_tree_report.pdf

Time Complexity
The runtime of the algorithm can be simply be computed as $O(mkI/C)$
where $m$ is the number of random children to consider per search and $k$ is the number of parallel searches, and $I$ is the number of iterations and $C$ is the number of cores available.

Memory Complexity
The memory complexity is $O(mk)$ since in each iteration we map $mk$ states over the cluster.

$\endgroup$
  • $\begingroup$ Note that this is the second hit on google. It does not look like you tried very hard. $\endgroup$ – Johan May 1 '16 at 12:18

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.