CMSC 471

Artificial Intelligence -- Fall 2009

HOMEWORK TWO
out 9/15/09 due 10/1/09 (CHANGED!)

http://www.cs.umbc.edu/471/fall09/hw/hw2.html



In this assignment, we'll explore the search space of the game Rush Hour. I've provided some Lisp infrastructure (data structures plus basic variables and functions). I've also given you some very structured guidance on how to design and implement a solution. You do not have to follow my guidance, as long as you provide working code with the specified functionality.

You may modify the code I've provided, but please maintain the provided code and your new code in separate files, and document any changes that you make to the provided code.

1. Implementation (80 points)

Implement a generic uninformed search function, along the lines of Russell & Norvig, Figure 3.9 (page 72). Write wrapper functions that invoke this generic search function to perform breadth-first and depth-first search in the Rush Hour search space. Test your code thoroughly, and make sure it's sufficiently well documented for the TA and me to read it and understand what it's doing.

2. Results and Discussion (10 points + up to 10 bonus points)

Run your code on the test cases test1, test2, and test3, and submit a short (one-page) summary of your findings. How did the run time (measured in number of nodes created and expanded) and length of solution compare for breadth-first search and depth-first search? Bonus: Extra credit if you include results for test4 (the first puzzle from the actual game).

3. Analysis of Search Space (10 points)

How many legal states are there in the state space for each of the four test cases given above? Give exact values for test1 and test2. For test3 and test4, you may give an estimate, along with a discussion of whether your estimate is an upper or lower bound, and how one might compute an exact number of legal states.

Background and Design Guidance

Rush Hour

Rush Hour is a game that consists of a 6x6 grid and a set of 1x2 and 1x3 vehicles positioned on the grid. The goal is to move a designated vehicle out of traffic and off the board. The goal vehicle always starts somewhere in the 3rd row (i.e. y=2 in a 0-based array), and must move off the board to the right.

A vehicle can only move along its axis of orientation (i.e., the goal vehicle and other horizontally aligned vehicles can only move left or right, and vertically aligned vehicles can only move up or down). In order to move a vehicle, the position it is moving into must be empty.

Take a look at the test file test2. In this puzzle, there is one other vehicle in addition to the goal vehicle g. (Spaces marked NIL are empty.) In order to solve the puzzle, v1 needs to be moved down one step, and then g needs to be moved to the right one step. When g reaches the end of the row, the goal has been achieved.

You can play Rush Hour by visiting http://www.puzzles.com/products/RushHour/RHfromMarkRiedel/Jam.html or http://www.thekidzpage.com/freekidsgames/games/rush/index.htm. (I haven't been able to get the first of these links to work on my Mac, but the second one works fine for me.) The standard game comes with 40 puzzles in increasing order of difficulty. The hardest test case I'm requiring you to solve is significantly easier than even the first "real" game -- you'll see why!

Infrastructure

You should download the file rush-hour-basics.lisp. Read the documentation in the file thoroughly to be sure that you understand the code. The file includes a definition for the game CLOS class; a function to load a game specification from a file and create a new game instance; and a number of utility, debugging/logging, and I/O functions.

A couple of notes on the Lisp code in this file: