CMSC 471

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)

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 include 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)

3. Analysis of Search Space (10 points)

Background and Design Guidance

Rush Hour

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.thekidzpage.com/freekidsgames/games/rush/index.htm. 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

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

• There are several functions for writing debugging and/or logging messages. If you use the format function with a second argument of *DEBUG*, the message will be written to the global variable *DEBUG*. By default, this global variable is bound to T, which sends messages to standard output (i.e., the screen). You can send this output to a file by using open-debug with the name of the file. When you close the logging/debugging file with close-debug, it will revert to sending messages to standard output. Note that because of buffering, until you actually close the log file, you may not see anything in the file.
• The x-coord and y-coord functions are implemented using Lisp's macro capability. This is an efficient way to do in-place expansion, giving a shorthand representation for frequently used code fragments without the overhead of a function call. If you decide to use macros in your own code, be sure you read up on them first, since getting the right things to evaluate at the right time with the backquote-comma (` ,) syntax can be tricky.
• I've used an array to represent the game board. The main functions you need to know for manipulating arrays are make-array, array-dimensions, and aref, which dereferences an array location.
• I've written the load-game function, so for this assignment, you won't need to do much of your own I/O. However, you might want to take a look at this function and the debugging functions to learn how some of the basic I/O functions work (open, close, with-open-file, print-object, read, and read-line).
• In Common Lisp, functions can return more than one value. The values function is used to construct a set of multiple values. There are special functions for receiving these multiple values, primarily multiple-value-setq and multiple-value-bind (which behaves like let, i.e., it binds the values locally). The function read-from-string returns multiple values (the next token in the string and the index into the string where that token ended). You'll see in read-token-line how to catch and use those multiple values. If you treat a function that returns multiple values as returning just one value, you'll get the first value, which is often what you want. Values aren't really necessary (and there's raging debate in the Lisp community about whether using them is a good idea or not). You may want to use them in your code, in cases where you want to return more than one value (e.g., from the basic search function), or you may just decide to construct a list of values. Either way is acceptable.

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

PLEASE NOTE: You have a long time to complete this assignment. It will take a lot of time to implement everything and get it working. You should start TODAY. You should not put it off until the last few days before the due date. You have been warned.

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.

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 30 from the February 4 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...)