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
57
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
416
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 ...
- 101
2
votes
1
answer
133
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
344
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
379
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 ...
- 21
5
votes
1
answer
819
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
525
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
569
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
415
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 ...
- 53
8
votes
1
answer
2k
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 ...
- 347
19
votes
1
answer
44k
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 ...
- 423