# 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
Filter by
Sorted by
Tagged with
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
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
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
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
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
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
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
569 views

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

In Artiﬁcial 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
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 ...
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