用lisp實現的井字遊戲正在完成遊戲而不是一個動作

Question

我正在做一個簡單的CLI tic-tac-toe遊戲，它使用一個使用LISP的alpha-beta修剪的negamax算法的AI，我正在人工智能如何實現其動作的問題。它不是完成它應該的單一動作，而是完全地完成遊戲，所以遊戲只有最後兩步。我已經運行了它（步驟），它看起來像問題是，在negamax函數的（when（> value bestValue））塊中設置了bestPath變量，即使它說該塊沒有被執行爲。而且，它設置的值並不是正確的值，如果它適合設置它的話。有什麼建議麼？這是我的代碼。

; 
; Prints an ASCII tic tac toe board 
; 
(defun print-board (board) 
    (format t "~% ~d | ~d | ~d 0 | 1 | 2~% --------- ---------~% ~d |  ~d | ~d 3 | 4 | 5~% --------- ---------~% ~d | ~d | ~d 6 | 7 |  8~%~%" 
     (or (nth 0 board) ".") (or (nth 1 board) ".") (or (nth 2 board) ".") 
     (or (nth 3 board) ".") (or (nth 4 board) ".") (or (nth 5 board) ".") 
     (or (nth 6 board) ".") (or (nth 7 board) ".") (or (nth 8 board) "."))) 

