Physiology > STUDY GUIDE > University of California, Berkeley - CS 70CS_188_Spring_2020_Written_Homework_1-17 (All)

University of California, Berkeley - CS 70CS_188_Spring_2020_Written_Homework_1-17

Document Content and Description Below

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 left; turn 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 turn left 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; facing 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 for action 2 turn left, turn right, left, left up, left down, right, right up, right down, up, down do if action 2 fleft; left up; left downg and state:facing direction == right then continue if action 2 fright; right up; right downg and state:facing direction == left then continue if action 2 fturn rightg and state:facing direction == right then continue if action 2 fturn leftg and state:facing direction == left then continue next state state:apply action(action) if next state not in wall and next state not collide with skull then successors.append(next state) return successors [Show More]

Last updated: 2 years ago

Preview 1 out of 16 pages

Buy Now

Instant download

We Accept: