I am writing a report where I used a slightly modified version of MCTS (not parallelized). I thought It could be interesting if I could calculate its time complexity. I'd appreciate any help I could get.

Here's the rough idea of how it works:

Instead of tree search, I'm using graph search meaning I keep a list of visited nodes in order to avoid adding duplicate nodes.

So in the expansion phase, I add all child nodes of the current node that aren't present elsewhere in the tree.

For the remaining phases, it's essentially the same as the basic version of MCTS, with a default random policy in the simulation step.

  • $\begingroup$ Are you sure it makes sense to talk about time complexity in MCTS? It does not have a end or a certain amount of iterations you should do in each node, it is always relative for the problem you are trying to solve. $\endgroup$ – Miguel Saraiva Jun 10 '19 at 18:54
  • $\begingroup$ I actually agree, my professor suggested it and I wanted to either calculate the complexity or have a good argument justifying why I didn't do it. $\endgroup$ – ATidedHumour Jun 10 '19 at 18:57
  • 1
    $\begingroup$ You can still quantify the time complexity that depends on some parameter of the problem. $\endgroup$ – nbro Jun 10 '19 at 18:57
  • $\begingroup$ I would like to note that the time complexity of an algorithm actually depends on the implementation. For example, the usage of different data structures can affect the time complexity. So, I would suggest you to link us to or add to your post the algorithm (or its pseudocode) that you implemented. Furthermore, maybe this would be a question better asked on https://cs.stackexchange.com, even though I would say it is on-topic here too. $\endgroup$ – nbro Jun 10 '19 at 19:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.