Description

HW3–Local Search – Adversarial Search
75pts

1) 5pts – Give the name of the algorithm that results when you do a local beam search with k = 1.

Answer:

2) 30pts – Consider the following partial search tree (we are in the middle of the search), where each edge is labeled with the cost of the corresponding operator and the leaves (fringe nodes) are labeled with the value of a heuristic function, h, estimating the remaining cost to the goal. Which node will be expanded next by each of the following search methods? Give a very small explanation or show your work.

1. Uniform-Cost Search: ………..
2. Greedy Best-First Search: …….
3. A* Search: ………..

3) 10pts A heuristic results in exploring N=180 nodes and finds the solution at depth d=2. What is its effective branching factor? Give an approximate answer, but you must show your work.

Hint:

4) 30pts – Game Playing

Using the following Minimax tree, answer the following questions:

a) 5pt – What score is guaranteed for MAX?

Answer:

b) 15pt – Indicate all the nodes that are pruned using alpha-beta pruning? You can use the node name or values to indicate.

Answer:

c) 5 – True or False: If Max uses alpha-beta pruning in Minimax, can s/he miss the chance of a better play (if s/he did’t prune)? Assume a perfect opponent.

Answer:

d) 5pt – What is the expectimax value for the following chance node (circle)? Assume equal probability for each of the chance outcome and the given expectimax values for the MIN node.

Chance

MIN 3 6 2

*) For those who have requested extra study questions, other good questions to work on (from the topics we covered) are: AIMA 3rd ed: 4.9 (topic not covered, but in the slides) 5.12, 5.15, 5.18, 5.19, 5.21,