1. The following problem asks about minimax search and alpha-beta pruning in game trees. The game tree below illustrates one position reached in the game. It is MAXs turn to move. The tree shows MAX considering three possible moves, A1, A2 and A3. In response to each MAXs move Ai, the tree shows three possible moves for MIN, labeled Ai1, Ai2, Ai3. Below that are leaf nodes showing the estimated score of each resulting position returned by the heuristics. For example, if MAX moves A3 and then MIN moves A33, then the heuristics estimate that the resulting position is worth 6. Note that each heuristics estimate is an integer. (a) (8 pts total, 2pts each) Propagate the scores from the leaves to the root using minimax search. At each branch node, write the score in the box. (b) (12 pts total 4 pts deducted for each node incorrectly marked) Draw an X on each leaf node that will be pruned by alpha-beta search from leftmost to rightmost branch. (c) (12 pts total 4 pts deducted for each node incorrectly marked) Draw an O on each leaf node that will be pruned by alpha-beta search from rightmost to leftmost branch. (d) (5 pts) What move will MAX make? (A1,A2 orA3) _____ (e) (5 pts) What move does MAX expect MIN to make in response? (A11,A12,) _____

MAX A2 MIN 3 4 Ai A33 X *