-1

我正在制作一个简单的 CLI tic-tac-toe 游戏，其 AI 使用 Negamax 算法和 LISP 进行 alpha-beta 修剪，我对 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))))))
4

1 回答 1

0

要解决实际问题，需要使用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 约定在单词之间使用破折号而不是 camelCase 来命名变量。就像你对函数所做的那样。
  2. COND（来自 的所有内容）中有重复的代码(PRINT-BOARD ...)。你应该把它移到COND.
  3. 您应该将其拆分为更小的函数。至少使用一个单独的函数来询问玩家输入。

  4. IMO，用它LOOP代替DO这里会更干净。或者更好的是，使用iterate。如果你设置了quicklisp，你可以这样做

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

  5. 结束消息（“x won”、“draw”）可以移出循环或在另一个函数中完成。

  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!"))))

或与常规循环相同。差别不大，但 iterate 的语法稍好一些。

(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!"))))
于 2016-04-23T07:46:26.197 回答