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.
11 questions
2 votes
0 answers
342 views
Why solely a one-step-lookahead in value/policy-iteration?
In value iteration and policy iteration we solely consider a one-step-lookahead where the lookahead is from the previous iteraiton and therefore need to sweep over all states and iterate this ...
- 53
1 vote
0 answers
761 views
Does iterative deepening depth-first search expand at most twice as many nodes as breadth-first search?
My understanding is that iterative deepening search is roughly equivalent to breadth-first search, except instead of keeping all visited nodes in memory, we regenerate nodes as needed, trading off ...
- 111
2 votes
1 answer
286 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 ...
- 197
2 votes
1 answer
446 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 ...
- 21
1 vote
1 answer
578 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 ...
- 13
5 votes
1 answer
1k 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: ...
- 153
2 votes
1 answer
785 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 ...
- 123
2 votes
0 answers
900 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 ...
- 21
1 vote
0 answers
580 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 ...
- 63
9 votes
1 answer
3k 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 ...
- 375
20 votes
1 answer
55k 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 ...
- 433