CptS440-540 Homework 4 Solved

General Instructions: Put your answers to the following problems into a PDF document and upload the document as your submission for Homework 4 for the course CptS 440 Pullman (all sections of CptS 440 and 540 are merged under the CptS 440 Pullman section) on the Canvas system by the above deadline. Note that you may submit multiple times, but we will only grade the most recent entry submitted before the deadline.

1. Consider the game tree below. Upward-pointing triangles are MAX nodes, downward-pointing triangles are MIN nodes, and squares are terminal nodes.
   1. Show the result of performing Minimax-Decision search on the game tree. Put the final

      value next to each node in the tree. Finally, indicate which action MAX should take: a1, a2

      or a3.

   2. Show the result after performing Alpha-Beta-Search on the game 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.

2. CptS 540 Students Only: For the level 2 terminal node (with value 2) in the a3 subtree of the game tree in Problem 1, how would you change this value in order to ensure a3 is the optimal choice for MAX?

1