(defun make-board ()
  "Resets the values of the board to empty"
  (setf *main-board* (list 1 2 3 4 5 6 7 8 9))) 
 
(defun random-member (lst) 
  "Returns a random member of a given list." 
  (elt lst (random (list-length lst)))) 
 
(defun print-board (board) 
  (format t "~5% ~& ~a  ~a  ~a " 
            (elt board 6)
            (elt board 7) 
            (elt board 8)) 
  (format t " ~& ~a  ~a  ~a " 
            (elt board 3) 
            (elt board 4) 
            (elt board 5)) 
  (format t "~& ~a  ~a  ~a "  
            (elt board 0) 
            (elt board 1) 
            (elt board 2)) 
  (format t "~3% 0: New game~5%")) 
 
(defun filter-legals (board) 
  (mapcan #'(lambda (element) 
      (and (numberp element) (list element))) board)) 
 
(defun make-move (move board) 
  (let ((token (if (oddp (list-length (filter-legals board))) 
                   'x 'o))) ; Sets the right token to be placed 
    (setf (elt board move) token))) ; Places it in the indicated spot 
 
(defun win-check (board) 
  (dolist (combination '((6 7 8)    ; 
                         (3 4 5)    ; 
                         (0 1 2)    ; 
                         (0 3 6)    ;  All combinations 
                         (1 4 7)    ;  in which any player 
                         (2 5 8)    ;  has won. 
                         (0 4 8)    ; 
                         (2 4 6)))  ; 
    (let ((test-list ; Replaces the combinations by real-board values. 
          (mapcar #'(lambda (element) 
              (elt board element)) combination))) 
      (when (and (eql (elt test-list 0)     ; 
                      (elt test-list 1))    ; Compares the board to 
                 (eql (elt test-list 0)     ; the possible win list. 
                      (elt test-list 2)))   ;  
       (return-from win-check t)))) 
    nil) 
 
(defun ai-win-p (board) 
  "Detects whether the AI can win the game, and returns a move that does it" 
  (dolist (move (filter-legals board)) 
    (let ((iterate-board (copy-list board))) 
      (make-move move iterate-board) 
      (when (win-check iterate-board) 
        (return-from ai-win-p (list move))))) 
  nil) 
 
(defun human-prediction (board) 
  "Returns nil if human can win, t if tie or AI win. if unknown, recurses back to ai-prediction" 
  (cond 
    ((ai-win-p board) 
      (return-from human-prediction nil)) 
    ((= (list-length (filter-legals board)) 1) 
      t) 
    (t  
      (dolist (move (filter-legals board)) 
        (let ((think-board (copy-list board))) 
          (make-move move think-board) 
          (if (ai-prediction think-board) 
              t 
              (return-from human-prediction nil)))))) 
  t) 
 
(defun ai-prediction (board) 
  "Calls the human-prediction predicate to filter unacceptable moves, or returns a list of playable moves." 
  (cond 
    ((= (list-length (filter-legals board)) 1)  ; If there's only one legal move, 
      (filter-legals board))                    ;   returns it in a list. 
    ((ai-win-p board)                           ; If the AI can win now,  
      (ai-win-p board))                         ;   returns it in a list. 
    (t 
      (let ((acceptable-moves '())) 
        (dolist (move (filter-legals board) acceptable-moves) 
          (let ((think-board (copy-list board))) 
            (make-move move think-board) 
            (when (human-prediction think-board) 
              (push move acceptable-moves))))))))   

(defun brains () 
  "Executes a move on behalf of the AI" 
  (let ((think-board 
        (mapcar #'(lambda (element) 
            (if (numberp element) 
                (1- element) 
                element)) *main-board*))) 
    (if (ai-prediction think-board) 
        (make-move (random-member (ai-prediction think-board)) 
                    *main-board*) 
        (make-move (random-member (filter-legals think-board)) 
                    *main-board*)))) 

(defun play-game () 
  "Main game function, infinite loop broken at end of a game" 
  (loop 
    (print-board *main-board*) 
    (let ((user-input (read))) ; Asks user for input. Explores the possibilities. 
      (cond 
        ((eql user-input 0)            ; Player picks the New Game option, 
          (return-from play-game nil)) ; exists game loop 
        ((member user-input (filter-legals *main-board*)) 
          (make-move (1- user-input) *main-board*) ; Human enters a valid legal move 
          (when (win-check *main-board*)  ; Checks if the game is won 
            (print-board *main-board*) 
            (if (y-or-n-p "~& You won. New game?") 
                (return-from play-game nil) 
                (exit))) 
          (when ; Checks for a tie 
            (zerop (list-length (filter-legals *main-board*))) 
            (print-board *main-board*) 
            (if (y-or-n-p "~& It's a tie. New game?") 
                (return-from play-game nil) 
                (exit))) 
          (brains) 
          (when (win-check *main-board*) ; Checks for an AI win 
            (print-board *main-board*) 
            (if (y-or-n-p "~& You lost. New game?") 
                (return-from play-game nil) 
                (exit))) 
          (when ; Checks for a tie 
            (zerop (list-length (filter-legals *main-board*))) 
            (print-board *main-board*) 
            (if (y-or-n-p "~& It's a tie. New game?") 
                (return-from play-game nil) 
                (exit)))) 
        (t (format t "~&Invalid input, try again.~%")))) 
      (when (listen)      ; If *standard-input* has content left, 
        (clear-input))))  ; removes 'em. 
 
(defun main-loop () 
  "Init function of the game, infinite loop covering game startup" 
  (loop 
    (make-board) 
    (when (zerop (random 2)) ; With a 50% chance, 
       (brains)) 
    (play-game)))   

(main-loop)