CSE 571  Homework 3

CSE 571 
Homework 3

Only typed answers will be accepted.
Be precise and concise in your answers. You may add hand-drawn figures when necessary.
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.
3) (4pt) How would you describe a game where you are in a team (P1 to Pi) playing against another (Pi+1
to PM), which further satisfies the following: 1) only one team wins and the other team loses; 2) winning
team may have members in its team defeated but at least one member undefeated; 3) losing team must
have all its members defeated. 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.