18 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" ...
user avatar
  • 9,369
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 ...
user avatar
  • 23.8k
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 ...
user avatar
  • 1,663
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 ...
user avatar
  • 9,369
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 ...
user avatar
  • 9,369

Only top scored, non community-wiki answers of a minimum length are eligible