;;;; Game Search Engines
;;;;
;;;; File:         game-search.lsp
;;;; Author:       <your name> (<your e-mail address>)
;;;; Version:      2

;; Abstract interface to state-oriented search.
;;
;;	state ::= s-expression
;;
;;	move ::= s-expression
;;
;; (state-value 'state) ===> <numeric value of state>
;;			      if state has a direct
;;				             value
;;			===> nil otherwise
;;
;; (state-legal-moves 'state)
;;     ===> '<list of moves that can be made from
;;	      the state>
;;
;; (state-next 'state 'move)
;;     ===> '<result state of making the move when in
;;            the given state>
;;
;; (state-next-player 'state) ===> 'max	if max is the
;;				    next player to move
;;				    from the state.
;;			      ===> 'min	if min is next.
;; (state-print 'state) prints state nicely formatted.
;;
;; *state-max-value*	Winning values for the
;; *state-min-value*	players max and min.
;;
;; The STATE-VALUE, STATE-LEGAL-MOVES, STATE-NEXT,
;; STATE-NEXT-PLAYER, and STATE-PRINT functions and
;; the *STATE-MAX-VALUE* and *STATE-MIN-VALUE* global
;; variables define the state abstraction.  These are
;; part of the environment, and are not passed as
;; arguments.  Notice that they all have names beginning
;; in `STATE-', which is COMMONLISP's way of naming the
;; parts of a `STATE object abstraction'.



;; Variables to gather statistics and traces for game
;; searches.
;;
(defvar *trace* nil)	   ; True to trace.
(defvar *visits*)	   ; Number of state visits
			   ; while computing one move.
(defvar *limit* 100)	   ; Limit on number of state
			   ; visits while computing
			   ; one move.

;; Functions to gather statistics and trace game
;; searches.

;; Increment *VISITS* and call ERROR if it goes over the
;; *LIMIT*.
;;
(defun increment-visits ()
  (setf *visits* (+ *visits* 1))

  (cond
   ((> *visits* *limit*)
    (error "exceeded limit on state visits per move"))))

;; This function takes the STATE argument and the
;; RESULT of FIND-VALUE-AND-MOVES below and outputs
;; a trace if *TRACE* is true.  The RESULT is
;; returned, so this function can be used to return
;; the final result from FIND-VALUE-AND-MOVES.
;;
(defun return-value-and-moves
	  (state value-and-moves)
  (cond
   (*trace*
    (fresh-line)
    (cond
     ((null (cdr value-and-moves))
      (princ '|Direct value |)
      (princ (car value-and-moves)))
     (t
      (princ '|Value |)
      (princ (car value-and-moves))
      (princ '| on move |)
      (princ (cadr value-and-moves))))
    (princ '| at state: |)
    (state-print state)
    (fresh-line)))
  value-and-moves)


;; Find the best value for a STATE, using the BETTER
;; function to determine which value is best.  Value
;; v1 is better than v2 if and only if
;;
;;		(funcall BETTER v1 v2)
;;
;; is true.  (BETTER is typically either #'> or #'<).
;;
;; If STATE has a direct value, this is its value.
;; Note that if there are no legal moves from STATE,
;; then STATE will have a direct value.
;;
;; Otherwise all legal moves from STATE are tried,
;; and the value for the state attained by each move is
;; found.  The best value found is returned.
;;
;; In addition to the BETTER function, a WORSE function
;; is also given as an argument.  The function calls:
;;
;;		(funcall WORSE  v2 v1)
;;		(funcall BETTER v1 v2)
;;
;; give the same results: WORSE returns the same results
;; as BETTER with its arguments reverse.  Both WORSE and
;; BETTER are given so they can be exchanged when
;; changing from MIN to MAX and vice versa in the mini-
;; max algorithm.
;;
;; When finding the value for the state attained by a
;; move, this function calls itself with WORSE and
;; BETTER exchanged, so the value of the attained state
;; is the value for the other player.

;; This function returns both a value and the list of
;; moves that lead to that value, in the form:
;;
;;	( value . list-of-moves )
;;
;; If STATE has a direct value, NIL is returned as the
;; list of moves.  Note that the first move in the list
;; is the move from STATE.
;;
;; The aguments WORST and BEST are also given so that
;; the optimization known as alpha-beta pruning may be
;; used.  These arguments mean that the caller does not
;; care to distinguish between WORST and values worse
;; than WORST, or BEST and values better than BEST.
;; Thus if a move leads to a value at least as good as
;; BEST, no more moves need to be tried.  Similarly if
;; a move leads to a value better than WORST, then that
;; value can replace WORST when evaluating subsequent
;; moves.
;;
;; This function increments *VISITS* and calls ERROR if
;; that is then over the *LIMIT*.  It is up to the
;; caller of this function to zero *VISITS*.
;;
;; If *TRACE* is true, this function prints out the
;; numeric value it returns, the first move of the
;; move list if any, and the state being evaluated.
;;
;; RR: <give your rewrite rules here>
;;
(defun find-value-and-moves (state
			     worse better
			     worst best)

  (increment-visits)

  ;; Replace this line and the next with your code.
  (return-value-and-moves state '(0)))

;; The following function handles recursion through
;; the list of legal moves from STATE for the
;; FIND-VALUE-AND-MOVES function.  It takes the same
;; arguments as FIND-VALUE-AND-MOVES, plus two
;; recursion arguments.
;;
;; Iteration variables:
;;
;;	result		If non-NIL, the best result
;;			for all the legal moves from
;;			state tried so far.  If NIL,
;;			no moves have yet been tried.
;;
;;	moves		The list of legal moves from
;;			state that have not yet been
;;			tried.
;;

;; RR: (find-value-and-moves-recurse
;;       'state #'worse #'better worst best
;;	 'result nil) ===> ???
;;
;;     (find-value-and-moves-recurse
;;       'state #'worse #'better worst best
;;	 'result '(move . more-moves))
;;	   ===> ???
;;		    if ???
;;
;;	   ===> ???
;;
;;		    otherwise
;;
;;	   where
;;
;;	   (find-value-and-moves
;;	    (state-next 'state 'move)
;;	    #'better #'worse best worst)
;;		====> '(new-value . new-moves)
;;	   (best-value-of #'better v1 v2)
;;	       ===> v1 if (funcall #'better v1 v2)
;;	       ===> v2 otherwise
;;	   (best-result-of #'better '(v1 . m1) nil)
;;	       ===> '(v1 . m1)
;;	   (best-result-of #'better '(v1 . m1)
;;			            '(v2 . m2))
;;	       ===> '(v1 . m1) if (funcall #'better
;;					   v1 v2)
;;	       ===> '(v2 . m2) otherwise
;;
;; worst, best, new-value, v1, v2 are numbers

(defun find-value-and-moves-recurse (state
				     worse better
				     worst best
				     result
				     moves)

  ;; Replace this line and the next with your code.
  '(0))

;; Play a game starting at a given state.
;;
;; Returns a list of all the moves made preceeded by the
;; outcome of the game, which is 'MAX-WINS, 'MIN-WINS,
;; or 'DRAW.
;;
;; After this function is called, the global variable
;; *VISITS* holds the number of states visited while
;; the game was being played.
;;
(defun play-game (state)
  (setf *visits* 0)
  (let* ((value-and-moves
	  (cond
	   ((eql (state-next-player state) 'max)
	    (find-value-and-moves state #'< #'>
				  *state-min-value*
				  *state-max-value*))
	   (t
	    (find-value-and-moves state #'> #'<
				  *state-max-value*
				  *state-min-value*))))
	 (value (car value-and-moves))
	 (moves (cdr value-and-moves)))
   (cond
    ((<= value *state-min-value*)
     (cons 'min-wins moves))
    ((>= value *state-max-value*)
     (cons 'max-wins moves))
    (t
     (cons 'draw moves)))))