PROJECT TWO: comparison of alternative search algorithms
(using The 15 Puzzle)


Here is your FIRST Problem-Solving assignment. Its is due a 
little more than two weeks from  today.

I hope you find this not only straightforward, but quite
a bit of fun as well! But yes there is a bit of grunt work to do
in setting up your experimental facility:


The intent of this assignment is to help demonstrate to 
you the expense of the various search algorithms we've been
discussing, and the benefits that KNOWLEDGE accrues when
solving problems.  We started with BFS and DFS, which are
called "WEAK" methods, since they search without much problem
specific knowledge available to them. We discussed Uniform Cost
Search that added a cost model to our search to allow
us to seek minimal cost solutions.  Shortly we'll add heuristic
knowledge to our problem-solver in developing the A* algorithm.
Each additional bit of knowledge and structure should improve
performance, i.e. searching should take less time (fewer
states generated and explored) in computing solutions.

So, this is your assignment:

1-Fully implement the BFS and DFS search algorithms.


2-Fully implement the Uniform Cost Search Algorithm by modifying
that code (simply copy the code of the search alg. and modify
it accordingly, including the definition of a node. 

3-Fully implement the Iterative Deepening DFS algorithm.

At this point, you should have 4 search algorithms coded and
ready to be used, but first, we'll add yet another SMARTER algorithm.

4-Fully implement the Greedy and A* algorithms (which will be discussed in 
class with you next week, in plenty of time to complete the project.) 
Do this by modifying the uniform cost search code by adding additional 
info to a node, another access function, and a call in the appropriate 
place to a heuristic evaluation function. 


5-INSTRUMENT each of the 6 algorithms you've coded to produce 
basic statistics:  
 a)the number of nodes generated 
 b)the number of nodes containing states that were generated previously
 c)the number of nodes on the OPEN list when termination occurs
 d)the number of nodes on the CLOSED list (if there is one) when 
termination occurs

  
6-Fully implement the 15 PUZZLE (its the 4 by 4 version of the
  8 PUZZLE, with tiles numbered from 1 to 15, rather than 1 to 8).
  The same operators defined for the 8 PUZZLE should work, but of
  course the state representation must change.  The "success"
  function should be written to allow an optional flag to control
  whether or not a solution is printed, or the statistics gathered
  in 4, or both. (Ughhh, more grunt work.)

7-Now, here is the fun part.  You must also define TWO Heuristic
evaluation functions, one based upon the function described in 
class on the 8 Puzzle, and another function OF YOUR OWN CHOICE.
These Heuristic Evaluation functions are to be used by the
A* and Greedy algorithms previously implemented in step 4.

8-Finally, run all of the above on at least three test cases:
  a)a hard 15 puzzle (meaning a starting position that requires
    at least 15 moves)  
  b)a moderately hard puzzle (meaning a starting
    position with at least 8 moves) and 
  c) a trivial puzzle (meaning a starting position with at least 3 moves).

This means that starting with each of the three puzzles, you
should run 
 a)BFS and generate solutions and statistics
 b)DFS and likewise generate solutions and statistics, taking
   care to run this one repeatedly for different depth bounds
 c)Likewise with iterative deepening
 d)Likewise with Uniform Cost Search with the cost function defined as simply
   ONE and generate solutions and statistics
 f)Greedy and A* with inclass heuristic function and generate solutions and statistics
 g)Greedy and A* with your very own heuristic function generate solutions and statistics


WE WILL BE SENDING  TEST PUZZLES FOR YOU TWO DAYS BEFORE IT IS DUE!  


And that's all folks!  


sal


SOME MORE FOOD FOR THOUGHT:

You might find it very interesting to run your test cases for
each of the algorithms under different ORDERINGS of the operators!
This means, that running BFS and DFS multiple times for the same
starting state but with different orderings of operators (i.e.
the successor function implements North/East/South/West, then 
North/South/East/West, then North/West/East/South, and so forth)
will likely produce different results! Hmmmmm.....

Will alternative orderings make a difference in Uniform Cost
Search? Greedy?  A*?  In BFS? In DFS?

Interesting question, isn't it?