19
votes
What is the difference between tree search and graph search?
There is always a lot of confusion about this concept, because the naming is misleading, given that both tree and graph searches produce a tree (from which you can derive a path) while exploring the ...
3
votes
Accepted
MCTS: How to choose the final action from the root
By far the most commonly used strategy is to select the child with the highest number of visits. This is as described in the 2008 paper you linked. It's also what's referred to as the "robust child" ...
- 10.1k
2
votes
Accepted
What is this algorithm? Is it a variant of Monte-Carlo Tree Search?
In short it looks like you have constructed a valid reinforcement learning method, but it does not have much in common with Monte Carlo Tree Search. It may have some weaknesses compared to more ...
- 30.3k
1
vote
If $h_1(n)$ is admissible, why does A* tree search with $h_2(n) = 3h_1(n)$ return a path that is at most thrice as long as the optimal path?
The sketch of the proof for your first question:
for an open node $n$, if $f_1(n) = g(n) + h_1(n)$, in the same situation in using $h_2$, it will be $f_2(n) = g(n) + 3 h_1(n)$. Hence, all the time ...
- 1,751
1
vote
Accepted
What should the initial UCT value be with MCTS, when leaf's simulation count is zero? Infinity?
Assigning a value of $\infty$ to unvisited nodes is indeed the "default" or most basic choice, and it indeed ensures that the search never visits a node for a second time if it also still ...
- 10.1k
1
vote
Accepted
Unclear definition of a "leaf" and diverging UTC values in the Monte Carlo Tree Search
Q1. When expanding the choices at the leaf node L, do I expand all, a few or just one child?
Expanding all nodes or expanding just one node are both possible. There are different advantages and ...
- 10.1k
Only top scored, non community-wiki answers of a minimum length are eligible