CSE 473 Midterm Exam – May 1, 2016
Name:
This exam is take home and is due on Sunday May 8 at 11:45 pm. You can submit it in
the online DropBox or to one of the TAs. This exam should not take significantly longer than
3 hours to complete if you have already carefully studied all of course material. Studying
while taking the exam may take longer. :)This exam is open book and open notes, but you must complete all of the work yourself
with no help from others. Please feel free to post clarification questions to the class message
board, but please do not discuss answer there.
Partial Credit: If you show your work and *briefly* describe your approach to thelonger questions, we will happily give partially credit, where possible. We reserve the rightto take off points for overly long answers. Please do not just write everything you can thinkof for each problem.
Name: Please do not forget to write you name in the space above!
There are 12 pages in this exam (including this one).

1

Q.1 (30)

Q.2 (30)

Q.3 (30)

ScoresQ.4 (20)

2Q.5 (30)

Q.6 (30)

Total (170)

Question 1 – True/False – 30 points
Circle the correct answer each True / False question.
1. True / False – A* Tree Search requires a consistent heuristic for optimality. (3 pt)
2. True / False – Minimax is optimal against perfect opponents. (3 pt)
3. True / False – Greedy search can take longer to terminate than uniform cost search.
(3 pt)
4. True / False – Uniform cost search with costs of 1 for all transitions is the same as
depth first search. (3 pt)
5. True / False – Alpha-Beta pruning can introduce errors during mini-max search. (3 pt)
6. True / False – Each state can only appear once in a search tree. (3 pt)
7. True / False – Policy Iteration always find the optimal policy, when run to convergence.
(3 pt)
8. True / False – Higher values for the discount (γ) will, in general, cause value iteration
to converge more slowly. (3pt)
9. True / False – Using the true cost from any state to the goal is a consistent heuristic.
(3pt)
10. True / False – Graph search can sometimes expand more nodes than tree search. (3pt)3Question 2 – Short Answer – 30 points
These short answer questions can be answered with a few sentences each.
1. Short Answer – Briefly describe the relationship between admissible and consistentheuristics. When would you use each, and why? (5 pts)

2. Short Answer – Briefly explain the difference between value iteration and policy iteration. Name one advantage or disadvantage of each. (5 pts)

3. Short Answer – Both alpha-beta pruning and depth-limited search can improve thespeed of minimax. Suppose you can only choose one or the other. Under what conditions would you prefer alpha-beta, and under what conditions would you prefer depthlimited search?

4. Short Answer – Briefly describe the difference between UCS and A* search. When
would you prefer to use each, and why? (5 pts)

4

5. Short Answer – Value iteration and expectimax can both be used to solve MDPs.
When would you prefer to use each, and why? (5 pts)

6. Short Answer – Can reflex agents act rationally? Please provide a brief example tojustify your answer. (5 pts)

5Question 3 – Tree Search – 30 points
Given the state graphbelow, run each of the following algorithms and list the order that theTree Searchnodes are expanded (a node is considered expanded when it is dequeued from the fringe).
state graph below, run each of the following algorithms and list the order that theThe values next to Given
eachtheedge
denote the cost of traveling between states.
nodes are explored (a node is considered explored when it is dequeued from the fringe). The
next to eachto
edgedenote thecost (i.e.
of travellingstates.
Use alphabeticalvalues
ordering
breakties
A between
shouldbe before B in the fringe, all ofthings being equal).AnyIt
isalsopossiblethatastatemay
expandedthan once. Everyand all ties should be broken by alphabetical ordering (i.e. A should be added moreto the fringe
before B). It is also
possiblea state may
occurandmore thanin the theorder explored.
Everyordering should always
startwiththethatstartnode
endoncewithgoal node.
ordering should always start with the start node and end with the goal node.

a) Depth­First Search: A, C, E, F, Gb) Iterative­Deepening
1. Breadth first search[5 pts] Search: A, A, C, B, A, C, E, B, Gc) Uniform­Cost Search: A, B, C, E, D, F, G

2. Depth first search [5 pts]

3. Iterative deepening [5 pts]

4. Uniform cost search [5 pts]

6

the following
Now, considerGiven
the following
twoheuristics:
heuristics:

State s

H1(s)

H2(s)

A (start)

1012B

811C

78D

44E

34F

23G (goal)00d) Give the ordering of nodes explored using A* search and heuristic H2 (remember ties should∗
be broken orderingby alphabetical
5. Provide the expansionfor Aordering)search with heuristic H2 (again breaking ties
A,
B,D,C,E,F,
G
alphabetically). [5 pts]e) Is hueristic h1 admissible?
Yes
NoIs heuristic h2 consistent?
Yes
No
6. List which, if any,of the twoheuristics are admissible[2.5 pts]
Is heuristic
h3 admissible?
Yes
No
Is heuristic h4 consistent?
YesNo

7. List which, if any, of the two heuristics are consistent [2.5 pts]

7

