;---------------------------------------------------------------------------------------------------
; David (Tom) Harper
;---------------------------------------------------------------------------------------------------

; i need a while loop
(defmacro while (test &rest body)
`(do ()
((not ,test))
,@body)
)

; returns a new board position. this could overwrite a previous position if no validation happens.
(defun domove (board player move)
	(let ((tempboard (copy-list board))) (setf (nth move tempboard) player) tempboard)
)

; generates all legal moves a player could make.
(defun getnextmoves (board player)
	(mapcan 
		#'(lambda (n) 
			(if (null (nth n board)) (list (domove board player n)) nil)
		)
		'(0 1 2 3 4 5 6 7 8) ; all possible board values
	)
)

; returns t is board is a winning position for player, nil otherwise- it's not pretty, but 
; this seems to be the most efficient way to do this
(defun iswin (board player)
  (or (and (eq (first board) player) (eq (second board) player) (eq (third board) player))
      (and (eq (fourth board) player) (eq (fifth board) player) (eq (sixth board) player))
      (and (eq (seventh board) player) (eq (eighth board) player) (eq (ninth board) player))
      (and (eq (first board) player) (eq (fourth board) player) (eq (seventh board) player))
      (and (eq (second board) player) (eq (fifth board) player) (eq (eighth board) player))
      (and (eq (third board) player) (eq (sixth board) player) (eq (ninth board) player))
      (and (eq (first board) player) (eq (fifth board) player) (eq (ninth board) player))
      (and (eq (third board) player) (eq (fifth board) player) (eq (seventh board) player))
  )
)

; returns t if board is a draw position
(defun isdraw (board)
	(not (member nil board))
)

; returns 'x when given 'o, and vice-versa.
(defun getopponent (player)
	(if (eq player 'x) 'o 'x)
)

; The following heuristic function works pretty well- if you want the computer
; to play worse change this!
(defun heuristic (board player)
	(cond 
		( (iswin board player) 
			(+ 3 (/ 3 (length (remove nil board))))
		)
		( (iswin board (getopponent player)) 
			(- (+ 3 (/ 3 (length (remove nil board)))))
		)
		(t 0)
	)
)

;  prints a two-dimensional representation of the board.
(defun showboard (b)
	(format t "~% ~d | ~d | ~d~% ---------~% ~d | ~d | ~d~% ---------~% ~d | ~d | ~d~%~%"
		(or (first b) "1") (or (second b) "2") (or (third b) "3")
		(or (fourth b) "4") (or (fifth b) "5") (or (sixth b) "6")
		(or (seventh b) "7") (or (eighth b) "8") (or (ninth b) "9")
	)
)

; ab performs minimax search with alpha-beta pruning. Returns
; a list of board positions representing what it sees as the best moves for 
; both players.  The first element of the list is the value of the board 
; position after the proposed move.

(defun run_ab(board depth player)
	(ab board depth player 99 -99)
)

(defun ab (board depth player alpha beta)
  (cond 
    ( (or (iswin board 'x) (iswin board 'o) (isdraw board)) (list (heuristic board player) nil)  )
    (t  
      (let 
        ((nextmoves (getnextmoves board player)) (best-choice nil))
        (cond 

; we want to return something rational if nextmoves is empty
          ((null nextmoves) (list (heuristic board player) nil)) 

; start into ab
          (t
            (do 
; knock one item off the list
              ((movesminus1 nextmoves (cdr movesminus1)) (quit nil))

; bail if no mor items left
              ((or quit (null movesminus1)))
              (let* 
                (
; grab next test move off stack
                  (testmove (car movesminus1))

; do the ab search recursively - one mans alpha is another's beta
                  (search-result (ab testmove (1+ depth) (getopponent player) (- beta) (- alpha)))

; a new heuristic value bubbles up- first element is the winner
                  (heuristic-value (- (car search-result)))

                )
; basically, if this happens we have a new best choice and beta
                (when (> heuristic-value beta)
                  (setq beta heuristic-value)
                  (setq best-choice (cons testmove (cadr search-result)))
                )
; if this happens we prune the tree- beta is larger than alpha (or vice versa, depending on pov)
                (when (>= beta alpha) 
                  (setq quit t)
                )
              )
            )
; best choice is the new beta, right?
            (list beta best-choice)
          )
        )
      )
    )
  )
)

; run the game here
(defun ttt ()
  (let ((board (list nil nil nil nil nil nil nil nil nil) ) )

; loop until someone wins or loses
    (do ()

; if someone won, do something
	((or (iswin board 'x) (iswin board 'o) (isdraw board))
		(showboard board)
		(when (iswin board 'o) (format t "You lost.~%"))
		(when (iswin board 'x) (format t "You won.~%"))
		(when (isdraw board)  (format t "Draw.~%"))
	)

; otherwise, keep going
	(showboard board)
	(format t "Enter move (1-9): ")

; this part gets input and validates that it is a number and an ok number
	(setq myinput 9)
	(while (or (< myinput 0) (> myinput 8) )
		(setq myinput (read) )
		(if (not (numberp myinput)) (setq myinput 10) )
		(setq myinput (- myinput 1) )
		(if (not (null (nth myinput board))) (setq myinput 9) )
	)
; input ok- do move
	(setq board (domove board 'x myinput))

; computer does its move if it can
	(when (and (not (isdraw board)) (not (iswin board 'x)) ) 
		(showboard board)
		(let ((choice (run_ab board 0 'o)))
			(setq board (car (cadr choice)))
			(format t "My move: ~%")
		)
	)
    )
  )
)