CS 188 Introduction to
Spring 2020 Artificial Intelligence Written HW 1 Sol.
Solutions for HW 1 (Written)
1
,Q1. [50 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
(turn lef t, turn right) and 8 moving actions (lef t, right, up, down, lef t up, lef t 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 lef t up, the agent will not move and nothing
will happen. Furthermore, if the agent is already facing lef t and a turn lef t action is taken, nothing happens.
Lastly, the agent cannot move into a cell currently occupied by the skull, or a wall.
0 1 2 3 4 5 6
0
1
2
3
4
5
6
(a) Answer the following questions for the Montezuma’s revenge board above:
(i) [4 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: (x, y, f acing direction, x skull, y skull)
Size of the state space: 2 × N × M
Explanation of each term in the size of the state space: There are N possible positions for the agent, 2
directions that the agent can face, and M possible positions for the skull.
2
, (ii) [4 pts] Please fill in the following pseudocode for the getSuccessor function for this game:
procedure getSuccessor(state)
successors ← empty list
turn left, turn right, left, left up, left down, right, right up, right down, up, down
for action ∈ do
right
if action ∈ {lef t, lef t up, lef t down} and state.f acing direction == then
continue
left
if action ∈ {right, right up, right down} and state.f acing direction == then
continue
right
if action ∈ {turn right} and state.f acing direction == then
continue
left
if action ∈ {turn lef t} and state.f acing direction == then
continue
next state ← state.apply action(action)
not in wall not collide with skull
if next state and next state then
successors.append(next state)
return successors
(iii) [2 pts] What is the goal test?
Is our current location (xH , yH ) = (3, 0)?
3
Spring 2020 Artificial Intelligence Written HW 1 Sol.
Solutions for HW 1 (Written)
1
,Q1. [50 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
(turn lef t, turn right) and 8 moving actions (lef t, right, up, down, lef t up, lef t 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 lef t up, the agent will not move and nothing
will happen. Furthermore, if the agent is already facing lef t and a turn lef t action is taken, nothing happens.
Lastly, the agent cannot move into a cell currently occupied by the skull, or a wall.
0 1 2 3 4 5 6
0
1
2
3
4
5
6
(a) Answer the following questions for the Montezuma’s revenge board above:
(i) [4 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: (x, y, f acing direction, x skull, y skull)
Size of the state space: 2 × N × M
Explanation of each term in the size of the state space: There are N possible positions for the agent, 2
directions that the agent can face, and M possible positions for the skull.
2
, (ii) [4 pts] Please fill in the following pseudocode for the getSuccessor function for this game:
procedure getSuccessor(state)
successors ← empty list
turn left, turn right, left, left up, left down, right, right up, right down, up, down
for action ∈ do
right
if action ∈ {lef t, lef t up, lef t down} and state.f acing direction == then
continue
left
if action ∈ {right, right up, right down} and state.f acing direction == then
continue
right
if action ∈ {turn right} and state.f acing direction == then
continue
left
if action ∈ {turn lef t} and state.f acing direction == then
continue
next state ← state.apply action(action)
not in wall not collide with skull
if next state and next state then
successors.append(next state)
return successors
(iii) [2 pts] What is the goal test?
Is our current location (xH , yH ) = (3, 0)?
3
