Description
1. Consider the following initial and goal states for a 3×3 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).