CS 188 Artificial Intelligence Written HW
Artificial Intelligence Written HW
CS 188 Artificial Intelligence Written HW 1
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
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)