Answer Happy

(a) Consider the following minimax game tree. There are two players Max and Min; the player Max wants to maximise the utility and the player Min wants to minimise the utility. The tree has five layers and we can use Lm-n to denote the nth node from left to right in the layer m; for example, the root node can be denoted by L1-1, the first node at the bottom layer (with value 8) can be denoted by L5-1, and the fourth node at the fourth layer (with value 11) can be denoted by L4-4. Give the value of the root node (L1-1) and the values of the two nodes at the second layer (L2-1 and L2-2). Justify you answer. [2 marks]

Max Min Max Min 8 15 13 17 7 20 4 30 (b) We use the alpha-beta pruning algorithm to prune the tree. List all the pruned nodes. Assume that child nodes are visited from left to right. Justify you answer. [10 marks] (c) Now suppose that the Max player in the third layer is replaced by a Chance player. We then have the following game tree. Let us say that the chance nodes go their different children with the same probability. Give the value of the root node (L1-1) and the values of the two nodes at the second layer (L2-1 and L2-2). Justify you [2 marks] answer. 12 11 16 9 14

Max Min Chance 14 Min 8 15 13 17 7 20 30 (d) Can this tree get pruned (assume that child nodes are visited from left to right)? If yes, list all the pruned nodes; If no, give your explanation. [6 marks] 12 11 16 9