Depth First Iterative Deepening Search

-------------------------------------
Description
-------------------------------------

The Depth First Iterative Deepening Search (DFIDS) was designed to
find the best leash length for the Depth First Search. According to
a draft paper written by D. Kopec and T.A. Marsland 
(http://www.cs.ualberta.ca/~tony/RecentPapers/Draft.5.2.pdf),
credit for this iterative search belong to Slate and Atkin (1977) who
used it in their chess program. Generally this search takes an initial
node (a list containing, level treatment and score)  at level zero and determines 
if the node score is greater than the goal which is the parent score. If
it is, the node is expanded, level is increased by one, and the node 
successors are tested. The function terminates when the best value is found. 
The result is then passed to back select.

------------------------------------
Pseudo-code
------------------------------------
Procedure DFID

Input:  Type of software engineering model (AG, AG2, PB, HY)
	
Output: Best found treatment and score

Set treatment to empty
Get the score of an empty treatment

while (level < 6 and triedSinceBest < 100)
      Create listOfTrials containing lists of treatments, 
      bestScore so far and a list of parameters that can be played with

      while (listOfTrials is not empty and triedSinceBest < 100)
      	    take the first treatment from listOfTrials and find its score

	    	 if (score > bestScore)
                    Set the bestScore to score
		    Set the bestTreatment to treatment
		    Set triedSinceBest to 0
							
		if the score of a treatment is greater than the score for the parent,
		and its level is not the same as its current, then the treatment is 
     		expanded with successor nodes.

		These successors are pushed onto the listOfTrials and the process is
     	   	repeated with a successor as the new first treatment. 

level++

Perform a back select on the best treatment

-----------------------------------
DFIDs is repeated depth first search at different levels.
According to the pom2 model there are 6 variable ranges which
can be randomized, 'DYNAMISIM 'CRITICALITY 'CULTURE 'TEAMSIZE 'SIZE 'TEAM-ALPHA 
so our last level value will be 6.

The initial score is set to zero, this represents the current max score.
The first treatment starts out empty. The score from this is applied the 
successor nodes of that parent (the node with the empty treatment). 
The successor node treatment gets a score when sent into the model. If 
the score is greater than the parent score then, this score replaces the 
current max/bestCurrentVal.

The successor nodes who are greater are considered for expansion and the 
process repeats until level 6 is reached or the number of tries since
the last best value reaches 100.

-------------------------------------
Actual Code
-------------------------------------
(defun dfid (type)
  (let ((parameters (list 'DYNAMISIM 'CRITICALITY 'CULTURE 'TEAMSIZE 'SIZE 'TEAM-ALPHA))
        (valuesOfEach 10)
        (listOfTrials (list))
        (triedSinceBest 0)
        (level 0)
        (bestTreatment (list))
        (bestScore 0))
    (while (and (< level 6) (< triedSinceBest 100))
      (push (list (list) 0 bestScore (copy-list parameters)) listOfTrials)
      (while (and (not (null listOfTrials)) (< triedSinceBest 100))
        (let* ((treatment (pop listOfTrials))
               (score (runpom2 type (first treatment))))
          
          (if (> score bestScore)
              (progn
                (setf bestScore score
                      bestTreatment (first treatment)
                      triedSinceBest 0)))
          
          (if (> score (third treatment)) 
              (if (not (= (second treatment) level))
                  (progn
                    (dotimes (x valuesOfEach)
                      (dolist (parameter (fourth treatment))
                        (push (list 
                               (append 
                                (list (list parameter (our-sample parameter))) 
                                (first treatment))
                               (1+ (second treatment))
                               score
                               (remove-if #'(lambda (x) (equal x parameter)) 
                                          (copy-list (fourth treatment))))
                              listOfTrials))))))))
      (incf level))
      (backselect bestTreatment type)))

-------------------------------------
Policy Commitment
-------------------------------------

1. Ranges are added to the treatement one at a time. At
   each level.

2. DFID does not need to reset and start again.

4. Because of its completeness this algorithm is Deterministic.

7. Early termination criteria: if after 100 tries the best score
   cannot be beaten, then termination occurs and the best score is returned