Exercise 4        Name __________________        Score __/14

1. Give the Minimax values for the game tree at right.
2. Give the a-b values for the game tree at right. Show any pruning.
3. Is there any difference in left-to-right or right-to-left pruning?
4. Prove the following assertion: for every game tree, the utility obtained by MAX using minimax decisions against a suboptimal MIN will never be lower than the utility obtained playing against an optimal MIN.
   
   Consider a MIN node whose children are terminal nodes, If MIN plays suboptimally, then the value of the node is greater than or equal to the value it would have been if MIN played optimally. Hence, the value of the MAX nod that is MIN's parent can only be increased. By simple induction, this argument can be extended all the way to the root.
    
5. Can you come up with a game tree in which MAX can do better using a suboptimal strategy against a suboptimal MIN?
   
   If MIN always falls for a certain kind of trap and loses, then setting the trap guarantees a win even if there is a devastating response for MIN. In the figure, the minimax move is a2 for MAX. To set the trap MAX moves a1, depending upon MIN to play suboptimally and move b1 or b2.
    
6. What are the SUCCESSOR states of the following, assuming X moved first?
   X=3, 6, 8

   0	1	2
   3	4	5
   6	7	8

7. Give the Minimax values for the game tree with 3 players at right.