CSE571 Assignment 3 Solution

Exercise 1.1 (9pt)
Given the following minimax tree discussed in class, answer the following questions about alpha-beta pruning, and explain your answers by providing the alpha-beta values for a and b below. Except for the root node, the labels for the edges can be used as labels for the corresponding child nodes.

a. (3pt) Assuming we always explore from left to right, can the leaf nodes at j and k be pruned when the ordering of the leaf nodes can be arbitrarily changed (similar to what you see in the exercises in our offline lecture)? If so, provide an ordering of the leaf nodes. Otherwise, explain why.
b. (3pt) Given a), think about the optimal ordering of the leaf nodes (assuming the same structure) for alpha-beta pruning in this tree? What are the nodes that will be pruned?
c. (3pt) Observing a and b above, provide an intuitive answer to why alpha-beta pruning takes time O(2m/2) with optimal ordering, where m is the maximum depth of the game tree.
Exercise 1.2 (9pt)
On the minimax game tree below, answer the following questions about alpha-beta pruning assuming left to right traversal, and explain your answers.

a. (3pt) What are the values of A, B and C that ensure that X1 and its leaf nodes will not be pruned?
b. (3pt) For the node n1 to be pruned, what is the requirement on the variables A, B and C?
c. (3pt) For the node n2 to be pruned, what is the requirement on the variables A, B and C?
Exercise 1.3 (14pt)
In the following, a “max” tree consists only of max nodes, whereas an “expectimax” tree consists of a max node at the root with alternating layers of chance and max nodes. At chance nodes, all outcome probabilities are nonzero. The goal is to find the value of the root with a bounded-depth search. For each of (a)–(f), either give an example or explain why this is impossible.
a. (2pt) Assuming that leaf values are finite but unbounded, is pruning (as in alpha–beta) ever possible in a max tree?
b. (2pt) Is pruning ever possible in an expectimax tree under the same conditions?
c. (2pt) If leaf values are all nonnegative, is pruning ever possible in a max tree? Give an example, or explain why not.
d. (2pt) If leaf values are all nonnegative, is pruning ever possible in an expectimax tree? Give an example, or explain why not.
e. (2pt) If leaf values are all in the range [0, 1], is pruning ever possible in a max tree? Give an example, or explain why not.
f. (2pt) If leaf values are all in the range [0, 1], is pruning ever possible in an expectimax tree?
g. (2pt) Consider the outcomes of a chance node in an expectimax tree. Which of the following evaluation orders is most likely to yield pruning opportunities? Explain.
(i) Lowest probability first
(ii) Highest probability first
(iii) Doesn’t make any difference
Exercise 1.4 (10pt)
Consider that you are playing a strategy video game:
From wiki: “A strategy video game is a video game genre that focuses on skillful thinking and planning to achieve victory. It emphasizes strategic, tactical, and sometimes logistical challenges. Many games also offer economic challenges and exploration. They are generally categorized into four sub-types, depending on whether the game is turn-based or real-time, and whether the game focuses on strategy or tactics.”

There are a total of M players in this game, indexed by i. Pi represents the ith player, and Ui represents the utility returned for agent i under a terminal state, which is always positive.

1) (2pt) Express the relationship of these players as purely competitive using the utility values only, and not as a standard zero-sum or constant-sum game.
2) (4pt) Express the relationship of these players as both competitive and cooperative using Us only.
Explain your solution.

Exercise 1.5 (8pt)
Which of the following are true and which are false? Give brief explanations.
a. (3pt) In a fully observable, turn-taking, zero-sum game between two perfectly rational players, it does not help the first player to know what strategy the second player is using— that is, what move the second player will make, given the first player’s move.
b. (3pt) In a partially observable, turn-taking, zero-sum game between two perfectly rational players, it does not help the first player to know what move the second player will make, given the first player’s move.
c. (2pt) A perfectly rational Pacman never loses.