Question 4 Minimax– GameTrees – 20 points
and Alpha­Beta Pruning
In the followingIngame
tree,gametriangles
pointingup
maximizing
nodes pointing
and triangles pointing
the following
tree, triangles
pointing up
arearemaximizing
nodes and triangles
down
areminimizing
nodes.
Tree
traversal
isperformed
left
torightand
anypruning
isdonedown are minimizing nodes.
using alpha­beta pruning.

Answer the following questions with a possible integer value for each variable, or just write “notpossible”
if theneed
pruningto
will fillneverinhappenno matter
what. Whatpossible
integer(a,values
In this problem,you
numericvalues
forarethelettersb, forc, d, e, and f ) toa, b, c, d, e, and f such that:cause different subtrees to be pruned during alpha-beta search, or to say if no such values
are possible (by1. writing“nottoE7theThe tree
can bepossible”
pruned at edge
only?right of the blanks).

1. E7 is pruned (andno others) [5 pts]
a: ________ b: ________ c: ________ d: ________ e: ________ f: ________
a:

b:

c:

d:

Answer ­ not possiblee:f:

2. andTheE9tree canpruned at edge
E3 noonly?others) [5 pts]
2. E5, E6, E8,arebepruned(anda:

b:

c:

d:

e:

a: ________ b: ________

f:

c: ________ d: ________ e: ________ f: ________­ not possible
3. E6 and E9 areAnswer
pruned(and no others) [5 pts]

a:

b: 3.

The tree can be pruned at edges E5 and E6 only?

c:

d:

e:

f:

4. E3 is pruned (along with everything below it, as always) [5 pts]
a:

b:

c:

d:

e:

f:

8

MDP / Value Iteration
You are given the gridworld MDP shown below where each state is labelled by a letter, and all
terminal states are denoted by a positive or negative reward value in parentheses (NOTE: The
reward is given after taking the only action EXIT from that terminal state). There are no living
rewards or penalties. Assume that each legal action moves the actor to the adjacent square inthat given direction (North, East, South, West) with 100% success except for state B which hasthe transition function:Question 5 – Value Iteration – 30 points

Consider the following gridworld
MDP shown below where each state is labelled by a letter,T(B, North, A) = 1.00
T(B,South,C) =by
0.75 a positive or negative reward value in parentheses
and all terminal states are denoted
T(B, South, A) = 0.25
(NOTE: The reward is givenT(B,afterthe only action EXIT from that terminal state).
East, D)taking= 1.00

There are no living rewards andthateachaction
moves
theto the adjacenta) assume
Given a discountfactor
γ = 0.5legal, fill in thevalues below
for eachstateactor
after n iterations
square in that given direction (North, East, South, West) with 100% success except for statenABCDEFB which has the transition function:
01000

T(B, North, A) = 1.00
T(B,­4South, C)= 0.758
0
T(B, South, A) = 0.25
T(B, East, D) = 1.00
T(B, West, B) = 1.00

00000

2

1. Given a discount factor γ = 0.5, fill in the values V n (s) below that the value integration
algorithm would compute:[15pt]nABCDEF

V0
V1
V2
V3
Note: you do not need to show every step of your work and are welcome to write aprogram to do this or compute it by hand. The transition distribution is designed tominimize the overall computation involved. However, writing out the math for a few
steps at the top of the next page will help us assign partial credit if your final numbers
are not correct.
9

(extra space for part one)

2. Write the policy that would be executed given the values V3 computed above [10pt].

3. The policy that you computed above should assign π(E) = East, that is it should
prefer going east from state E. If this is not the case, please double check your work.
What range of discount factors γ (if any) would change optimal action of state E togo West? Briefly explain your reasoning/show your work. As always, please assumeγ ∈ [0, 1] [5pt].

10Question 6 – Stutter Step MDP and Bellman Equations – 30 points
Consider the following special case of the general MDP formulation we studied in class.
Instead of specifying an arbitrary transition distribution T (s, a, s0 ), the stutter step MDP
has a function T (s, a) that returns a next state s0 deterministically. However, when the agent
actually acts in the world, it often stutters. It only actually reaches s0 half of the time, andit otherwise stays in s. The reward R(s, a, s0 ) remains as in the general case.
1. Write down a set of Bellman equations for the stutter step MDP in terms of T (s, a),by defining V ∗ (s), Q∗ (s, a) and π ∗ (s). Be sure to include the discount γ. [20 pts]

112. Consider the special case of the stutter step MDP where R(s, a, s0 ) is zero for all states
except for a single good terminal state, which has reward 1, and a single bad terminal
state, with reward -100. Furthermore, assume all states s are connected to both terminal states (there exists some sequence of actions that will go from s to the terminal
state with non-zero probability).
If γ = 1, briefly describe what the optimal values V ∗ (s) for all states would look like.
[5 pts]3. Again, set the rewards as in the previous question, but now consider γ = 0.1 anddescribe V ∗ (s). Would the optimal policy π ∗ (s) change? [5 pts]

12