Common Lisp中的Alpha-beta修剪

Question

我尝试使用维基百科中的伪代码编码Alpha-beta。程序到达(EQ depth 0)后，它返回启发式值，但深度继续deacreasing导致循环。现在我的代码看起来像这样：

(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在评论中指出的那样，这可能会导致意外：

使用诸如α或β之类的名称时要注意的一件事是，典型的支持Unicode的lisp实现会将它们改为Α和Β。你能说出A和Α或B和Β之间的区别吗？

(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进行比较。如果您希望仅比较数字，请使用=。
• 总是用let引入局部变量，永远不要在setq中引入一个未在当前范围内定义的变量。您的代码失败，因为您的Lisp实现在您第一次在未绑定的符号上调用setq时定义全局变量。之后，您会在递归代码中改变全局变量，这会使其失效。
• 没有超长的行（在大多数语言中都是如此），正确缩进，将每个新表单放在自己的行上，从同一个缩进开始。
• Lisp中的BREAK进入调试器。如果你想提前退出循环，请使用RETURN（这是有效的，因为像DO这样的迭代构造引入了名为BLOCK的隐式nils）。