********************************************************************** File ~/../public/A2/README Homework Assignment 2 CSE 150, UCSD Winter 1997 Due: Monday, February 3, midnight ********************************************************************** >>> SUMMARY: This assignment is the second in a series of three which will introduce you to the notion of "state space search" in AI. In this assignment, we will use the "helper" functions that we designed in assignment A1, along with a search engine, to actually solve the 8-puzzle. To do so, we will implement breadth first search, depth first search with a depth bound, and iterative deepening. Then we will compare the run times. When we are done with this, we will be able to play with heuristics on the next assignment. To Recap: The 8-Puzzle is a problem involving 8 numbered, movable tiles set in a 3 x 3 frame. One cell of the frame is always empty thus making it possible to move an adjacent tile into the empty cell. For example, when you buy it at the store, the puzzle may have the configuration on the left below. The problem is to find a series of moves that leads you to the goal on the right, no matter what the initial configuration. (Actually, some faulty puzzles make the problem impossible! Fortunately for you, we will not give you any such faulty puzzles!) ; +---+---+---+ +---+---+---+ ; | 2 | 8 | 3 | | 1 | 2 | 3 | ; +---+---+---+ +---+---+---+ ; Initial: | 1 | 6 | 4 | Goal: | 8 | | 4 | ; +---+---+---+ +---+---+---+ ; | 7 | | 5 | | 7 | 6 | 5 | ; +---+---+---+ +---+---+---+ Our representation of the 8-puzzle will simply be a list of elements, read from left-to-right, top-to-bottom. We will use "e" to represent the empty square in the list. So our representation of the initial state above would be: (2 8 3 1 6 4 7 e 5) and the goal state is: (1 2 3 8 e 4 7 6 5) Note that there may be MANY possible initial states. Otherwise it wouldn't be much of a problem! One could also define different goal states, and this approach would work fine for that also. But we will only use one goal state, while testing on different initial states. >>> RULES: In writing your function definitions, you may use any built-in LISP function, special form, or macro introduced in Chapters 1 through 12 in the Winston and Horn text, except for SET, SETF, and SETQ. Also, you may not use any iteration constructs such as DO, DOTIMES, DOLIST, or LOOP. As usual, SETQ and SETF will be useful while you are *developing* your code, to define test arguments. For example: USER: (setq i '(2 8 3 1 6 4 7 e 5)) (2 8 3 1 6 4 7 E 5) USER: (sss i) (U U L D R) USER: (sss i 'DFS) (U U L D R) USER: (sss i 'DFS 15) ; don't try this at home...leave it to the professionals! (U U L D D R U L D R ...) MAKE SURE SUCH "TESTING" CODE IS NOT IN YOUR TURNED IN HOMEWORK FILE! You may discuss your program with other students or the TA or the professor. However, you may not copy anybody else's program. In writing your code, you are on your own. >>> ASSIGNMENT: This assignment has SEVEN parts, described below. Each part involves defining a function with a specified name. (You may find it useful to define some other functions too, if you wish.) All these function definitions should be put in a file named "hw2.cl" so that when that file is loaded into LISP, evaluating calls to the functions will work as required. Make sure the file name and function names are spelled correctly; your assignment will be graded in part by a computer program, and computer programs don't handle misspellings very well. Make sure your programs are commented in acceptable LISP style! Your file "hw2.cl" must be submitted using the "turnin" utility no later than the due time deadline specified above. Once you have done a "prep cs150w", just type "turnin hw2.cl" to submit your solution file. ---------------------------------------------------------------------- Part I. We will all use the following data structure for the OPEN list: The open list will be a list of lists, of the form: ( .... ) where is a list of lists of the form: (( ) ( ) ...( )) This list is in reverse order from the initial state. The initial state is not on the list (since it didn't require any move to get to it!). ( ) is as in the last assignment, e.g., (L (2 8 3 1 6 4 7 e 5)) So, an example OPEN list is: (((U (2 E 3 1 8 4 7 6 5)) (U (2 8 3 1 E 4 7 6 5))) ((D (2 8 3 1 6 4 7 E 5)) (U (2 8 3 1 E 4 7 6 5))) ((L (2 8 3 E 1 4 7 6 5)) (U (2 8 3 1 E 4 7 6 5))) ((R (2 8 3 1 4 E 7 6 5)) (U (2 8 3 1 E 4 7 6 5)))) Define a function named OPEN-INIT that takes one argument, the initial state, and returns the first OPEN list generated from that state. This function is special in that, unlike the other functions defined below, it is the "creator" for an OPEN list - the other function will simply extend a given OPEN list. For example: USER(52): (setq i '(2 8 3 1 6 4 7 E 5)) (2 8 3 1 6 4 7 E 5) USER(53): (open-init i) (((U (2 8 3 1 E 4 7 6 5))) ; your result will all be on one line ((L (2 8 3 1 6 4 E 7 5))) ; Count parentheses!! Make sure your ((R (2 8 3 1 6 4 7 5 E)))) ; version produces the IDENTICAL result. ; This is a list of THREE paths, each ; ONE move long. To do this part, you need a "moves" function that, given a state, returns a list of possible moves out of that state. Luckily for you, we will supply that function! It is included in this directory, in the file "moves.cl". There are a bunch of functions in that file - the ONLY one you need is "moves", which works like: USER(10): (moves '(2 e 3 4 7 8 1 5 6)) ( (D (2 7 3 4 E 8 1 5 6)) (L (E 2 3 4 7 8 1 5 6)) (R (2 3 E 4 7 8 1 5 6)) ) (the nice layout above is mine: just to make it clear. What you actually get on your terminal is one big line) To automatically include this function in your code, put: (load "moves") at the top of your file. You will also probably want: (load "solnA1") there too - that will load our solution to assignment A1, which we include here also! ---------------------------------------------------------------------- Part II. Define a function named EXTEND-PATH that takes one argument, a path, and returns a list of all possible extensions to the path. It uses REMOVE-REDUNDANT to only give extensions that do not visit previous states. For example, USER: (extend-path (first (open-init i))) (((U (2 E 3 1 8 4 7 6 5)) (U (2 8 3 1 E 4 7 6 5))) ((D (2 8 3 1 6 4 7 E 5)) (U (2 8 3 1 E 4 7 6 5))) ((L (2 8 3 E 1 4 7 6 5)) (U (2 8 3 1 E 4 7 6 5))) ((R (2 8 3 1 4 E 7 6 5)) (U (2 8 3 1 E 4 7 6 5)))) This has taken the first path off of the result of (open-init i), and extended it in all possible ways, making a list of FOUR paths, all TWO moves long. Note that this is a legal OPEN list, all by itself! Let's see how the REMOVE-REDUNDANT makes a difference in EXTEND-PATH: USER(56): (setq test-path (first (extend-path (first (open-init i))))) ((U (2 E 3 1 8 4 7 6 5)) (U (2 8 3 1 E 4 7 6 5))) USER(57): (extend-path test-path) (((L (E 2 3 1 8 4 7 6 5)) (U (2 E 3 1 8 4 7 6 5)) (U (2 8 3 1 E 4 7 6 5))) ((R (2 3 E 1 8 4 7 6 5)) (U (2 E 3 1 8 4 7 6 5)) (U (2 8 3 1 E 4 7 6 5)))) Note that one possiblility is missing. Which one? Why? You can see that this method of keeping an explicit OPEN list costs some redundancy over the "keep the OPEN list in the system stack" method. However, this will prove useful later when we want to *sort* the OPEN list based on our heuristics. ---------------------------------------------------------------------- Part III. Define a function named SEARCH-BFS. SEARCH-BFS takes one argument, an OPEN list, and returns the path to the goal state by using a breadth first search. So, for example: (SEARCH-BFS (open-init '(2 8 3 1 6 4 7 e 5))) (U U L D R) SEARCH-BFS, like all of our search routines, will check for failure (empty open list), and then get the first path off of the OPEN list and check for success. If successful, it will return the path using our "PATH" function from the last assignment. If success is not at hand, it will recurse on a new OPEN list with the successors of that first path on the other end (treating the OPEN list as a queue, as discussed in class). SEARCH-BFS will use our function EXTEND-PATH to help in forming the new queue for the recursive call. ---------------------------------------------------------------------- Part IV. Define a function called SEARCH-DFS. SEARCH-DFS will take two arguments, an open list and a depth bound. It will make the same checks as the previous function, but then it acts somewhat differently, depending on whether the first path on the OPEN list exceeds the depth bound or not. I'll leave this (only slightly) tricky control structure to you. But remember, DFS means that new paths are added to the FRONT of the OPEN list. WARNING: It is very easy to get into a very deep recursion with this function! Even an infinite one! Make sure for your tests, that you leave the depth bound at something small, like 7. ---------------------------------------------------------------------- Part V. Define a function called SEARCH-ID. SEARCH-ID will take one argument (but you might find it useful to have an optional argument), an open list. It will use SEARCH-DFS to do iterative deepening. ---------------------------------------------------------------------- Part VI. Define a function called SSS (for state space search, but much easier to type!). SSS takes one argument, the initial state, and two optional arguments. The first optional argument is one of 'BFS, 'DFS or 'ID (default is 'BFS). The second optional argument only makes sense with DFS, being the depth bound on DFS. It defaults to 7. SSS checks whether it is at the goal state, and if not, calls one of search-BFS or search-DFS depending on its optional arguments. For example, USER: (setq i '(2 8 3 1 6 4 7 E 5)) ; an initial state (2 8 3 1 6 4 7 E 5) USER: (setq g '(1 2 3 8 e 4 7 6 5)) ; the goal state (1 2 3 8 e 4 7 6 5) USER: (sss g) ; the path to the goal state is nil! NIL USER: (sss i) ; five moves to the goal from the initial state "i" (U U L D R) ; this used the default: BFS USER: (sss i 'BFS) ; this explicitly specifies BFS (U U L D R) USER: (sss i 'DFS) ; Here, we try DFS with the default depth bound (U U L D R) USER: (sss i 'DFS 13) ; Here, we give it a deeper depth bound (U U L D R) USER: (sss i 'DFS 14) ; this shows the non-optimal property of Depth bounded (U U L D D R U L D R ...) ; Depth first search: We found a long path! USER: (sss i 'ID) ; Iterative Deepening will always give the (U U L D R) ; optimal answer... (What idiot language designer decided that printing out "..." would be an acceptable answer??) Why does DFS get a different answer for a different depth bound? ---------------------------------------------------------------------- Part VII. This part is more of a thought piece. Use the TIME function to find out which version is faster. For example, Try compiling some of your functions. For example, USER: (time (sss i 'BFS)) cpu time (non-gc) 1050 msec user, 184 msec system cpu time (gc) 0 msec user, 0 msec system cpu time (total) 1050 msec user, 184 msec system real time 1560 msec space allocation: 35066 cons cells, 0 symbols, 91952 other bytes, (U U L D R) The "gc" refers to the use of the garbage collector, which occasionaly must go about looking for unused CONS cells. This should not really count against you. Now, take a look at how much compilation helps. You can compile functions in lisp via: USER: (compile 'search-BFS) SEARCH-BFS NIL NIL Note that if you do a (load "hw2.cl"), your function will no longer be compiled! Now: USER(79): (time (sss i 'BFS)) cpu time (non-gc) 984 msec user, 134 msec system cpu time (gc) 200 msec user, 50 msec system cpu time (total) 1184 msec user, 184 msec system real time 1750 msec space allocation: 34116 cons cells, 0 symbols, 90256 other bytes, (U U L D R) Shows a faster result in non-gc user time. Questions: 1. Which is faster, BFS, DFS, or ID? On all problems? For all depth bounds? Try the following start state: (setq i '(2 8 3 1 4 5 E 7 6)) with DFS with a depth bound of 8 and 15 versus ID. What's going on? 2. What functions make the most difference in run time when they are compiled? How fast can you get your searches to run? I don't expect definitive answers to all of these questions, but I expect a reasonable effort. Please put this at the bottom of your file, appropriately set off with semicolons!