Common Lisp 中的 Alpha-beta 修剪

Question

我尝试使用维基百科中的伪代码对 Alpha-beta 进行编码。在程序达到 (EQ depth 0) 后，它 returns 启发式值但深度继续减少导致循环。现在我的代码如下所示：

(defun ab(tab node depth a b)
(cond ((EQ depth 0) (calculaH tab))
        ((eq (mod depth 2) 0) (setq v -999999) (setq movimiento (sigMov depth node tab))  (loop while (not(null movimiento))  
                                                        do (setq v (max v (ab (nth 3 movimiento) movimiento (- depth 1) a b)))
                                                           (setq a (max a v))
                                                           (cond((<= b a) (break))
                                                                (t (setq movimiento (sigMov depth movimiento tab))))) (return v))

        (t (setq v 999999) (setq movimiento (sigMov depth node tab)) (loop while (not(null movimiento))   
                                                        do (setq v (min v (ab (nth 3 movimiento) movimiento (- depth 1) a b)))
                                                           (setq a (min b v))
                                                           (cond((<= b a) (break))
                                                                (t (setq movimiento (sigMov depth movimiento tab))))) (return v))))

我应该在我的代码中的某个地方增加深度值吗？为什么递归不自己增加值？

Answer 1

维基百科上的 alpha-beta prunning algorithm 几乎可以原样翻译成 Lisp。因为它使用无限值，所以我们不要使用“999999”，而是定义 min 和 max 可以可靠地处理这些特殊值的函数：

(defpackage :alphabeta
  (:use :cl)
  ;; custom min/max functions that support infinity
  (:shadow min max))

(in-package :alphabeta)

(defvar -∞ '-∞ "Negative infinity symbol")
(defvar +∞ '+∞ "Positive infinity symbol")

(defun min (a b)
  (cond
    ((eql a +∞) b)
    ((eql b +∞) a)
    ((eql a -∞) -∞)
    ((eql b -∞) -∞)
    (t (cl:min a b))))

(defun max (a b)
  (cond
    ((eql a -∞) b)
    ((eql b -∞) a)
    ((eql a +∞) +∞)
    ((eql b +∞) +∞)
    (t (cl:max a b))))

该代码还依赖辅助函数，我在这里声明以避免警告：

 ;; You need to implement the followning functions
(declaim (ftype function terminal-node-p heuristic-value children))

那么，伪代码就可以写得差不多了。为了这个问题，我保留了相同的希腊变量，但正如 Dan Robertson 在评论中指出的那样，这可能会导致意外：

One thing to be wary of when using names like α or β is that a typical Unicode-aware lisp implementation will upcase them into Α and Β. Can you tell the difference between A and Α or B and Β?

(defun alphabeta (node depth α β maximizing-player-p)
  (when (or (= depth 0) (terminal-node-p node))
    (return-from alphabeta (heuristic-value node)))
  (if maximizing-player-p
      (let ((value -∞))
        (dolist (child (children node))
          (setf value (max value (alphabeta child (1- depth) α β nil)))
          (setf α (max α value))
          (when (<= β α)
            ;; β cut-off
            (return)))
        value)
      (let ((value +∞))
        (dolist (child (children node))
          (setf value (min value (alphabeta child (1- depth) α β t)))
          (setf α (min α value))
          (when (<= β α)
            ;; α cut-off
            (return)))
        value)))

如果您只想比较数字，请不要将数字与 EQ. Use = 进行比较。
始终使用 let 引入局部变量，永远不要 setq 未在当前范围内定义的变量。您的代码失败是因为您的 Lisp 实现在您第一次对未绑定符号调用 setq 时定义了全局变量。之后，您在递归代码中更改了全局变量，这使其功能失调。
不要有过长的行（大多数语言都是如此），正确缩进，将每个新表格放在自己的行上，从相同的缩进开始.
BREAK in Lisp enters the debugger. If you want to exit a loop early, use RETURN (this works because iteration constructs like DO introduce implicit BLOCK 名为 nil).

Common Lisp 中的 Alpha-beta 修剪

Alpha-beta pruning in Common Lisp

artificial-intelligence

common-lisp

minimax

alpha-beta-pruning