CMSC 671
Artificial Intelligence -- Fall 2003
HOMEWORK TWO
out 9/15/03 due 9/29/03
http://www.cs.umbc.edu/671/fall03/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
test0,
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 #1: Implement more than one option for checking repeated
states. Give results for the different options, and discuss how
changing this option affects the performance of search.
Bonus #2:
test4
is a harder problem (the first "real" game from the actual game). If
you can get your code to run to completion on this problem,
report your results and receive bonus points!
3. Analysis of Search Space (10 points)
How many legal states are there in the state space for each of the
five test cases given above?
Give exact values for test0, test1, and test2. For test3 and test4,
you may give an estimate, along with a discussion of whether your
estimate is an upper or loew 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. x=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.eagle-i.com/JAVA/rush.html.
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:
- 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 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 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 Russell & Norvig's
Figure 3.9. 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 symbol that
names the function, e.g., 'q-bfs,
and use (funcall (symbol-function 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...)