CS 188
Spring 2021
Introduction to
Artificial Intelligence Written HW 1
Due: Wednesday 2/10/2021 at 10:59pm (submit via Gradescope).
Policy: Can be solved in groups (acknowledge collaborators) but must be written up individually
Submission: Your submission should be a PDF that matches this template. Each page of the PDF should
align with the corresponding page of the template (page 1 has name/collaborators, question 1 begins on page
2, etc.). Do not reorder, split, combine, or add extra pages. The intention is that you print out the
template, write on the page in pen/pencil, and then scan or take pictures of the pages to make your submission.
You may also fill out this template digitally (e.g. using a tablet.)
First name
Last name
SID
Collaborators
For staff use only:
Q1. Probability Review /30
Q2. Uninformed Search and Heuristics /70
Total /100
1
Q1. [30 pts] Probability Review
This question is meant to review part of the probability prerequisite. It might be helpful to look into resources under
General Resources at https://piazza.com/berkeley/spring2021/cs188/resources.
Let A, B, C, D be four random variables.
(a) What is the smallest set of independence or conditional independence relationships we need to assume for the
following scenarios?
(i) [1 pt] P (A,B) = P (A|B)P (B)
(ii) [1 pt] P (A,B) = P (A)P (B)
(iii) [2 pts] P (A,B,C) = P (A|B)P (B|C)P (C)
(iv) [3 pts] P (A,B,C) = P (A)P (B|C)P (C)
(v) [3 pts] P (A,B,C) = P (A)P (B)P (C)
(b) Simplify the following expressions to one probability expression. Please show your work.
(i) [3 pts] P (A,B)∑
a P (a,B)
(ii) [3 pts] P (A,B,C,D)∑
a
∑
b P (a,b,C,D)
(iii) [4 pts] P (A,C,D|B)P (C,D|B)
(iv) [4 pts] P (A|B)∑
c P (c|B)
(v) [6 pts]∑
b P (A,b|C)P (D|A,b,C)
P (A|B,C) , given A ⊥⊥ B|C
2
Q2. [70 pts] Uninformed Search and Heuristics
Consider the following simplified version of the classic Atari video game, Montezuma’s Revenge: It is played on the
board illustrated below. An agent (represented by the person icon in cell (1,3)) wishes to grab the key (in cell (3,0)).
A skull starts in cell (5,2) and moves to the right by one cell after each action is executed until it ends up in the
rightmost cell, at which point it starts moving to the left, and repeats this pattern back and forth.
The agent can be facing either left or right. There are 10 possible actions for the agent: 2 turning actions
(face left, face right) and 8 moving actions (left, right, up, down, left up, left down, right up, right down). The
agent can move up or down while facing either direction, but can move sideways or diagonally only if facing in that
direction. For example, if the agent is facing right but tries to move left up, the agent will not move and nothing
will happen. Furthermore, if the agent is already facing left and a face left action is taken, nothing happens.
Lastly, the agent cannot move into a cell currently occupied by the skull, or a wall.
(a) Answer the following questions for the Montezuma’s revenge board above:
(i) [7 pts] Let N be the number of possible cell locations that the agent can be in, and let M be the number
of possible cell locations that the skull can be in. Recall that for “pacman pathing”, the representation of
the state was (x, y) where x was the row and y was the column of pacman’s position.
Describe a representation of a state in the state space for this game and give an expression for the size of
the state space.
Representation of the state space:
Size of the state space:
Explanation of each term in the size of the state space:
3
(ii) [3 pts] What is the goal test?
4
(b) Now, consider the simplified board below, which has no skull and no facing-direction for the agent (i.e.,
the agent can move in any of the 8 directions as long as it remains in the board). For the three following graph
search algorithms, perform the search procedure yourself (please show your work) and provide answers to
the questions below regarding the nodes expanded during the search as well as the final path found by the
algorithm.
On this board, assume that a diagonal move has a cost of 3, whereas moving left, right, up, or down has a
cost of 1. Do notice the difference in costs, and recall which algorithms use this cost information and which
algorithms do not.
Remember that the search procedure should begin at the agent’s starting position (C). To break ties when
adding nodes of equal cost to the frontier, follow alphabetical order.
Finally, when listing the order/number of nodes expanded, do not include nodes which are taken off the frontier
but discarded immediately due to already having been expanded.
E
C
BA
D
F
G H
5
(i) [8 pts] Breadth-first graph search
Frontier data structure: FIFO.
Recall that BFS selects the shallowest unexpanded node in the frontier for expansion, which will be the
oldest node in the frontier.
E
C
BA
D
F
G H
Order of nodes expanded:
Number of nodes expanded:
Path returned:
Length of path:
Cost of path:
What are the depths d(A), d(B), . . . d(H)?
State s A B C D E F G H
d(s)
6
(ii) [8 pts] Uniform-cost graph search
Frontier data structure: priority queue (make sure you update/reorder the whole frontier after each addi-
tion)
Recall that UCS keeps track of the lowest cost, g(v), to get from the start node to the node v.
E
C
BA
D
F
G H
Order of nodes expanded:
Number of nodes expanded:
Path returned:
Length of path:
Cost of path:
What are g(A), g(B), . . . , g(H)?
State s A B C D E F G H
g(s)
7
(iii) [8 pts] A* graph search (with Manhattan distance to the goal as the heuristic)
Frontier data structure: priority queue (make sure you update/reorder the whole frontier after each addi-
tion)
Recall that A* computes f(v) for the nodes v that it expands, with f(v) = g(v) + h(v) where g(v) is the
lowest cost to reach v from the start node and h(v) is an estimate of the distance from v to the goal.
E
C
BA
D
F
G H
Order of nodes expanded during the search:
Number of nodes expanded during the search:
Path returned by the search:
Length of path returned by the search:
Cost of path returned by the search:
What are f(A), f(B), . . . , f(H)? Note that the h(v) is found by calculating the Manhattan distance from
v to goal.
State s A B C D E F G H
f(s)
8
(c) [10 pts] Given your answers above, what are the qualitative differences between the results achieved by BFS,
UCS, and A*? Which one finds the shortest path (in number of steps)? Which one finds the optimal path (in
cost)?
9
EC
BA
D
F
G H
(d) For the same board and setting as part (b), give an example for each of the following types of heuristics. Please
briefly explain why the example you chose satisfies the requested properties.
(i) [3 pts] Admissible and consistent.
Note: You can use a heuristic that we have frequently used in this class, or you can just assign any set of
numbers to the states that qualifies as an admissible and consistent heuristic.
State s A B C D E F G H
Heuristic h(s)
Explanation:
(ii) [4 pts] Admissible but inconsistent
State s A B C D E F G H
Heuristic h(s)
Explanation:
(iii) [3 pts] Inadmissible and inconsistent
State s A B C D E F G H
Heuristic h(s)
Explanation:
10
(e) (i) [8 pts] For this new version of the game, your friend Nancy suggests taking the old game setting from part
(b) and now adding the ability for the agent to perform a maximum of one “teleportation” action during
the game. That is, on one of the agent’s moves, it can choose to jump from its current state to any other
non-goal state on the board, and the cost of teleporting is 1.
1. How does this new teleportation ability change the state space of the game from part (b), which was
(x, y)? Does anything need to be added or removed?
2. Nancy argues that in this new game, at least one previously consistent heuristic can become inconsistent.
Is Nancy right?# Yes, and I will give an example below.# No, and I will provide a proof below.
Note: we define heuristics for this problem as being a function of only the cell location: They cannot
incorporate anything that did not exist in the old version of the game that we are comparing to.
If you believe Nancy is right, give an example of a heuristic that used to be consistent in the old game
but is no longer consistent in this new game. Make sure to explain why it is no longer consistent (perhaps
with a drawing of a board state and an explanation).
State A B C D E F G H
h(s)
If you believe Nancy is wrong, provide an argument for why a heuristic that was consistent in the old game
must also remain consistent in this new game. Be specific about your reasoning and use mathematical
quantities such as heuristic costs of states h(v) and true costs of actions c(v, a, v′).
11
(ii) [8 pts] For this new version of the board, your friend Ethan suggests adding the skull back to the old
board setting from part (b), and having the skull move back and forth between the cells E and F.
1. How does the presence of this skull change the state space of the game from part (b), which was (x, y)?
Does anything need to be added or removed?
2. Ethan argues that in this new board, at least one previously consistent heuristic can become inconsis-
tent. Is Ethan right?
# Yes, and I will give an example below.# No, and I will provide a proof below.
Note: we define heuristics for this problem as being a function of only the cell location: They cannot
incorporate the location of the skull, since that did not exist in the old version of the board that we are
comparing to.
If you believe Ethan is right, give an example of a heuristic that used to be consistent on the old board but
is no longer consistent on this new board. Make sure to explain why it is no longer consistent (perhaps
with a drawing of a board state and an explanation.
State A B C D E F G H
h(s)
If you believe Ethan is wrong, provide an argument for why a heuristic that was consistent in the old board
must also remain consistent in this new board. Be specific about your reasoning and use mathematical
quantities such as heuristic costs of states h(v) and true costs of actions c(v, a, v′).
12


















































































































































































































学霸联盟