Exam (elaborations)
CS 188 Spring 2020 Written Homework 1 17 CS 188 Spring 2020
- Course
- Institution
CS 188 Spring 2020 Written Homework 1 17 CS 188 Spring 2020
[Show more]
Seller
Follow
solutions
Reviews received
Content preview
CS 188 Introduction toSpring 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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller solutions. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $7.49. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
82977 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now