CMSC 471

Artificial Intelligence -- Fall 2011

out 9/15/11, due 10/4/11

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 the algorithm in Slide 28 from the September 8 slides. 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.

Your code must be submitted in two ways: first, as a hardcopy with your results and analysis (#2 and #3, below); second, using the submit command on the gl machines. You may submit multiple files, but you must have at least one file called hw2.lisp that is the driver file (i.e., that contains all of your code or loads the other files that contains the code). You should submit rush-hour-basics.lisp if you are using the code I've provided, whether or not you modify that file, so that everything will load in your directory. (If you haven't modified >rush-hour-basics.lisp, you don't need to submit a printed copy.)

Although you do not need to follow my design, your code must three top-level functions: load-game, which takes a file name and returns a game object; a depth-first-search function called dfs that takes a game object (and an optional depth limit if you implement depth limits); and a breadth-first-search function called bfs that takes a game object (and possibly an optional depth limit). NOTE: You can simply include the load-game function that I have provided; this note just means that if you reimplement it for any reason, you should use the same function name (load-game), argument (file name), and return value (game object).

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

Run your code on the test cases test1, test2, and test3. Submit a log of these test cases (i.e., a screen capture of the interpreter as you run each of the test cases that shows your program's output). You must also submit a short (one-page) summary that discusses 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) and/or if you include a discussion of the effects of varying a depth limit.

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 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!


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:

Notes on Coding in Lisp

Because Lisp is an interpreted language, it's very easy to test code fragments. I strongly recommend testing every function independently before moving on to the next one (as opposed to writing all of your code, loading it all in, and starting to debug the whole thing at once). You can debug bottom-up by testing low-level functions thoroughly before testing the higher-level functions that call them. You can also debug top-down by writing "stub" functions at lower levels that serve as place holders for the low-level functions, allowing you to test the higher-level functions and the overall structure of the code before adding the low-level functions.  The file test0 is the simplest possible case, so you may want to use this for your initial debugging.

The tools I primarily use for debugging are tracing, format statements in the program, and the step function. There is also some built-in functionality in Lisp for inspecting the stack and data objects, but I personally find that the interface for doing this in CLISP is not very easy to use.

Implementation Suggestions

This approach is more or less what I used to develop my own implementation. (Actually, my design was a bit more top-down, but it's easiest to write and test code bottom-up, so I've laid it out that way.) You should read these entire section before you get started. These notes are just an overview; you'll still need to figure out how to design the pieces and "glue" them together to have a working system.

Just as a guideline, my code for everything described here, including comments, is about 250 lines of code.

Write a function called GOALP that takes one argument (a game instance) and returns T if the specified game board is in the goal state, as defined above. Test this function on the test games provided.

In my design, the movements are implemented in two steps. First, there is a set of operators that compute how a given move affects the game state, and that return the state-change information without actually changing the board. Second, there is a single APPLY-MOVE operator that creates a new game board with the move applied to it. The advantage of this decomposition is that I can first compute all of the legal moves (and test this code during the development process), then apply each of them sequentially.

I suggest writing four operators (MOVE-UP, MOVE-DOWN, MOVE-RIGHT, and MOVE-LEFT), each of which can be applied to a blank square on the board. These operators are analogous to the move operators for the 8-puzzle, but instead of moving a single tile, you need to move the adjoining vehicle, which will take either 2 or 3 spaces.

In my implementation, these operators return 2 values using the values function: the name of the vehicle to be moved, and the space that moving it will free up. Board locations are represented as (x, y) pairs, where x and y are zero-based.

For example, on the game board shown in test2, applying the operator MOVE-RIGHT to the location (2,2) (i.e., the 3rd row and 3rd column) would return (values g (2 4)), meaning that I can "move" the blank space at (2, 2) to the right by moving vehicle g (to the left), freeing up location (2 4) (the 5th space in row 3). If the operator is not legal (because there is not a vehicle in the right direction, or the vehicle is not properly oriented), the functions return (values nil nil).

Write a function LEGAL-MOVES that loops across the game board, trying to apply each of the four operators to each of the board locations, and collecting a list of legal moves. This function should just return the list of legal moves (which will be NIL if there are no legal moves on the board).

Write the function APPLY-MOVE, which should take a move, represented as a triple: the empty square ((x,y) location) to free up, the vehicle to move into it, and the square that will become empty after the move. This function should create a new game instance that has a new unique name (which you can generate using the gensym function), a copy of the game board that is then updated to reflect the move being applied, a link back to the parent node, and a depth that is one greater than the parent's depth.

Write the BASIC-SEARCH function as given in Slide 28 from the September 8 slides. You might want to use the &key feature to include optional arguments that can be passed to this function, such as a depth limit. Note that the queueing function is sent into this function -- the best way to do this is to send in the function binding, e.g., #'q-bfs, and use (funcall q-fn ARG ...) to invoke the queuing function.

Detecting repeated states is very important in this domain, so you may want to have this function maintain a CLOSED list (list of nodes that have been expanded) as well as the usual OPEN list. You'll probably want a separate function to detect repeated states and remove them from the list of new nodes, or you could do this check in the EXPAND function. (Note that I've given you ARRAY-EQUAL, which can be used to test whether two game boards are the same.) You'll also want to check for the depth limit, and may want to have the option of setting the depth limit to NIL, meaning that there is no depth limit.

You should also keep track of the cumulative number of generated and expanded nodes, since you'll need to report those in your final results. This function should return a list of four things: either the symbol 'SUCCESS or 'FAIL, the goal node found, the number of created nodes, and the number of expanded nodes. You can then pass this list to PRINT-SEARCH-INFO, which will print a summary of the search, including the path back to the node (assuming you've linked all of your parent nodes correctly!)

Write the EXPAND function: given a node to expand, apply APPLY-MOVE to all of the moves listed by LEGAL-MOVES.

Write Q-BFS (the function to be called by BASIC-SEARCH) and BFS (the wrapper that invokes BASIC-SEARCH with Q-BFS). Write Q-DFS (the function to be called by BASIC-SEARCH) and DFS (the wrapper that invokes BASIC-SEARCH with Q-DFS). These functions should just be a line or two each.

You're done! :-) (modulo testing, gathering results, debugging, getting rid of the infinite loops...)