# PS1

## Contents

- 1
**Problem Set 1**(65 points)- 1.1 Task 1. Course Policy [6 points]
- 1.2 Task 2. Environments and Agents [15 points]
- 1.3 Task 3. Uninformed Search [12 points]
- 1.4 Task 4. Informed Search [12 points]
- 1.5 Task 5. Borealis (Programming Challenge) [20 points]
- 1.6 Task 6. Certification and Peer Evaluation [required for credit, 0 points]

**Problem Set 1** (65 points)[edit]

EECS492 problem sets are a collaborative activity amongst your staff-assigned team. You may also discuss the problem sets and problem solving approach with other teams, but the work you submit must be wholly that of your team. In particular, you may not derive your solutions from previous years' solutions, nor may you derive your solutions from code snippets found elsewhere (including online). Examples: studying pseudo-code as found on Wikipedia is acceptable; adapting code from an open source project is not.

Your submission will include a written portion (which must be typeset, including any equations, figures, or graphs, and must be in PDF format), and a programming portion. Your writeup should include a terse restatement of each question (copy/paste is fine) in a font face that clearly separates the question from your answer, and should be formatted in an easy-to-navigate fashion (i.e., with large headings for task, and smaller headings for each problem). Make sure that the uniqnames of each member are listed at the top of every page as a running header. Deviations from this format will be penalized.

For the programming portions, you must include all of your code in a ready-to-compile state, along with a README that gives invocation instructions. Your PDF and programming files must then be zipped and submitted by email. Your email must have the following form, where the challenge score is computed based on the scoring rules described in the problem set.

TO: eecs492-staff@april.eecs.umich.edu SUBJECT: PS1: <uniqname1>, <uniqname2>, <uniqname3>. challenge=<challenge score> CC: <all of your team members>

You may receive a "moderation pending" message; this is harmless.

### Task 1. Course Policy [6 points][edit]

**1.1.** As you know, this problem set is a team activity, and your team must meet to discuss your approach and solutions. Which collaborations are permitted by the course policy? [1 point each]

- A) Discussing algorithms and approaches with another team.

- B) Submitting a programming solution that extends and enhances the code from one of last year's teams.

- C) Meeting as a group to divide up the problems amongst your team members, then merging the results by email on the due date.

- D) Reading wikipedia or other online resources (e.g., academic papers) for additional ideas that could be applied to your programming assignment.

**1.2.** Suppose you turned in this problem set on Saturday January 22nd at 1:30a. What lateness penalty would you incur? [2 points]

### Task 2. Environments and Agents [15 points][edit]

**2.1.** For each of the following agents, describe the environment attributes that apply. In some cases, the correct classification is not necessarily clear-cut; explain your reasoning. For reference, the environment attributes are:

- Fully/Partially Observable
- Deterministic/Stochastic/Strategic
- Episodic/Sequential
- Static/Dynamic
- Discrete/Continuous
- Single-Agent/Multi-agent

Also, agents can be described in terms of their world representation (stateless, fixed model, learning model) and in terms of their planning strategy (reflexive, or utility-maximizing predictive). Describe a reasonable implementation of each agent, and categorize its world representation and planning strategy. Explain your answer; for example, for a utility-maximizing agent, what is the utility function?

A rough template is provided for the first option. Remember to support all but the most obvious answers with a sentence or two! [1 point per response]

a) Supermarket bar code scanner

- Environment properties:

- Agent world representation:

- Agent planning strategy:

b) Search engine web crawler

c) Online poker playing bot

d) Amazon product recommendation engine

e) A bit-torrent client

f) (Optional) The *interrogator* of a Turing test.

### Task 3. Uninformed Search [12 points][edit]

Consider a state space where the start state is number 1 and each state k has two successors: numbers 2k and 2k + 1.

3.1. Draw the portion of the state space for states 1 to 15. [4 points]

3.2. Suppose the goal state is 9. List the order in which nodes will be visited for the searches below. [2 points each]

- a) breadth first search (BFS)

- b) depth first search (DFS)

- c) depth limited search (DLS) with limit 2

- d) iterative deepening search (IDS).

### Task 4. Informed Search [12 points][edit]

4.1. A* Practice

Consider the search tree below. The cost-to-go heuristic h() is given at each node (e.g., at node & state A, the cost-to-go heuristic is 3.) Assume that action costs are uniformly 1 and that state only state I is a goal node.:

A3 / \ / \ B2 C0 / \ / \ D1 E1 F2 G2 /\ /\ /\ /\ H2 I0 J1 K1 L1 M4 N2 P2

- a) Is the heuristic admissible? If not, identify the node(s) with the offending heuristic value(s). [2 points]

- b) What is the value of f() at node F? [2 points]

- c) Consider an A* search on this tree from state A to I. For each iteration of A*, write out the state of the fringe. When writing out the list of nodes in the fringe at a particular step, you should list all of the paths and their f() value. [2 points]

(Please write your answer in the format below, where you identify the step number, the paths on the fringe, and the f() value for each path on the fringe. Note that the particular paths and values below are made up.)

step 1: [A(3)] ... step 11: [ACMN(10), ABR(23), ABVZ(27)] ...

4.2. Heuristic Functions

- a) Is the heuristic function h()=0 admissible? [2 points]

- b) What, in general, is the consequence of a heuristic function that underestimates the true value? (Consider the effect on completeness, runtime, memory usage.) [2 points]

- c) What would happen if the heuristic function computed the exact cost to goal? [2 points]

### Task 5. Borealis (Programming Challenge) [20 points][edit]

In the rest of this assignment, we explore the design of agents to play a simple game called Borealis, patterned after a popular iPhone diversion called Aurora Feint. Borealis is laid out on a rectangular grid, with each cell of the grid possibly containing a colored tile. The game starts with a particular configuration of tiles, and the object of the game is to clear the grid. The rules are fairly simple. Whenever three or more tiles are arrayed in a horizontal or vertical line, they disappear. The Borealis world has gravity, so when a cell becomes vacant, any tiles above it will fall down until all are resting on the bottom or another tile.

Agents can perform two basic action types. First, they can swap the contents of two horizontally adjacent cells. Second, they can rotate the board by 90, 180, or 270 degrees. Note that when the board is rotated, gravity makes the tiles in each column fall down to the bottom, maintaining their order. Once gravity has run its course, horizontal or vertical runs of three or more same-colored tiles may disappear, which may then trigger further moves by gravity, and possibly further disappearances, etc.

The goal of Borealis is to cause all the tiles to disappear in the minimum number of moves. Getting "stuck"--- i.e., tiles remain that cannot be removed-- is considered a loss.

You can try out the Borealis game for yourself, by downloading the attached archive and following the instructions in README.txt. We won't be using the rule-based agents this term, so you can skip that part of the README. For the impatient, you can do this:

tar -xzvf eecs492_ps1.tgz cd eecs492_ps1 ant java -jar borealis.jar human puzzle21.txt

You should begin by playing the game yourself so that you can get a first-hand feel for the rules. We've included a number of simple puzzles (those with just a single digit) for you to try.

**5.1.** Implement a simple breadth-first search for Borealis that can solve puzzle21, puzzle22, and puzzle23. Note that we've provided a template to get you started. We've also provided a working DepthLimitedAgent that can be adapted to a BreadthFirstAgent by changing fewer than 10 lines of code. [5 points]

Submit your code and the solutions (i.e., a list of moves). Are the solutions optimal?

**5.2.** Your solution will fail on puzzle24. Explain what happened and why. [2 points]

**5.3.** Suppose we asked you to implement a graph-style search, instead of a tree-style search. This would require you to be able to detect when you've reached a state that you've previously reached. Describe how you could perform this test as efficiently as possible (consider both memory and computational costs). [2 points]

**5.4.** Implement an IncrementalDeepeningSearch that can solve puzzle24. (Again, you will find the provided code very helpful.) Submit your code and the solutions. Is the solution optimal? [5 points]

**5.5. CHALLENGE [6 points]**

Consider problem puzzle2011; it is significantly harder than the ones you've worked before, and finding an optimal solution is likely impractical. On this problem, your goal will be to find a sub-optimal solution (or as close as you can get). You will find it helpful to read ahead in the book for ideas, and the staff will be happy to serve as a sounding board! (Note that this problem is a graded part of the problem set; challenges are not "optional").

The team with the best solution will get an award (of a delicious nature) along with 10 bonus points. You'll also get a chance to briefly explain your approach to the class!

Your score on the leaderboard will be computed as (2N+1)*T, where N is the number of tiles remaining at the end of the game and T is the number of turns. Lowest score wins. As you can see, if you solve the puzzle, your score will be the number of turns; if your solution does not solve the puzzle, your leaderboard score will go up dramatically. (Note that your leaderboard score does not directly factor into your problem set score, though particularly poor methods will generally get fewer points on the problem set.)

You can write your solution however you like. The only requirement is that your solution output a list of moves compatible with the move lists produced by the staff-provided code (one move per line). You are free to use whatever language, whatever computing resources you have available. Submit your solutions to the leaderboard, by visiting the apps page.

Turn in your code, and your best solution, along with a short writeup (a paragraph) describing your idea. Please also include the computational time required to find your solution.

### Task 6. Certification and Peer Evaluation [required for credit, 0 points][edit]

Print or write the following on a sheet of paper:

**"I participated and contributed to team discussions on each problem, and I attest to the integrity of each solution. Our team met as a group on [DATE(S)]." **

Each team member should sign the paper (physically, not digitally), and a photo of the paper should be included with your problem set. By doing so, you are asserting that you were materially involved in each answer, and that you certify that every solution complies with the collaboration policy of this course. In the event of a violation of the course's guidelines, your certification will be forwarded to the honor council.

If the statement requires qualification (i.e., it's not quite true), please describe the issue and the steps you took to mitigate it. If a team member did not materially contribute to a particular solution, then their score on that problem will generally be reduced. The staff will use their discretion based on the specific circumstances you identify, and we are happy to discuss potential problems prior to the problem set due date.

If your team works together, as required, this will be painless! :)

Each member of your team must also complete a peer evaluation, accessible from the apps page.

Your evaluations of your teammates will remain private. If problems develop with your team, it is up to your team to resolve them: we will not intercede except in the most extreme situations.