Alpha-beta pruning in Common Lisp

Question

I tried coding Alpha-beta using the pseudocode found in Wikipedia. After the program reaches (EQ depth 0) it returns the heuristic value but depth continues deacreasing causing a cycle. Right now my code looks like this:

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

Should I increase depth value somwhere in my code? Why doesn´t the recursion increases the value by itself?

Answer 1

The alpha-beta prunning algorithm on Wikipedia can be translated into Lisp almost as-is. Since it uses infinite values, let's not hack around with "999999" but define min and max functions that work reliably with those special values:

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

The code also relies on auxiliary functions, which I declare here to avoid warnings:

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

Then, the pseudo-code can be written nearly identically. For the sake of this question, I kept the same greek variables, but as pointed out by Dan Robertson in comments, this might lead to surprises:

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

• Never compare numbers with EQ. Use = if you expect to compare only numbers.

• Always introduce local variables with let, never setq a variable which is not defined in current scope. Your code fails because your Lisp implementation define global variables the first time you call setq on unbound symbols. After that, you mutate global variables in your recursive code, which make it dysfunctional.

• Do not have overlong lines (this is true in most languages), indent properly, put each new form on its own line starting at the same indentation.

• 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 BLOCKs named nil).