**********************************************************************

Homework Assignment 3
CSE 150, UCSD
Fall 2002

NEW DUE TIME!!!
Due: Thursday November 14, 2002 at Midnight

**********************************************************************

>>> SUMMARY:

This assignment is the third (and last!) in a series of
three designed to introduce you to the notion of "state
space search" in AI.  In this assignment, we will add two
more search types to SSS: type A* for algorithm A*, and RBFS
for recursive best first search.  Then we can compare run times
for these with BFS, DFS and ID.  Even simple heuristics can
beat DFS if the depth bound is high enough.  To verify this,
you will implement the out-of-place heuristic and perform
some experimental analysis.

BONUS EXTRA CREDIT TASK: Create your very own heuristic!!!
See if you can develop something innovative, ingeniously
augment your out-of-place function, or just code-up
something you found in a book in order to try to beat your
"plain" out-of-place heuristic's performance.

To see how the 8-puzzle works (if you haven't got it by now!)
see the README for assignment A1 or A2.

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

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 (...or even your cat).  However, you must
follow the Gilligan's Island Rule.  In writing your code,
you are on your own.

>>> ASSIGNMENT:

This assignment has seven sections, described below, plus
the BONUS Extra credit section.  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 "hw3.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 "hw3.cl" must be submitted using the "turnin"
utility no later than the due time deadline specified above.
Once you have done a "prep cs150f", just type "turnin
hw3.cl" to submit your solution file.  DO NOT turn in
multiple or tarred files!

The turnin.dest directory will be removed at midnight on the
due date so remember to turnin on time!

----------------------------------------------------------------------
Part i.  Useful functions we're giving you.

Once again, we have provided the moves function in moves.cl,
and solution files to assignments A1 and A2 which contain
functions necessary to this assignment.  These are
"solnA1.cl" and "solnA2.cl".  Additionally, we are providing
you with a number of utility functions (described below) in a file
called "utilsA3.cl".  You may use your own functions if you
are confident of them, but you will only be turning in the
new code, so make sure that if you load your solutions that
you load them using the given file names (no paths!), since
these are what we'll be providing when we test your code.
Thus, you could do something like the following at the top
of your code:

   (load "moves.cl")
   (load "solnA1.cl")
   (load "solnA2.cl")
   (load "utilsA3.cl")

Recall that heuristic search uses an evaluation function
like

                    f(node) = g(node) + h(node)

where g gives the actual cost of reaching the node in the
search tree, h gives the estimated cost of getting from the
node to the goal, and f is the evaluation function for our
heuristic search.  We will define these functions over
paths, since each path implicitly has the node of interest
as its first element, and since we want to define g to be
the depth of the node in the search tree (equivalently, the
length of the path).

Here are some utility functions which will be useful for
this assignment:

;;; Get the state out of the most recent move of path.
;;; Input:  A path
;;; Output:  The state of the path (i.e. the state of the first element of the path)
;;; Side-effects:  None
(defun get-current-state (path) (get-state (first path)))

;;; These functions here are helper functions for RBFS
;;; For RBFS, we're going to use a slightly different data structure.
;;; The repeat loop of the RBFS algorithm keeps track of the f-score of a given node (path)
;;; and alters it based on various components of the algorithm.  So,
;;; instead of just a path, we will keep a list with the path and the f-limit
;;; assigned to that node (i.e.  (path f-value)).

;;; Given an RBFS-path, return the score portion
;;; Input:  a list containing two items, the first is a path and the second is a score
;;; Output:  The score portion of the list
;;; Side-effects:  None
(defun get-score (p)
  (second p))

;;; Given an RBFS-path, return the  node (or path) portion
;;; Input:  a list containing two items, the first is a path and the second is a score
;;; Output:  The path portion of the list
;;; Side-effects:  None
(defun get-node (p)
  (first p))

;;; This function will help us merge out lists.  This function takes two
;;; RBFS-paths and compares the f-scores of the two.
;;; Input: two RBFS-paths (a list containing two items, the first is a path and the second is a score)
;;; Output:  T if the score of path1 <= the score of path2, Nil otherwise
;;; Side-effects: None
(defun list-comp (path1 path2)
  (<= (get-score path1) (get-score path2)))

;;; Given a list of paths, return a new list containing RBFS-paths
;;; Input:  p, A list of paths and f, a score function (like out-of-place-f)
;;; Output:  A list of RBFS-paths (an RBFS-path consists of a two item list with the first item
;;; being a path and the second item the f-score of the path.
;;; Side-effects: None
(defun make-score-list (p f)
   (if (endp p) '()
     (cons (cons (car p) (list (funcall f (car p)))) (make-score-list (cdr p) f))))


The functions above are provided in "utilsA3.cl".

get-current-state is a fairly obvious utility function.
null-move-path and null-move-path-p are used to construct
and recognize paths for the initial state.  Their only
purpose is to allow the initial state to be conveniently
passed to the heuristic function, f, as a path, and to be
assigned a value of 0 for the g component of f.  We'll
talk more about the RBFS helper function in Part V.

----------------------------------------------------------------------
Part I.

Define a function called OUT-OF-PLACE that takes one argument,
a state of the 8-puzzle, and returns the number of tiles out
of place (with respect to our goal state). For example,

USER(2): (setq init '(2 8 3 1 6 4 7 e 5))
(2 8 3 1 6 4 7 E 5)

USER(3): (setq goal '(1 2 3 8 e 4 7 6 5))
(1 2 3 8 E 4 7 6 5)

USER(4): (OUT-OF-PLACE init)
4 ;; N.B.: Don't count "e" as out of place!

USER(5): (OUT-OF-PLACE goal)
0

OUT-OF-PLACE is a particularly simple state evaluation function.
We are going to use it in a heuristic search. N.B.: it returns
a LOWER number the BETTER the state is.


----------------------------------------------------------------------
Part II.

Define a heuristic evaluation function called
OUT-OF-PLACE-F.  OUT-OF-PLACE-F evaluates and returns the
f-cost associated with the single path it takes as its
argument.  The f-cost of a path is simply the sum of its
g-cost and h-cost.  OUT-OF-PLACE-F uses OUT-OF-PLACE to
determine the h-cost of a path.  A path's h-cost is the
value returned by OUT-OF-PLACE for the state of the last, or
"current", move of the path.  The g-cost of a path is its
depth in the search tree (i.e., the length of the path).
For example, the state (1 2 3 e 8 4 7 6 5) has ONE square
out of place, the "8-square." Using this as the current
state in a call to OUT-OF-PLACE-F, we get :

USER(1): (OUT-OF-PLACE-F '((D (1 2 3 e 8 4 7 6 5)) 
                           (R (e 2 3 1 8 4 7 6 5)) 
                           (U (1 2 3 4 8 7 e 6 5))
    (nil (1 2 3 e 8 7 4 6 5))))
4

The path in the above example has an h-cost of 1 and a
g-cost of 3, resulting in an f-cost of 4.

The provided function, get-current-state, will be useful for
extracting the current state from the path passed to
OUT-OF-PLACE-F.

----------------------------------------------------------------------
Part III.

Define a higher-order function named BETTER. BETTER takes
one argument, an evaluation function f, and returns a lambda
expression that takes two paths as arguments. The function
"f" is intended to be a path evaluation function, such as
OUT-OF-PLACE-F above, that returns a LOWER number for better
paths.  The lambda expression returned by BETTER will take
TWO paths as arguments, and use funcall to call f on each
path argument and return T if the first is better than OR
EQUAL TO the second, NIL otherwise.

For example:

;; set up 2 initial states for testing
USER(1): (setq i1 '(2 8 3 1 6 4 7 E 5))       
(2 8 3 1 6 4 7 E 5)
USER(2): (setq i2 '(1 2 3 8 6 4 7 5 E))
(1 2 3 8 6 4 7 5 E)
;; make them into open lists:
USER(3): (setq o1 (make-open-init i1))
(((NIL (2 8 3 1 6 4 7 E 5))))
USER(4): (setq o2 (make-open-init i2))
(((NIL (1 2 3 8 6 4 7 5 E))))
;; extend them, and get the first path off the extension:
USER(5): (setq p1 (first (extend-path (first o1))))
((U (2 8 3 1 E 4 7 6 5)) (NIL (2 8 3 1 6 4 7 E 5)))
USER(6): (setq p2 (first (extend-path (first o2))))
((U (1 2 3 8 6 E 7 5 4)) (NIL (1 2 3 8 6 4 7 5 E)))

;; Note:  BETTER returns a lexical closure
USER(5): (BETTER #'OUT-OF-PLACE-F)                
#<Interpreted Closure (:INTERNAL BETTER) @ #x5407ba>

;; Try heuristic function  on p1 and p2
USER(6): (funcall #'OUT-OF-PLACE-F p1)
4
USER(7): (funcall #'OUT-OF-PLACE-F p2)
4

;; BETTER makes a comparison operation out of the heuristic function
USER(8): (funcall (BETTER #'OUT-OF-PLACE-F) p1 p2)
T
USER(9): (funcall (BETTER #'OUT-OF-PLACE-F) p2 p1) 
T


----------------------------------------------------------------------
Part IV.

Define a search routine named SEARCH-A*.

SEARCH-A* takes two arguments, an open list and a heuristic
evaluation function that works on paths.  SEARCH-A*
implements the A* algorithm discussed in class. A* will look
a lot like your BFS routine, but the new open list in the
recursive call will have to be sorted each time, instead of
simply adding the new paths from EXTEND-PATH to the back of
the open list.

For example:

USER(10): (search-A* (make-open-init i1) #'Out-of-place-f)
(U U L D R)

As you can see from the above example, the built-in Common LISP 
function SORT can be used to do the sorting.  SORT takes two 
arguments:  a list and a predicate which compares two items on the 
list.  SORT returns the list sorted according to the predicate.  
For example:

USER(1): (sort '(3 1 4 1 5 9) #'<)
(1 1 3 4 5 9)

One problem with this method is that a given open list might
get sorted repeatedly.  This can be bad, especially if the
built-in SORT function is quicksort, whose worst-case
behavior occurs on a sorted list.  A better solution is to
always sort the *new* path extensions (a very short list),
and then MERGE this sorted list with the already-sorted open
list. This solution requires that the open list always be
sorted. Initially, this will be trivially true when you use
MAKE-OPEN-INIT, since the initial open list will simply
consist of one path with the null move on it. Then, by
making sure that new extensions are always sorted before
they are merged in, you can prove to yourself that the open
list will always be sorted by induction.  In order to merge
your two sorted lists, you can use the built-in function
MERGE.  MERGE takes four arguments: the type of the desired
result, the two (already-sorted!) lists to be merged, and
the predicate according to which the merge takes place.  For
example,

USER(1): (merge 'list '(1 3 5 7 9) '(2 4 6 8 10) #'<)
(1 2 3 4 5 6 7 8 9 10)

USER(2): (merge 'list '(3 1 7 5 9) '(2 4 6 8 10) #'<)
(2 3 1 4 6 7 5 8 9 10)

Note that the second call didn't work because the two lists
were not already sorted.  Remember, in your recursive call,
you should only need to sort the shorter of the two lists -
the paths resulting from the expanded move.

----------------------------------------------------------------------
Part V.

Write a search function called search-RBFS which implements
recursive best first search as described in Russel and Norvig.  This
function is a little bit tricky and has input that is different from
what we have previously used, so we have provided a number
of helper functions described above and found in UtilsA3.cl.

Here is an outline of the functions that you should write:

;;; p = a path
;;; limit = the depth limit
;;; f = the heuristic function

(defun search-RBFS (p limit f) ...
This is a very simple funtion that should just call RBFS below and 
parse the output from RBFS (which is an RBFS-path) so that a nice path 
of moves is returned.  The last two parameters should be made optional 
and default to an appropriate value.


;;; p = a path
;;; limit = the current depth limit
;;; f = the heuristic function
(defun RBFS (p limit f) ....

The input, p, to this function is JUST A PATH (not an open list).  Notice
that RBFS only passes around nodes and does not deal with
an open list.  This function will implement the part
of the code in Russell and Norvig that is NOT in the repeat loop and will
call, RBFS-repeat to do the repeat loop portion.  This function returns
what is called an RBFS-path.  That is a two item list containing the path
and the score of the path.


;;; successors = a list of RBFS-paths **** (NOTE that these are RBFS-paths)
;;; limit = the current depth limit
;;; f = the heuristic function
(defun RBFS-repeat (successors limit f)

This function implements the portion of the algorithm in the repeat loop.
RBFS-paths are used so that we can keep track of the f-score as we change
it according to the algorithm.  You may find the "min" function useful here.  Notice
that this function will call RBFS as part of its operation.  Don't let this confuse
you.  Just treat it like any other function call.

Don't get confused about what is passed into the three function.  search-RBFS
and RBFS both take a path as an argument (a list of moves), however, RBFS-repeat
takes a list of RBFS-paths (which are two item lists with a path as the first item and
a score as the second item).  Make sure you are passing the right things to these
function as you make your recursive calls.

One note, the algorithm as described in Russell and Norvig uses infinity for the limit
 in a number of places.  It would be nice to do it that way, however, I found it made
things to complicated.  Instead, just use a number like 10,000 as the equivalend of 
infinity.

----------------------------------------------------------------------
Part VI.

Modify SSS by adding the keyword argument "F" which
specifies the heuristic evaluation function on paths.  Add
A* and RBFS as search types to SSS also.  The default values
for the keywords should be BFS for :type, 7 for :depth, and
#'OUT-OF-PLACE-F for :f.  As before, the first argument to
SSS is the mandatory initial state argument.  When you are
done, SSS will support 5 search types!

Here are some sample (legal) calls to this new, improved
SSS, given the earlier setq of symbol i:

;; uses all defaults
(SSS i)                     

;; uses A* with default function
(SSS i :type 'A*)         

;; Uses RBFS with some other choice of heuristic function
(SSS i :type 'RBFS :f #'some-other-f)                                       

;; Since BFS is selected, the depth bound will be ignored
;; because it's not passed to SEARCH-BFS (this is fine) 
(SSS i :type 'BFS :depth 500)   

----------------------------------------------------------------------
Part VII.

In this part we compare our new search routines.  Again, use the TIME 
function to find out which version is faster. If you want, you can 
compile your whole solution (and similarly, previous parts) through 
the command:

USER: (compile-file "hw3.cl")
...lots of stuff....

Now, if you do:

USER: (load "hw3")
; Fast loading /a/desi/home/desi/gary/classes/150/pa/A3/hw3.fasl.


Lisp will automatically load the compiled version if you don't
give the ".cl" extension.  Alternately, you can (load "hw3.fasl").
(load "hw3.cl") forces the uncompiled code to be loaded.
Note:  whichever you've loaded most recently is in force!

Now do the following:
   (setq init '(2 8 3 1 6 4 7 e 5))
   (time (sss init :type 'BFS))
   (time (sss init :type 'DFS :depth 12))
   (time (sss init :type 'ID))
   (time (sss init :type 'A*))         ; here - you can use either 
   (time (sss init :type 'RBFS)) ; out-of-place or your new 
                                        ; heuristic fn.

1. Which algorithm is fastest for this initial state?

2. Can you get DFS to be faster than one or both of A* and IDA*
on this initial state by varying the depth parameter?  Will BFS or
ID ever be faster than A*?  What about IDA*? EXPLAIN.

----------------------------------------------------------------------
EXTRA CREDIT

Define your own evaluation function.  It may include
OUT-OF-PLACE as a component, if you wish.  Use
OUT-OF-PLACE-F as "template" for designing this
function. Does it beat out-of-place in time to a solution?