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 its essentially the same as the basic version of MCTS, with a default random policy in the simulation step.

  • 1
    $\begingroup$ Hi. Please, ask just one question per post. I would ask the question about the correctness in another post. $\endgroup$ – nbro Jun 10 at 15:05
  • $\begingroup$ Okay, I edited my question $\endgroup$ – ATidedHumour Jun 10 at 18:52
  • $\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 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 at 18:57
  • 1
    $\begingroup$ You can still quantify the time complexity that depends on some parameter of the problem. $\endgroup$ – nbro Jun 10 at 18:57

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.