1. Consider the following initial and goal states for a 3x3 Wumpus World search problem. The initial state has the agent in (1,1) facing Right, and the goal state is that the agent in (1,2), colocated with the gold, regardless of orientation. The available actions are GOFORWARD, TURNLEFT and TURNRIGHT, and should be considered in this order. Note that all three actions are applicable in every state. Executing GOFORWARD when facing a wall results in the same state.
Draw the search tree generated by the A* search algorithm to solve this problem using the cityblock distance for the heuristic h. The city-block distance for a Wumpus World state is the city-block distance between the agent’s current location and the agent’s goal location. Next to every node, show the values of f, g and h. If two nodes have the same f value, then prefer nodes farther to the left in the search tree.
2. Consider the game tree below. Upward-pointing triangles are MAX nodes, downward-pointing triangles are MIN nodes, and squares are terminal nodes.
a. Perform Minimax-Decision search on the above tree. Put the final value next to each node in the tree. Finally, indicate which action MAX should take: a1, a2 or a3.
b. Perform Alpha-Beta-Search on the above tree (don’t reuse your tree from part (a)). Put an “X” over all nodes (internal and terminal, and all nodes in a subtree) that are pruned, i.e., not evaluated. Put the final value next to all non-pruned nodes. Finally, indicate which action MAX should take: a1, a2 or a3.
c. 540 students only. Consider the last five terminal leaf nodes in the above tree with utilities 8, 9, 4, 5, 6. If you could change these utilities to any value between 1 and 9, what values would you use in order to maximize the number of nodes pruned by the Alpha-Beta-Search. Show this tree and perform Alpha-Beta-Search on this tree in the same way as described in part (b).
1
