1
$\begingroup$

I was reading: https://stackoverflow.com/questions/34724201/whats-the-time-complexity-of-monte-carlo-tree-search

Where it says:

The runtime of the algorithm can be simply be computed as O(mkI/C) where m and k are the same as before, and I is the number of iterations and C is the number of cores available.

According to this definition let's suppose we had a game with a branching factor of b then made some changes to that game so the new branching factor is 5b. How does this affect the run time complexity of MCTS?

From what I see if we run in same environment this doesn't change the run time (as the equation doesn't include b - branching factor) but that doesn't make sense to me...

$\endgroup$
1
  • $\begingroup$ Please insert enough detail from the link so the readers do not have to visit it and study the problem. You write "According to the definition"... No definition is included. $\endgroup$ Jun 29, 2023 at 15:30

1 Answer 1

2
$\begingroup$

Monte-Carlo Tree Search is not an exhaustive search algorithm. It just does a certain amount of iterations, and then it is done. The branching factor has a (dramatic) influence on the size of the search space, but this does not affect the runtime of MCTS.

Note that if the search space is a lot larger, the quality of a result with a fixed number of iterations is likely (much) lower. So if a similar quality of result is required, the number of iterations must also drastically go up. But this is not a requirement like it is with exhaustive search algorithms, you can also simply accept a (relatively) poor quality result. If you are facing an opponent that also can not afford to do an exhaustive search, this is not a problem in of itself.

What does affect the performance of MCTS is the average depth of a game tree, as it means more time has to be spent in random rollouts to get sample outcomes. At least in traditional MCTS, some variants replace the random rollout with estimators such as heuristics or neural networks which may not become more expensive with a higher average depth.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.