CSW 4701- Artificial Intelligence
                            Search Programs in LISP

(Comment
Here we detail the bidirectional search procedure for state spaces that
are trees:

(loop
(print "Please tell me the starting position:")
(setf state (read))
(setf SI (list state nil))
(print "Please tell me the goal state you wish to find:")
(setf goal (read))
(setf SQ goal)
(bidirect SI SQ 'successor-function-forward 'successor-function-backward )

(comment Ok, now the implementation code follows.)

(defun bidirect (si sg succsf succsb)
 (let ( ( openf   (list  (list si nil nil) ) ) ;note the inner list is a node
        ( openb   (list  (list sg nil nil) ) ) ;note the inner list is a node
          ;note for trees, we don't need a closed list
        ( nf      nil )
        ( nb      nil )
        ( daughtersf nil )
        ( daughtersb nil )
        ( jointpath nil  ))
 (loop
 (cond
  ((or (null openf) (null openb))  ;Have we exhausted the search space?
   (print "Sorry, the problem posed is insoluable")
   (return nil)))

 (setf nf (pop openf))  ;Ok, remove the first node and update open 
                        ;we don't need a closed list for trees

 (cond
  ((setf jointpath (member (state nf)  openb )  )
                   ;have we found our node in the backward frontier?
    (print "Great. I found a solution. Here it is:")
    (return (success jointpath)) ))

 (setf daughtersf (apply succsf nf)) ;here we generate new derived states

 (setf openf (append openf daughtersf)) ;open is used as a QUEUE, thus its bfs.

 (setf nb (pop openb))  ;Ok, remove the first node and update open  

 (cond
  ((setf jointpath (member (state nb) openf )  )
                   ;have we found our state in the forward fronteir?
    (print "Great. I found a solution. Here it is:")
    (return (success jointpath)) ))

 (setf daughtersb (apply succsb nb)) ;here we generate new derived states

 (setf openb (append openb daughtersb)) ;open is used as a QUEUE, thus its bfs.

  ) ;closes loop
  ) ;closes let
  ) ;closes defun


)  ;closes main loop