用 lisp 实现的井字游戏是完成游戏而不是一步一步
Tic tac toe implemented with lisp is finishing game instead of making a single move
我正在使用 AI 制作一个简单的 CLI tic-tac-toe 游戏，AI 使用 negamax 算法和 alpha-beta p运行ing 使用 LISP，我对 AI 如何制作它有疑问移动。它没有采取应有的单一步骤，而是完全玩完了游戏，因此游戏只进行了两步。我通过 (step) 运行 它看起来问题是 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))))
这是 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))))))
解决实际问题需要用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，但这些也适用于其余代码。
- 使用通常的 Lisp 约定在单词之间使用破折号而不是驼峰式命名变量。就像你对函数所做的那样。
COND 中有重复代码（(PRINT-BOARD ...) 中的所有内容）。你应该把它移到 COND.- 你应该把它拆分成更小的功能。至少使用一个单独的函数来询问玩家输入。
IMO，在这里使用 LOOP 而不是 DO 会更干净。或者更好的是，使用 iterate. If you have quicklisp 设置，你可以只做
(ql:quickload :iterate)
(use-package :iterate)
结束消息（"x won"、"draw"）可以移出循环或在另一个函数中完成。
- 您要检查是否有玩家在游戏循环的每次迭代中都赢得了游戏。由于只有一名玩家下棋，因此足以检查该玩家是否获胜。另外
DRAW-P 不需要检查其中一名玩家是否赢了，因为无论如何在调用 DRAW-P 之前都会检查它。
- 列表的随机访问效率非常低，所以板子最好使用数组。我没有修复它，因为它需要更改大部分代码。
这是一个使用迭代进行了稍微清理的版本：
(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!"))))
我正在使用 AI 制作一个简单的 CLI tic-tac-toe 游戏，AI 使用 negamax 算法和 alpha-beta p运行ing 使用 LISP，我对 AI 如何制作它有疑问移动。它没有采取应有的单一步骤，而是完全玩完了游戏，因此游戏只进行了两步。我通过 (step) 运行 它看起来问题是 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))))
这是 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))))))
解决实际问题需要用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，但这些也适用于其余代码。
- 使用通常的 Lisp 约定在单词之间使用破折号而不是驼峰式命名变量。就像你对函数所做的那样。
COND中有重复代码（(PRINT-BOARD ...)中的所有内容）。你应该把它移到COND. 之外
- 你应该把它拆分成更小的功能。至少使用一个单独的函数来询问玩家输入。
IMO，在这里使用
LOOP而不是DO会更干净。或者更好的是，使用 iterate. If you have quicklisp 设置，你可以只做(ql:quickload :iterate) (use-package :iterate)结束消息（"x won"、"draw"）可以移出循环或在另一个函数中完成。
- 您要检查是否有玩家在游戏循环的每次迭代中都赢得了游戏。由于只有一名玩家下棋，因此足以检查该玩家是否获胜。另外
DRAW-P不需要检查其中一名玩家是否赢了，因为无论如何在调用DRAW-P之前都会检查它。 - 列表的随机访问效率非常低，所以板子最好使用数组。我没有修复它，因为它需要更改大部分代码。
这是一个使用迭代进行了稍微清理的版本：
(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!"))))