代码之家 › 专栏 › 技术社区 › Christian.M

用lisp实现的Tic-tac-toe正在结束游戏,而不是进行一次移动

negamax game-ai minimax tic-tac-toe lisp

-1

Christian.M · 技术社区 · 9 年前

我正在用一个AI制作一个简单的CLI tic tac toe游戏,这个AI使用negamax算法,并使用LISP进行alpha beta修剪,我对AI如何移动有问题。它没有做出它应该做的一个动作,而是完全完成了游戏,因此游戏只剩下两个动作。我已经运行了(步骤),看起来问题是bestPath变量是在negamax函数中的(when(>value bestValue))块中设置的,即使它表示该块没有按执行。此外,如果设置该值合适,则设置的值不正确。有什么建议吗?这是我的代码。

;
; 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))))

这是人工智能的代码。

;
; 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))))))

1 回复 | 直到 9 年前

1

0

jkiiski 9 年前

要解决实际问题,您需要使用 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 这里将保持简短,但这些也适用于代码的其余部分。

使用单词之间的破折号而不是camelCase的常规Lisp约定命名变量。就像你处理函数一样。
中有重复代码 COND (所有内容来自 (PRINT-BOARD ...) ). 你应该把它移到 条件 .
你应该把它分成更小的函数。至少使用一个单独的函数要求玩家输入。
IMO,使用起来会更干净 LOOP 而不是 DO 在这里或者更好,使用 iterate .如果你有 quicklisp 设置,你可以
```
(ql:quickload :iterate)
(use-package :iterate)
```
结束消息(“xwon”、“draw”)可以移动到循环之外或在另一个函数中完成。
你要检查每一个玩家在游戏循环的每一次迭代中是否赢得了游戏。因为只有一个玩家移动,所以检查该玩家是否获胜就足够了。而且 DRAW-P 不需要检查其中一个玩家是否获胜,因为在呼叫之前会进行检查 拉P 无论如何
列表的随机访问效率非常低,因此最好为电路板使用数组。我没有修复这个问题,因为它需要修改大部分代码。

下面是一个使用iterate进行了一些清理的版本:

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