;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;                                                                    ;;;
;;;  File:   alpha-beta.scm                                            ;;;
;;;  Author: Dave Reed                                                 ;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;;;  The following functions implement an alpha-beta search.  It may be used
;;;  in conjunction with the code in the file connect.scm, which plays the
;;;  game Connect-4. "alpha-beta-search" is the top-level search
;;;  function, with two inputs: the number of levels to search and the
;;;  static-evaluator to be used.  It returns an instance of the "alpha-beta"
;;;  function which does the alpha-beta search.  For example, the call
;;;    (alpha-beta-search 4 dumb-eval) will return an instance of the
;;;  "alpha-beta" function where the lookahead is 4 moves and the sample
;;;  static evaluator "dumb-evalt" is used.


(define HEURISTIC-LIMIT 10000)

(define (alpha-beta-search level static-eval)
  
  (define (alpha-beta player board achievable cutoff level static-eval)
    (define (alpha-beta-help moves achievable cutoff best-pair)
      (if (null? moves) 
          best-pair
          (let ((new-board (make-move (car moves) player board)))
            (let ((val (- 0 (cadr (alpha-beta (opponent player)
                                              new-board
                                              (- 0 cutoff)
                                              (- 0 achievable)
                                              (- level 1) static-eval)))))
              (if (or (equal? best-pair '(-1 0)) (> val achievable))
                  (if (>= val cutoff) 
                      (list (car moves) val)
                      (alpha-beta-help (cdr moves) val
                                       cutoff (list (car moves) val)))
                  (alpha-beta-help (cdr moves) achievable cutoff best-pair))))))
    
    (if (or (zero? level) (draw? board) (winner? player board) (winner? (opponent player) board)) 
        (list -1 (static-eval board player))
        (alpha-beta-help (get-moves board) achievable cutoff '(-1 0))))
  
  (lambda (player board)
    (car (alpha-beta player board 
                     (- 0 HEURISTIC-LIMIT) HEURISTIC-LIMIT level static-eval))))