; 
; Returns the symbol representing the other player 
; 
(defun opposite (player) 
    (if (eq player 'x) 'o 'x)) 

; 
; Checks if the player won 
; 
(defun won-p (board player) 
    (or (and (eq (nth 0 board) player) 
      (eq (nth 1 board) player) 
      (eq (nth 2 board) player)) 
     (and (eq (nth 3 board) player) 
      (eq (nth 4 board) player) 
      (eq (nth 5 board) player)) 
     (and (eq (nth 6 board) player) 
      (eq (nth 7 board) player) 
      (eq (nth 8 board) player)) 
     (and (eq (nth 0 board) player) 
      (eq (nth 3 board) player) 
      (eq (nth 6 board) player)) 
     (and (eq (nth 1 board) player) 
      (eq (nth 4 board) player) 
      (eq (nth 7 board) player)) 
     (and (eq (nth 2 board) player) 
      (eq (nth 5 board) player) 
      (eq (nth 8 board) player)) 
     (and (eq (nth 0 board) player) 
      (eq (nth 4 board) player) 
      (eq (nth 8 board) player)) 
     (and (eq (nth 2 board) player) 
      (eq (nth 4 board) player) 
      (eq (nth 6 board) player)))) 

; 
; Checks if neither player won and there are no valid moves 
; 
(defun draw-p (board) 
    (and (not (won-p board 'o)) 
     (not (won-p board 'x)) 
     (not (member nil board)))) 

; 
; Places a token at the desired position unless 
; it is already occupied 
; 
(defun make-move (board player move) 
    (unless (nth move board) 
     (let ((boardCopy (copy-list board))) 
      (setf (nth move boardCopy) player) 
      boardCopy))) 

; 
; Starts a human v human game of tic tac toe 
; 
(defun play() 
    (setf currentPlayer 'x) 
    (setf currentBoard (list nil nil nil nil nil nil nil nil nil)) 
    (print-board currentBoard) 
    (do() 
     ((or (won-p currentBoard 'x) 
      (won-p currentBoard 'o) 
      (draw-p currentBoard)) 
      (opposite currentPlayer)) 
     (format t "~%Enter move for ~a's: " currentPlayer) 
     (setf move (read)) 
     (do() 
      ((setf nextBoard (make-move currentBoard currentPlayer move))) 
      (format t "~%Illegal move. Try again: ") 
      (setf move (read))) 
     (setf currentBoard nextBoard) 
     (print-board currentBoard) 
     (if (won-p currentBoard currentPlayer) 
      (format t "~%Player ~a wins!" currentPlayer)) 
     (if (draw-p currentBoard) 
      (format t "~%Draw!")) 
     (setf currentPlayer (opposite currentPlayer)))) 

這裏是AI的代碼。

; 
; Evaluates the heuristic value of the board position 
; from the viewpoint of the player 
; 
(defun evaluate (board player depth) 
    (cond ((won-p board player) (- 10 depth)) 
      ((won-p board (opposite player)) (+ -10 depth)) 
      (t 0))) 

; 
; Generates all possible legal moves from the current position 
; 
(defun generate-moves (board player) 
    (loop for move from 0 to 8 
      unless (nth move board) 
      collect (make-move board player move))) 

; 
; Checks if the algorithm has searched deep enough into the tree. 
; 
(defun deep-enough (board player) 
    (or (won-p board player) 
     (won-p board (opposite player)) 
     (draw-p board))) 

; 
; Algorithm for deciding which move to choose 
; 
(defun negamax(board player depth) 
    (cond ((deep-enough board player) 
      (cons (evaluate board player depth) board)) 
      (t (setq bestValue -10) 
      (setq bestPath nil) 
      (setq successors (generate-moves board player)) 
      (loop for successor in successors 
       do 
        (let* ((result (negamax successor (opposite player) (+ depth 1))) 
         (value (- (first result)))) 
         (when (> value bestValue) 
           (setq bestValue value) 
           (setq bestPath successor)))) 
      (cons bestValue bestPath)))) 

; 
; Starts a game of tic-tac-toe with the computer 
; 
(defun play-ai() 
    (setq currentPlayer 'x) 
    (setq currentBoard (list nil nil nil nil nil nil nil nil nil)) 
    (print-board currentBoard) 
    (do() 
     ((or (won-p currentBoard 'x) 
      (won-p currentBoard 'o) 
      (draw-p currentBoard)) 
      (opposite currentPlayer)) 
     (format t "~%Enter move for ~a's: " currentPlayer) 
     (cond ((eq currentPlayer 'x) 
       (setf move (read)) 
       (do() 
        ((setf nextBoard (make-move currentBoard currentPlayer move))) 
        (format t "~%Illegal move. Try again: ") 
        (setf move (read))) 
       (setf currentBoard nextBoard) 
       (print-board currentBoard) 
       (if (won-p currentBoard currentPlayer) 
        (format t "~%Player ~a wins!" currentPlayer)) 
       (if (draw-p currentBoard) 
        (format t "~%Draw!")) 
       (setf currentPlayer (opposite currentPlayer))) 

      (t (setq currentBoard (rest (negamax currentBoard currentPlayer 1))) 
       (write-line "") 
       (print-board currentBoard) 
       (if (won-p currentBoard currentPlayer) 
       (format t "~%Player ~a wins!" currentPlayer)) 
       (if (draw-p currentBoard) 
       (format t "~%Draw!")) 
       (setf currentPlayer (opposite currentPlayer)))))) 

Answer 1

爲了解決企業的實際問題，你需要使用LET而不是SETQ定義局部變量。特別是在NEGAMAX函數中：

(defun negamax(board player depth) 
    (cond ((deep-enough board player) 
     (cons (evaluate board player depth) board)) 
     (t (let ((best-value -10) 
       (best-path nil) 
       (successors (generate-moves board player))) 
      (loop for successor in successors 
       do (let* ((result (negamax successor (opposite player) (+ depth 1))) 
          (value (- (first result)))) 
        (when (> value best-value) 
         (setf best-value value) 
         (setf best-path successor)))) 
      (cons best-value best-path))))) 

還有其他代碼問題。我將重點介紹PLAY-AI以保持簡短，但這些也適用於其他代碼。

1. 命名變量使用常用Lisp字典之間的破折號代替駝峯代替駝峯。就像你用函數做的一樣。
2. COND中有重複代碼（從(PRINT-BOARD ...)開始）。您應該將其移動到COND之外。
3. 你應該把它分成更小的函數。至少使用一個單獨的功能來要求玩家輸入。

4. IMO，在這裏使用LOOP而不是DO會更清潔。或者更好，使用iterate。如果你有quicklisp設置，你可以做

   (ql:quickload :iterate) 
   (use-package :iterate) 
   

5. 的結束消息（「X韓元」，「畫」），可以在循環外移動或在另一個函數來完成。

6. 您正在檢查每個玩家在遊戲循環的每次迭代中是否贏得了遊戲。由於只有一名球員進行了移動，因此足以檢查該球員是否獲勝。另外DRAW-P不需要檢查其中一名選手是否贏得比賽，因爲無論如何都要在致電DRAW-P之前進行檢查。
7. 列表的隨機訪問非常低效，所以最好使用數組作爲板。我沒有解決這個問題，因爲它需要更改大部分代碼。

下面是使用迭代有點清理版本：或者

(defun ask-move (board player) 
    (format t "~&Enter move for ~a's: " player) 
    (iter (for move = (make-move board player (read))) 
     (when move (return move)) 
     (format t "~&Illegal move. Try again: "))) 

(defun game-loop() 
    (let ((player 'x) 
     (board (list nil nil nil nil nil nil nil nil nil))) 
    (print-board board) 
    (iter (setf board (if (eq player 'x) 
          (ask-move board player) 
          (rest (negamax board player 1)))) 
      (print-board board) 
      (cond ((won-p board player) (return player)) 
       ((draw-p board) (return :draw))) 
      (setf player (opposite player))))) 

(defun play-ai() 
    (case (game-loop) 
    (x (format t "~&Player wins!")) 
    (o (format t "~&AI wins!")) 
    (:draw (format t "~&Draw!")))) 

與正規循環一樣。差別不大，但迭代的語法稍微好一點。

(defun ask-move (board player) 
    (format t "~&Enter move for ~a's: " player) 
    (loop 
    for move = (make-move board player (read)) 
    when move do (return move) 
    do (format t "~&Illegal move. Try again: "))) 

(defun game-loop() 
    (let ((player 'x) 
     (board (list nil nil nil nil nil nil nil nil nil))) 
    (print-board board) 
    (loop 
     do (setf board (if (eq player 'x) 
          (ask-move board player) 
          (rest (negamax board player 1)))) 
     do (print-board board) 
     when (won-p board player) do (return player) 
     when (draw-p board) do (return :draw) 
     do (setf player (opposite player))))) 

(defun play-ai() 
    (case (game-loop) 
    (x (format t "~&Player wins!")) 
    (o (format t "~&AI wins!")) 
    (:draw (format t "~&Draw!"))))