Quantcast

Maximum PC

It is currently Wed Oct 22, 2014 5:50 am

All times are UTC - 8 hours




Post new topic Reply to topic  [ 1 post ] 
Author Message
 Post subject: Tic-Tac-Toe in LISP
PostPosted: Tue Apr 01, 2008 7:46 pm 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11605
So, our final project (before the term project) was to create Tic-Tac-Toe in lisp. I attempted to use Alpha-Beta pruning, but something wasn't quite right somewhere in my code. The project was due on Monday, so here is my code. Somebody think they can fix it?

Minimax with Alpha-Beta pruning anyone? I do admit that it could be "cleaner" but I was trying so hard to get it complete, that I started brute forcing a lot of stuff, so this code is far from elegant. My apologies in advance.

Code:
;; Global Variables
(defvar CurrentPlayer    nil)
(defvar PossibleMoves    nil)
(defvar TempMoveList   nil)
(defvar GameBoard       (make-array 9))
(defvar TempBoard      (make-array 9))

;; Clear the board spaces, and ensure they are all set to "-"
(defun initBoard ()
   (setq i 0)
   (dotimes (i 9)
      (setf (aref GameBoard i) '-)
      (setf (aref TempBoard i) '-)
   )
)

;; Swap the current player, used for searching
(defun SwapPlayer ()
   (if (eql CurrentPlayer 'X)
      (setf CurrentPlayer 'O)
      (setf CurrentPlayer 'X)
   )
)

;; Set up both the PossibleMoves and TempMoves list variables to contain 1-9 at start of game
(defun initPossibleMoves ()
   (setq PossibleMoves '(1 2 3 4 5 6 7 8 9))
   (setq TempMoveList PossibleMoves)
)

;; Updates the main gameboard with the current player and their move
(defun UpdateBoard (player position)
   (setf (aref GameBoard position) player)
)

;; Updates the temp board, used for searching
(defun UpdateTempBoard (player position)
   (setf (aref TempBoard position) player)
)

;; Play a game of Tic-Tac-Toe, called from the tictactoe funciton
(defun PlayGame ()
   ;; Initialize the board, and set the list of possible moves to be inclusive of all of the spaces
   (initBoard)
   (initPossibleMoves)
   
   ;; Loop for each turn, check for a draw in between each turn, as there will be an odd number of actual moves
   ;; and an even number of moves per turn, a draw will occur mid turn.
   ;; Only check for that player to win after their move, X cannot win on Os move, etc.
   (loop
      (Xmove)
      (if (eql (CheckXWin) T)
         (progn (print "X Wins!")(return nil))
      )
      
      (if (eql (CheckDraw) T)
         (progn (print "The game is drawn")(return nil))
      )
      
      (Omove)
      (if (eql (CheckOWin) T)
         (progn (print "O Wins!")(return nil))
      )
   )
)

;; If there are no possilbe moves left, this is a draw. The fucntions postfixed with a T
;;  checks the temporary board/move list.
(defun CheckDrawT ()
   (if (equal (length TempMoveList) 0)
      (return-from CheckDrawT T)
      (return-from CheckDrawT nil)
   )
)

;; Checks for X win during alpha-beta searching
(defun CheckXWinT ()
   (cond
      ((and (eql (aref TempBoard 0) 'X) (eql (aref TempBoard 1) 'X) (eql (aref TempBoard 2) 'X)) (return-from CheckXWinT T))
      ((and (eql (aref TempBoard 0) 'X) (eql (aref TempBoard 3) 'X) (eql (aref TempBoard 6) 'X)) (return-from CheckXWinT T))
      ((and (eql (aref TempBoard 0) 'X) (eql (aref TempBoard 4) 'X) (eql (aref TempBoard 8) 'X)) (return-from CheckXWinT T))
      ((and (eql (aref TempBoard 1) 'X) (eql (aref TempBoard 4) 'X) (eql (aref TempBoard 7) 'X)) (return-from CheckXWinT T))
      ((and (eql (aref TempBoard 2) 'X) (eql (aref TempBoard 5) 'X) (eql (aref TempBoard 8) 'X)) (return-from CheckXWinT T))
      ((and (eql (aref TempBoard 3) 'X) (eql (aref TempBoard 4) 'X) (eql (aref TempBoard 5) 'X)) (return-from CheckXWinT T))
      ((and (eql (aref TempBoard 6) 'X) (eql (aref TempBoard 7) 'X) (eql (aref TempBoard 8) 'X)) (return-from CheckXWinT T))
      ((and (eql (aref TempBoard 2) 'X) (eql (aref TempBoard 4) 'X) (eql (aref TempBoard 6) 'X)) (return-from CheckXWinT T))
      (nil)
   )
)

;; Checks for an O win during the alpha-beta search
(defun CheckOWinT ()
   (cond
      ((and (eql (aref TempBoard 0) 'O) (eql (aref TempBoard 1) 'O) (eql (aref TempBoard 2) 'O)) (return-from CheckOWinT T))
      ((and (eql (aref TempBoard 0) 'O) (eql (aref TempBoard 3) 'O) (eql (aref TempBoard 6) 'O)) (return-from CheckOWinT T))
      ((and (eql (aref TempBoard 0) 'O) (eql (aref TempBoard 4) 'O) (eql (aref TempBoard 8) 'O)) (return-from CheckOWinT T))
      ((and (eql (aref TempBoard 1) 'O) (eql (aref TempBoard 4) 'O) (eql (aref TempBoard 7) 'O)) (return-from CheckOWinT T))
      ((and (eql (aref TempBoard 2) 'O) (eql (aref TempBoard 5) 'O) (eql (aref TempBoard 8) 'O)) (return-from CheckOWinT T))
      ((and (eql (aref TempBoard 3) 'O) (eql (aref TempBoard 4) 'O) (eql (aref TempBoard 5) 'O)) (return-from CheckOWinT T))
      ((and (eql (aref TempBoard 6) 'O) (eql (aref TempBoard 7) 'O) (eql (aref TempBoard 8) 'O)) (return-from CheckOWinT T))
      ((and (eql (aref TempBoard 2) 'O) (eql (aref TempBoard 4) 'O) (eql (aref TempBoard 6) 'O)) (return-from CheckOWinT T))
      (nil)
   )
)

;; The follow three functions check for actual win or draw conditions during gameplay.
(defun CheckDraw ()
   (if (equal (length PossibleMoves) 0)
      (return-from CheckDraw T)
      (return-from CheckDraw nil)
   )
)

(defun CheckXWin ()
   (cond
      ((and (eql (aref GameBoard 0) 'X) (eql (aref GameBoard 1) 'X) (eql (aref GameBoard 2) 'X)) (return-from CheckXWin T))
      ((and (eql (aref GameBoard 0) 'X) (eql (aref GameBoard 3) 'X) (eql (aref GameBoard 6) 'X)) (return-from CheckXWin T))
      ((and (eql (aref GameBoard 0) 'X) (eql (aref GameBoard 4) 'X) (eql (aref GameBoard 8) 'X)) (return-from CheckXWin T))
      ((and (eql (aref GameBoard 1) 'X) (eql (aref GameBoard 4) 'X) (eql (aref GameBoard 7) 'X)) (return-from CheckXWin T))
      ((and (eql (aref GameBoard 2) 'X) (eql (aref GameBoard 5) 'X) (eql (aref GameBoard 8) 'X)) (return-from CheckXWin T))
      ((and (eql (aref GameBoard 3) 'X) (eql (aref GameBoard 4) 'X) (eql (aref GameBoard 5) 'X)) (return-from CheckXWin T))
      ((and (eql (aref GameBoard 6) 'X) (eql (aref GameBoard 7) 'X) (eql (aref GameBoard 8) 'X)) (return-from CheckXWin T))
      ((and (eql (aref GameBoard 2) 'X) (eql (aref GameBoard 4) 'X) (eql (aref GameBoard 6) 'X)) (return-from CheckXWin T))
      (nil)
   )
)

(defun CheckOWin ()
   (cond
      ((and (eql (aref GameBoard 0) 'O) (eql (aref GameBoard 1) 'O) (eql (aref GameBoard 2) 'O)) (return-from CheckOWin T))
      ((and (eql (aref GameBoard 0) 'O) (eql (aref GameBoard 3) 'O) (eql (aref GameBoard 6) 'O)) (return-from CheckOWin T))
      ((and (eql (aref GameBoard 0) 'O) (eql (aref GameBoard 4) 'O) (eql (aref GameBoard 8) 'O)) (return-from CheckOWin T))
      ((and (eql (aref GameBoard 1) 'O) (eql (aref GameBoard 4) 'O) (eql (aref GameBoard 7) 'O)) (return-from CheckOWin T))
      ((and (eql (aref GameBoard 2) 'O) (eql (aref GameBoard 5) 'O) (eql (aref GameBoard 8) 'O)) (return-from CheckOWin T))
      ((and (eql (aref GameBoard 3) 'O) (eql (aref GameBoard 4) 'O) (eql (aref GameBoard 5) 'O)) (return-from CheckOWin T))
      ((and (eql (aref GameBoard 6) 'O) (eql (aref GameBoard 7) 'O) (eql (aref GameBoard 8) 'O)) (return-from CheckOWin T))
      ((and (eql (aref GameBoard 2) 'O) (eql (aref GameBoard 4) 'O) (eql (aref GameBoard 6) 'O)) (return-from CheckOWin T))
      (nil)
   )
)

(defun Xmove ()
   ;; Set the first player to X, Ask for their move, read it in, update the possible moves
   ;; subtract one from the space chosen and update the game board to put an X in the
   ;; appropriate space
   (setq CurrentPlayer 'X)
   (print PossibleMoves)
   (print "Enter space for your move (X):")
   (setq PlayerMove (read))
   (UpdatePossibleMoves PlayerMove)
   (setq PlayerMove (- PlayerMove 1))
   (UpdateBoard CurrentPlayer PlayerMove)
   
   ;; Output the current status of the board
   (OutputBoard)
)

(defun Omove ()
   ;; Perform the same steps as above, however instead of asking for user input, use the ComputerMove and AlphaBeta functions to generate the move
   (setq CurrentPlayer 'O)
   (setq CompsMove (ComputerMove))
   (UpdatePossibleMoves CompsMove)
   (setq CurrentPlayer 'O)
   (UpdateBoard CurrentPlayer (- CompsMove 1))
   
   ;; Output the current status of the board
   (OutputBoard)
)

;; Primary working function for finding a computer move
(defun ComputerMove ()
   (setq Value -2)                           ;; Initial value that is outside the utility values of +/-1 and zero
   (setq ListLength (- (length PossibleMoves) 1))   ;; LCV based on the current moves availible for this computer turn
   (setq TempMoveList PossibleMoves)            ;; Set the temporary list to be the same as the actual list
   
   (dotimes (i (- ListLength 1))
      ;; This will reset the Temporary Move list after each check of the availible moves. Such that each of the possible moves can be checked
      (setq TempMoveList PossibleMoves)
      (setq CurrentMove (nth i PossibleMoves)) ;; Choose the  next availible move
      
      (if (= i 0)      ;; If this is the first itteration, assume that the first availible move will be the selected move for this turn
         (setq SelectedMove CurrentMove)
      )
      
      ;; Update the temporary list of moves, so that the Alpha-Beta method will not include it as a child move
      ;; Set the next move to be that of the human player, X
      ;; Get the value returned by AlphaBeta and store it to evaluate later if it is a better move than the previous ones
      (SwapPlayer)
      (UpdateTempPossibleMoves CurrentMove)
      (setq NewValue (AlphaBeta -9999 9999 0))
      
      ;; We want to maximize the best move, if the value we have for the move we are evaluating is better than current value, save it and the
      ;; move associated with it
      (if (> NewValue Value)
         (progn
            (setq Value NewValue)
            (setq SelectedMove CurrentMove)
         )
      )
   )
   
   ;; Return the "best" move
   (return-from ComputerMove SelectedMove)
)

;; Perform an Alpha-Beta search on the child moves to a limit of 5
(defun AlphaBeta (alpha beta limit)
   ;; Check for terminal status or depth limit
   (if (CheckDrawT)
      (return-from AlphaBeta 0)
   )
   (if (= limit 5)
      (return-from AlphaBeta 0)
   )
   (if (CheckXWinT)
      (return-from AlphaBeta -1)
   )
   (if (CheckOWinT)
      (return-from AlphaBeta 1)
   )
   
   ;; If max's move (O)
   ;; Algorithm from: http://www.ocf.berkeley.edu/~yosenl/extras/alphabeta/alphabeta.html
   (if (eql CurrentPlayer 'O)
      (progn
         (dolist (moves TempMoveList)
            (UpdateTempPossibleMoves moves)            ;; Remove this current move from the ones being checked
            (UpdateTempBoard CurrentPlayer (- moves 1))   ;; update the temporary game board accordingly
            (SwapPlayer)
            (setq score (AlphaBeta alpha beta (+ limit 1))) ;; call again with the other player, and incrising the limit by one
            (if (> score alpha)   ;; this is a better move
               (setq alpha score)
            )
            (if (>= alpha beta)      ;; Cut off point
               (return-from AlphaBeta alpha)
            )
         )
         (return-from AlphaBeta alpha)   ;;this should be the value of the best move
      )
      (progn                           ;; This process is the same as above, however for the Min player / beta
         (dolist (moves TempMoveList)
            (UpdateTempPossibleMoves moves)
            (UpdateTempBoard CurrentPlayer (- moves 1))
            (SwapPlayer)
            (setq score (AlphaBeta alpha beta (+ limit 1)))
            (if (< score beta)
               (setq beta score)
            )
            (if (>= beta alpha)
               (return-from AlphaBeta beta)
            )
         )
         (return-from AlphaBeta beta)
      )
   )
)

;; Updates the temproary list, removes the passed in move
(defun UpdateTempPossibleMoves (move)
   (setq temp nil)
   (dolist (y TempMoveList)
      (if (/= move y)
         (push y temp)
      )
   )
   
   (setq TempMoveList temp)
   (setq temp nil)
   (dolist (y TempMoveList)
      (push y temp)
   )
   
   (setq TempMoveList temp)
   (setq temp nil)
)

;; Updates the possible moves, removing the arugment move from the list
(defun UpdatePossibleMoves (move)
   (setq temp nil)
   (dolist (y PossibleMoves)
      (if (/= move y)
         (push y temp)
      )
   )
   
   (setq PossibleMoves temp)
   (setq temp nil)
   (dolist (y PossibleMoves)
      (push y temp)
   )
   
   (setq PossibleMoves temp)
   (setq temp nil)
)

;; Starts the game. This allows for the game to be replayed by making the entry point outside of the tictactoe function
;; welcome messege is only displayed once.
(defun StartGame ()
   (print "Welcome to Tic-Tac-Toe. Please enter your first move:")
   (tictactoe)
)

;; Function to start a game
(defun tictactoe ()
   (print "Player X, first move:")
   (PlayGame)
   
   (print "Play again?")
   (setf answer (read))
   
   (if (eql answer 'Y)
      (tictactoe)
   )
)

;; Output the current status of the game board
(defun OutputBoard ()
   (format t "~% ~d ~d ~d~% ~d ~d ~d~% ~d ~d ~d~%~%"
      (or (aref GameBoard 0) "-")   (or (aref GameBoard 1) "-") (or (aref GameBoard 2) "-")
      (or (aref GameBoard 3) "-")   (or (aref GameBoard 4) "-") (or (aref GameBoard 5) "-")
      (or (aref GameBoard 6) "-")   (or (aref GameBoard 7) "-") (or (aref GameBoard 8) "-")
   )
)


Top
  Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 1 post ] 

All times are UTC - 8 hours


Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group

© 2014 Future US, Inc. All rights reserved.