Project 1.  Problemsolving agent for the 8-puzzle world...

Assigned: [Jan 24th, 2012]
Due: [Feb  14th, 2012]

In this project, you will extend an A* search algorithm and experiment
with it in a problem domain--specifically 8-puzzle domain. 
Part I asks you to complete some routines for generating children, and
testing goals for 8-puzzle problem. Part II asks you to extend the
skeleton of an A* search algorithm, and Part III aks you to run some
experiments and do analysis. 

PART I: Implementing 8-puzzle.

In this part we will implement 8-puzzle problem, and experiment with
several instances of the problem using the A* search algorithm that
you extend above.  We shall assume that the goal configuration of the
8-puzzle is always (note that this is slightly different from the text
example):

1 2 3 
4 5 6
7 8 -

(where "-" is the blank tile). 

To implement the 8-puzzle, we need to do the following:

Task 1. Develop a data structure for holding the 8-puzzle state

Task 2. Develop a function for generating 8-puzzle states that can be
   reached from the current state in one step. The result of this
   function should be elements of type (<act> <cstate>), where taking
   the action <act> from the given state will put us in the state
   <cstate>. 

Task 3. Develop a goal-test function

Task 4. Develop the heuristic functions as necessary

Task 5. Write a children generator function that takes a search-node, 
   uses the function in 2 to generate children nodes of this search
   node, and uses the heuristic function in 4 to set the g, h and f-values
   of the resulting nodes. 

Data structures for 8-puzzle: The most obvious (but not necessarily
the most efficient) representation would be a 3x3 array of integers,
with blank tile represented as 0, and the other tiles represented as
integers from 1 to 8. 

Common lisp provides the array data structure to support this. We can
generate a 3x3 array with the command make-array.

Here are some examples that explain the use of array data structures:

    USER(36): (setq j (make-array '(3 3) :initial-contents '((1 2 3) (4 5 6) (7 8 0))))
      #2A((1 2 3) (4 5 6) (7 8 0))
    USER(37): (aref j 0 0)
       1
    USER(38): (aref j 2 2)
       0
    USER(39): (aref j 1 2) ;;row 1 and column 2
       6
    USER(40): (setf (aref j 2 2) 8)
       8
    USER(41): j
       #2A((1 2 3) (4 5 6) (7 8 8))
    USER(42): 

To generate  new states from the old states, we note that in general
the blank tile can be sent up, down, left or right, giving at-most 4
children per node. Depending on the place where the blank tile is, the
some of these moves may not be possible (in which case the
corresponding child will not be there.)

Here is a code fragment for putting together the children of a state,
which calls left-child, right-child, up-child and down-child
respectively:

