Can you add the citation using ieee format?
zooz92
analysis3.docxAnalysis of Monte Carlo Prime Algorithm:
Time Complexity The runtime of the algorithm can be simply be computed as O(mkI/C)O(mkI/C) where mm is the number of random children to consider per search and kk is the number of parallel searches, and II is the number of iterations and CC is the number of cores available.
Memory Complexity The memory complexity is O(mk)O(mk) since in each iteration we map mkmk states over the cluster.
time complexity of Monte Carlo Tree Search (MCTS)
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
The running time depends heavily on the implementation.
Let n be an odd integer. Take a random number a from a uniform distribution on the set $\{1, 2,\cdots, n -1\}$. If a and n are relatively prime, compute the residue $\varepsilon \equiv a^{(n - 1)/2}(\bmod n)$, where $ - 1 \leqq \varepsilon < n - 2$, and the Jacobi symbol $\delta = (a /n)$. If $\varepsilon = 6$, decide that n is prime. If either $\gcd (a,n) > 1$ or $\varepsilon \ne \delta $ decide that n is composite. Obviously, if n is prime, the decision made will be correct. We will show below, that for composite n the probability of an incorrect decision is $\leqq 1 / 2$. The number of multiprecision operations needed for the whole procedure is $< 6\log _2 n$. m-fold repetition using independent random numbers yields a Monte-Carlo test for primality with error probabilities 0 (if n is prime) and $< 2^{-m}$(if n is composite) and with multiprecision arithmetic cost $< 6m\log _2 n$.
Links
https://cs.stackexchange.com/questions/51726/whats-the-time-complexity-of-monte-carlo-tree-search
https://www.jstor.org/stable/2007414?seq=1
