Questions tagged [tree-search]

For questions related to the tree search. As opposed to the graph search, a tree search does not use a closed list to keep track of the already visited nodes, so a tree search may visit the same nodes (or states) multiple times.

Filter by
Sorted by
Tagged with
3
votes
1answer
48 views

What is this algorithm? Is it a variant of Monte-Carlo Tree Search?

I'm using a Neural Network as an agent in a simple car racing game. My goal is to train the network to imitate a brute-force tree search to an arbitrary depth. My algorithm goes something like the ...
2
votes
1answer
89 views

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?

Consider a heuristic function $h_2(n) = 3h_1(n)$. Where $h_1(n)$ is admissible. Why are the following statements true? $A^*$ tree search with $h_2(n)$ will return a path that is at most thrice as ...
1
vote
1answer
102 views

Find the expected reward in an expectimax-based dice rolling game?

I have this question that I'm kinda stuck on. It's a game scenario in which we set up an expectimax tree. In the game, you have 3 dice with sides 1-4 that you roll at the beginning. Then, depending on ...
3
votes
1answer
79 views

What should the initial UCT value be with MCTS, when leaf's simulation count is zero? Infinity?

I am implenting a Monte Carlo Tree Search algorithm, where the selection process is done through Upper Confidence Bound formula: ...
1
vote
1answer
117 views

Unclear definition of a "leaf" and diverging UTC values in the Monte Carlo Tree Search

I have two questions regarding the Selection and Expansion steps in the Monte Carlo Tree Search Algorithm. In order to state the questions, I recall the algorithm that I believe is the one most ...
2
votes
0answers
56 views

Why do we use the tree-search version of breadth-first search or A*?

In Artificial Intelligence A Modern Approach, search algorithms are divided into tree-search version and graph-search version, where the graph-search version keeps an extra explored set to avoid ...
1
vote
0answers
51 views

What is a example showing that the tree-based variant for the greedy best-first search is incomplete?

I understand that a tree-based variant will have nodes repeatedly added to the frontier. How do I craft an example where a particular goal node is never found. Is this example valid. On the other ...
6
votes
1answer
774 views

MCTS: How to choose the final action from the root

When the time allotted to Monte Carlo tree search runs out, what action should be chosen from the root? The original UCT paper (2006) says bestAction in their ...
18
votes
1answer
24k views

What is the difference between tree search and graph search?

I have read various answers to this question at different places, but I am still missing something. What I have understood is that a graph search holds a closed list, with all expanded nodes, so ...