Removing Branches That Cannot Change the Answer

The Rocky Mountain juniper on my bench has a branch I’ve been watching for three weeks. It grows inward, toward the trunk, and I know it has to go eventually — it will never get light there, will never contribute to the silhouette. But I wait, because in bonsai you don’t cut until you’re certain.

Alpha-beta pruning operates on the same principle, just without the patience. When searching a game tree — chess, checkers, any two-player zero-sum game — you’re alternating between maximizing your score and minimizing your opponent’s. At some point, you discover a branch that cannot possibly influence the final decision. Your opponent has a guaranteed response that makes this entire line irrelevant. So you stop looking.

The “alpha” tracks the best score the maximizing player can guarantee. “Beta” tracks the best the minimizing player can force. When beta drops below alpha on any branch, that subtree gets pruned. Nothing there can change what either player would actually choose.

(defn alpha-beta [node depth alpha beta maximizing?]
  (if (or (zero? depth) (leaf? node))
    (evaluate node)
    (loop [children (get-children node) a alpha b beta]
      (if (or (empty? children) (<= b a))
        (if maximizing? a b)
        (let [v (alpha-beta (first children) (dec depth) a b (not maximizing?))]
          (recur (rest children)
                 (if maximizing? (max a v) a)
                 (if maximizing? b (min b v))))))))

The Ada version makes the bounds explicit as in-out parameters — the language insists you declare your intentions about what might change:

procedure Alpha_Beta_Demo is
   type Tree_Node;
   type Tree_Node_Access is access Tree_Node;
   type Child_List is array (Positive range <>) of Tree_Node_Access;
   type Child_List_Access is access Child_List;

   type Tree_Node is record
      Score : Integer := 0;
      Kids  : Child_List_Access := null;
   end record;

   function Is_Leaf (Node : Tree_Node) return Boolean is (Node.Kids = null);
   function Evaluate (Node : Tree_Node) return Integer is (Node.Score);

   procedure Alpha_Beta (Node : Tree_Node; Depth : Natural;
                         Alpha, Beta : in out Integer;
                         Maximizing : Boolean; Score : out Integer) is
      Child_Score : Integer;
      A : Integer := Alpha;
      B : Integer := Beta;
   begin
      if Depth = 0 or else Is_Leaf (Node) then
         Score := Evaluate (Node);
      else
         for Child of Node.Kids.all loop
            exit when B <= A;
            Alpha_Beta (Child.all, Depth - 1, A, B, not Maximizing, Child_Score);
            if Maximizing then A := Integer'Max (A, Child_Score);
            else B := Integer'Min (B, Child_Score); end if;
         end loop;
         Score := (if Maximizing then A else B);
      end if;
   end Alpha_Beta;
begin
   null;
end Alpha_Beta_Demo;

With good move ordering, alpha-beta can examine roughly the square root of the positions that minimax would need. That’s not a small improvement — it’s the difference between looking five moves ahead and looking ten.

The juniper branch is still there. I’ve decided it stays until May. The algorithm would have cut it weeks ago, but it doesn’t have to live with the result.