This question's topic is artificial intelligence.

Problem 1. Non-zero sum game [15 points] This question considers the application of Minimax and Alpha-Beta Pruning to non zero-sum games. Consider two players A and B, where each player has their own independent utility values for each state. The two players will try to maximize their respective utility values. In Fig. 1 the first and second layer corresponds to the players A and B respectively. The utilities in the leaf nodes have the form (UA, UB). You should: (a) [10 points] Compute the values for every non-leaf node in the tree shown in Fig. 1. Player A Player B (3,2) (7,5) (12,1) (4,6) (5,4) (1,2) Figure 1: Non-zero sum game tree (b) [5 points] Suppose that both players have positive utility at each leaf node, but the sum of their utilities is bounded by k. That is: UA> O UB > 0 UA+UB k You can perform alpha-beta pruning on this type of game. Give a general mathematical condition under which a child of player B's node can be pruned. Your answer should be stated in terms of quantities such as UA, UB, k or a and B.