Крестики-нолики, реализованные с помощью lisp, заканчивают игру, а не делают один ход

Question

Я делаю простую игру в крестики-нолики с ИИ, в которой используется алгоритм negamax с отсечкой альфа-бета с использованием LISP, и у меня возникают проблемы с тем, как ИИ делает свой ход. Вместо того, чтобы делать единственный ход, который он должен сделать, он полностью разыгрывает игру, поэтому игры занимают только два последних хода. Я выполнил (шаг), и похоже, что проблема в том, что переменная bestPath устанавливается в блоке (when (> value bestValue)) в функции negamax, даже когда он говорит, что этот блок не выполняется как. Кроме того, значение, для которого оно установлено, не является правильным, которое должно быть, если оно было подходящим для его установки. Какие-либо предложения? Вот мой код

;
; 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. Назовите переменные, используя обычное лисповское соглашение штрихов между словами вместо camelCase. Так же, как вы сделали с функциями.
2. Там повторяющийся код в COND (все из (PRINT-BOARD ...)). Вы должны переместить это за пределы COND,
3. Вы должны разделить его на более мелкие функции. По крайней мере, используйте отдельную функцию, чтобы попросить игрока ввести.

4. ИМО, было бы чище использовать LOOP вместо DO Вот. Или, что еще лучше, используйте итерацию. Если у вас настроен 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!"))))

Или то же самое с обычным циклом. Не большая разница, но итерация имеет немного более приятный синтаксис.

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