Description

CptS 440/540 Artificial Intelligence
Homework 4

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?
1