CptS 440/540 Artificial Intelligence
Homework 4
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.
a. 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.
b. 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?
