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.
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!
A couple of notes on the Lisp code in this file:
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 text, 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.
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.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).
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!)