Project #2
CSCE 625 (AI)
due Fri, Sep 28, 2012 (in class)

The overall goal of this assignment is to implement A* search to solve
a famous search problem: the "Blocksworld".  This problem involves
stacking blocks into a target configuration.  You are to write a
program to solve random instances of this problem using your own
implementation of A* search.  The focus of the project, however, is to
use your intuitions to develop a *heuristic* that will make solving
various instances of this problem efficient.  You may use any
programming language you like.

Description of the problem
--------------------------

This task involves stacking blocks.  The blocks are labeled by integers.
Here is an example random state and the goal state for a problem with
5 blocks on 3 stacks. (written side-ways so bottom of stack is on left) 

examples random state:
1 |  4
2 |  3  1
3 |  2  5

goal state:
1 |  1   2   3   4   5  
2 | 
3 | 

The state can be represented as list of lists, or an array.  However,
you should make your code flexible so that you can test it on different
numbers of blocks and stacks (as parameters).  The initial state can
be generated by just randomly assigning blocks to stacks.  The goal
state is always defined to have all the blocks in order on stack 1.
The operator in this problem can pick up only the top block on each
stack and move it to any other.

The objective of this project is to: 1) implement A* search, and 2)
develop and evaluate some heuristics.  This problem becomes harder as
the number of blocks scales up, and cannot be solved effectively with
BFS (though you can try it for small numbers of blocks).  You need a
A* and a heuristic to find solutions efficiently.  The default
heuristic (call it h0) can be taken to be the "number of blocks out of
place".  Your goal is to define a better heuristic(s) that will enable
your algorithm to find solutions faster (with fewer goal tests), and
to be able to solve larger problems (with more blocks).

As with project 1, you should turn in a table with some statistics
showing how your heurisics perform.  You should run direct
head-to-head comparisons of your heuristics on the same randomly 
generated problems.  You may set an upper-limit on the number
of goal tests for convenience - if you do so, be sure to report
the number of 'failures' with your statistics.

You should compare your heuristics with several different parameter
settings, which controls the difficulty of the problems.  For example,
start with 5 blocks and 3 stacks, then try 6 to 10 blocks to see how
scalable your performance is.  Then try expanding the number of stacks
from 3 to 7, to see if this makes the problem easier or harder.
See if you can solve "hard" problems, like with 10 blocks on 5 stacks,
as shown below (the solution has 18 steps):

1 |  4  
2 |  5   6   9   10 
3 |  2   7  
4 |  3   8  
5 |  1  

You must also write a short description of heuristic, a proof that
it is admissible (or at least an argument that it is approximately 
admissible), and a summary of your findings.

Note, you should implement the A* algorithm in the same was as
described in the textbook: as an iterative loop that uses a priority
queue.  I do not care about how you implement the priority queue.
Sevearl options are: 1) use a built-in data structure in your
language, 2) download and import/link a free library/module from the
Net, 3) implement a heap-based priority queue, or 4) simply place the
nodes in a list and sort it every time you do an insertion (slowest).
Any of these is fine with me; I don't want you to spend a lot of your
time on this aspect of the project, but rather focus on developing and
testing your heuristics.

What to turn in:
----------------

1) A short write-up with description of your heuristic, 
"proof" of admissibility, and summary of your findings.

2) A table of statistics (mean number of goal tests and solution depth
for each algorithm, averaged over at least 20 trials).  Note that
you should compare your algorithms with several different parameter
settings (number of blocks and stacks).

3) A printout of an example run.

You will have to schedule time to visit the TA to demo your program,
as part of your grade.

Example transcript
------------------
> python blocks.py 5 3 
initial state:
1 |  2  
2 |  3   5  
3 |  1   4  
iter=0, queue=0, f=g+h=5, depth=0
iter=1, queue=15, f=g+h=6, depth=1
iter=2, queue=27, f=g+h=6, depth=1
iter=3, queue=34, f=g+h=6, depth=1
iter=4, queue=41, f=g+h=6, depth=1
...
success! depth=10, total_goal_tests=2339, max_queue_size=644
1 |  2  
2 |  3   5  
3 |  1   4  

1 | 
2 |  3   5   2  
3 |  1   4  

1 | 
2 |  3   5   2   4  
3 |  1  

1 |  1  
2 |  3   5   2   4  
3 | 

1 |  1  
2 |  3   5   2  
3 |  4  

1 |  1   2  
2 |  3   5  
3 |  4  

1 |  1   2  
2 |  3  
3 |  4   5  

1 |  1   2   3  
2 | 
3 |  4   5  

1 |  1   2   3  
2 |  5  
3 |  4  

1 |  1   2   3   4  
2 |  5  
3 | 

1 |  1   2   3   4   5  
2 | 
3 |