(defun puzzle-children (state)
 (append (left-child state)
	 (right-child state)
         (up-child state)
         (down-child state))

Now, let us write left-child function. This function needs to return
either a list ((go-left <left-state>)), or nil. (The extra parenthesis
are so that we can "append" the children in the puzzle-children
function). 

In order to generate left-child, we first need to find out the
coordinates of the blank in the current state, generate the
coordinates of the position to the left of the blank, check if that
coordinate is feasible, if it is, swap the contents of that position
and the current position of the blank. 

We start with a small auxiliary function which tells us where the
blank is in the current state.

(defun where-is-blank (state)
  (loop for x from 0 to 2
    do (loop  for y from 0 to 2
               when (zerop (aref state x y))
               do (return-from where-is-blank (list x y)))))

We also need an auxiliary function that makes a new copy of the puzzle
state (so we can modify it appropriately to generate the child state):

(defun copy-puzzle-state (state)
  (let ((new-array (make-array '(3 3))))
	(loop for x from 0 to 2
              do (loop for y from 0 to 2
                    do (setf (aref new-array x y)
		             (aref state x y))))
	;;return new-array
         new-array))

Now we can write the code for generating the left-child:

(defun left-child (state)
  (let* ((blank-pos (where-is-blank state))
         (left-pos (list (first blank-pos)
		         (- (second blank-pos) 1)))
         ;;left position has the same row coordnate, but a different column
         ;;coordinate..
 	)
	(if (>=  (second left-pos) 0)
	  ;;going left doesn't make us go out of the board
         (let ((left-state (copy-puzzle-state state)))
	      ;;shift the left tile into the blank-pos
             (setf (aref left-state (first blank-pos) 
				   (second blank-pos))
		    (aref left-state (first left-pos) 
				    (second left-pos)))
               ;;shift the blank into the left-tile position
             (setf (aref left-state (first left-pos) 
				    (second left-pos))
			0)
             ;;return the action and state
            (list (list 'go-left left-state))))))

In the function above, let* is important as it does the initialization
sequentially. "let" will do the initialization concurrently.

Here is how it works:

    USER(107): j
        #2A((1 2 3) (4 5 6) (7 8 0))
    USER(108): (left-child j)
        ((GO-LEFT #2A((1 2 3) (4 5 6) (7 0 8))))
    USER(109):             

I have now given the solution for task 1 and the partial solution for
task 2. 

Complete the programs for  the rest of task 2 (develop code for
right-child, up-child and down-child) and tasks 3, 4 and 5.

**In doing Task 4, generate code for two heuristic functions:

  Num-Misplaced-tiles heuristic
  Manhattan-distance  heuristic

These were discussed in the class

**In doing Task 5, assume that each action has 1 unit cost. So if a
  node has g-value k, then its children will all have cost k+1.


Part II. Extend the code of a skeletal A* search algorithm

We shall start with a skeleton of the A* search algorithm:

(defun A* (nodes goalp children-fn fvalue-fn)
  (cond ((null nodes) nil)
	;; Return the first node if it is a goal node.
	((funcall goalp (first nodes)) (first nodes))
	;; Append the children to the set of old nodes
	(t (A* (sort (append (funcall children-fn 
		                (first nodes))
			     (rest nodes)) 
		     #'<		
		     :key fvalue-fn 
		     )
		 goalp
		 children-fn
		 fvalue-fn))))


(The sort function we are using is a built-in function for
commonlisp. It takes three arguments: List to be sorted, the
comparision predicate with which sorting is done (in our case <) , and
an optional argument :key, which takes a function and applies it to
the elements of the list, to get the field over which items of the
list are compared (in our case, the f-value))

To make our life simple, we shall assume that search nodes are defined
as structures with at least the following slots:

(defstruct node
  STATE   ;;the state of the problem corresponding to this node
  PARENT  ;;the node which is this nodes' parent
  ACTION  ;;the action which was taken at the nodes parent to get here
  G-VAL   ;;The g-value of the node
  H-VAL   ;;THe h-value of the node
  F-VAL   ;;THE f-value of the node
)



1. It keeps track of statistics on:

       A. The number of nodes generated, and the number expanded.
       B. The maximum amount of memory consumed (the maximum size to which
           the search queue grew), 
       C. The depth at which the goal node was found
       D. The average and effective branching factors of the tree
            (average branching factor is calculated by averaging the
             number of children of all expanded nodes. Effective
             branching factor eb is calculated by solving the equation:
             eb^gd = ne (where gd is the goal depth and ng is the
             number of nodes expanded). 
       E. The cost of the goal node found. 

The statistics should be printed at the end of each search run.  It is
okay to define global variables and update them to keep track of the
statistics. 

2. It prints the path from the root node to the goal node that is
   found. (It is okay to make a top level routine which calls A*, and
   processes the returned goal node to print the path. For this
   purpose, assume that the function node-parent refers to the parent
   of the node. It is nil for the root node. 





Part III. Experimenting with the 8-puzzle problems. 

In this part you run the code you developed on at least the following
8-puzzle initial states. For each initial state, you should run the
following search algorithms --

1. breadth-first (A* with h=0), 
2. A* with h= misplaced tiles 
3. A* with h=manhattan distance

You will compare the performances of these search algorithms in terms
of the statistics you collect (see part 1) and write a report
commenting on the statistics and whether they are in accordance with
the theory we learned in the class. In addition to the normal stats,
you should also "time" your programs. You can use the in-built "time"
function for this as illustrated below:

   USER(110): (time (loop for x from 1 to 1000 do ( + x x)))
   ; cpu time (non-gc) 130 msec user, 10 msec system
   ; cpu time (gc)     140 msec user, 0 msec system
   ; cpu time (total)  270 msec user, 10 msec system
   ; real time  390 msec
   ; space allocation:
   ;  24,125 cons cells, 0 symbols, 88,120 other bytes
   NIL

*** IT IS HIGHLY RECOMMENDED THAT YOU COMPILE YOUR CODE TO INCREASE SPEED.

Test cases:
 
Case 1: (2 step solution)

1 2 3 
4 5 6
- 7 8

Case 2: (3 step solution)

1 2 3
4 6 -
7 5 8

Case 3: (5 step solution)

4 1 2
- 5 3
7 8 6



Case 4: (8 step solution)

4 1 2 
7 6 3
- 5 8

Case 5: (10 step solution)

4 1 2
7 6 3
5 8 -

You are *encouraged* to experiment with additional initial state
configurations of your own choosing and include them in the
analysis report. You can generate a random initial state that is k
moves away from the goal state by calling the function

(random-puzzle-state k)

See the end of the project description for the code for
random-puzzle-state. 

**I reserve the right to add more test cases (and announce them in the
class). 


PART IV EXTRA CREDIT: (The marks you get on extra-credit portions will
be used to make-up for your deficiencies on other
homeworks/projects/exams etc.). You can pick all or some of the extra
credit tasks:

Task 1. Add depth-first search (A* with h= -2g) to the suite of
algorithms being compared in Part III. Since depth-first search may
get into loops and not terminate, you will have to modify the search
algorith and put a depth cutoff. 

Task 2. Consider defining the f-value to be 
  f(n) = w g(n) + (1-w)* h(n)

where w is a number between 0 and 1. 

Clearly, w= 0.5 corresponds to the normal evaluation function. 
Consider the effect of higher and lower values of w on the peformance
of the A* algorithm. You can restrict your check to a single
heuristic--say manhattan distance heuristic, and a small set of
problems. 

Task 3. Modify the child-generation function so that it does not generate
children states that are identical to an ancestor of the current
node. Run the tests of Part III again to find out how much of an effect this
duplicate removal algorithm has. 

Task 4. Consider implementing the pattern-database heuristic for the
8-puzzle. (If I haven't already discussed this in the class, and you
want to do it, let me know and I will tell you where the algorithm
writeup is). 

================
Code for generating random-puzzle-state

The code is given below. You can, for example, experiment with a
series of random problems of increasing solution length using your
manhattan and misplaced heuristics and see how the performance
degrades.

Here is the code. It expects that you have puzzle-children function
that returns children of a state in the form of list whose elements
are of the form (<action> <state>)

;;---------code start
(defun random-puzzle-state (distance &optional state &aux path cstate)
;;geneate a state that is distance away from the given state
;;if no goalstate is given we set it to the normal goal state config
  (unless state 
    (setq state  (make-array '(3 3) :initial-contents '((1 2 3) (4 5 6) (7 8 0)))))
  (setq cstate state)
  (push cstate path)
  (loop for move from 1 to distance
      do 
	(let ((children (mapcar #'second (puzzle-children cstate))))
	  ;;find a random child that is not on the path
	  ;; (otherwise you get loopy paths)
	  (loop for child in (random-permute children)
	      thereis (if (not (member child path :test #'puzzle-equal))
			  (progn (setq cstate child)
				 (push cstate path))))))
  (if (null cstate)
      (random-puzzle-state state distance)
    cstate))


(defun puzzle-equal (state1 state2)
  (loop for x from 0 to 2
      always (loop for y from 0 to 2
		 always (equal (aref state1 x y) (aref state2 x y)))))

(defun random-PERMUTE (list)
  ;;takes a list and permutes the list randomly
  (let ((l (copy-list list))
	(ret nil))
    (do ()
	((null l) ret)
      (let ((i (random (length l))))
	;;picks a random element of the list, deletes it
	;;and pushes it into the newlist
	(push (nth i l) ret)
	(setf l (delete (nth i l) l))))))


;;;;;;;;;;;;;;;USAGE
;USER(55): (random-puzzle-state 1)
;#2A((1 2 3) (4 5 0) (7 8 6))
;USER(56): (random-puzzle-state  1)
;2A((1 2 3) (4 5 6) (7 0 8))
;;notice how it generated two different states when it was called with
;;the same arguments two times. There is a random part to the code!
;USER(50): (random-puzzle-state  5)
;#2A((2 0 3) (1 5 6) (4 7 8))
;USER(51): (random-puzzle-state  10)
;#2A((1 6 2) (4 0 5) (7 8 3))
;USER(52): (random-puzzle-state  24)
;#2A((0 1 2) (6 5 3) (8 7 4))



			  =================


Various clarifications:


THe number of nodes expanded is equal to the number of times "children
generation function" was called. The maximum memory is the highest size the
queue attained (the queue can, in principle, attain a large size sometime
in the middle of the search and then come down in size).


The cost of the goal-node is essentially its g-value (which is equal
to sum of the costs of actions taken to reach it). In the puzzle
problem, since the actions all have unit cost, it is also equal to
depth. In general, given actions with non-uniform costs, depth and
g-value may not be same.


Please note that you cannot check the equality of two arrays by just doing
equal on them. Even if their contents are the same, you will still get nil
from equal.

USER(65): j
#2A((1 2 3) (4 5 6) (7 8 0))
USER(66): (equal j (copy-puzzle-state j))
NIL

You have to write your own equality function--just as you had
copy-puzzle-state function--which individually compares all elements of the
states.




=========

SORT is a destructive operation--in that it changes the list passed to
it _in place_. If something else is pointing to a part of that list,
you can get into trouble. 

The way to deal with it is to make a copy of the list you are sorting
before passing it on to sort function. 

the function copy-list does it.

In otherwords, you can do (sort (copy-list children1) ....)
and you should be fine.

Rao=