Game Trees: Minimax, Alpha-Beta Pruning, Move Ordering & Zobrist Transposition Tables

1. Minimax, Negamax & The Alpha-Beta Pruning Window

In a two-player deterministic zero-sum game of perfect information (Chess, Go, Checkers, Connect Four), the Minimax value of state $s$ is the best score the active player can guarantee against a perfect opponent. Rather than writing separate max_value() and min_value() functions, production engines use Negamax, relying on the zero-sum symmetry $\max(a, b) = -\min(-a, -b)$ and evaluating every board strictly from the side-to-move's perspective.

2. The $\Theta(b^{d/2})$ Theorem, Iterative Deepening & Zobrist Hashing

How much does Alpha-Beta prune? If moves are searched in worst-first order, Alpha-Beta prunes nothing and visits all $b^d$ leaves. If moves are searched in best-first order (the best move at each node is tried first), Knuth and Moore (1975) proved that Alpha-Beta visits exactly:

This reduces the effective branching factor from $b$ to $\sqrt{b}$ (e.g., in Chess from $b \approx 35$ to $\sqrt{35} \approx 6$), literally doubling the reachable search depth within a fixed time budget! To achieve near-perfect move ordering and avoid re-searching identical positions reached via different move sequences (transpositions):

• Zobrist Hashing (1970): Pre-generate a table of random 64-bit integers $Z[\text{piece}][\text{square}]$. The hash of a board is the XOR of $Z[p][sq]$ for all pieces on the board. Making or unmaking a move updates the 64-bit hash in $O(1)$ time via 2 or 3 XORs!
• Transposition Table (TT) Node Types: A cached depth-$d$ search over window $[\alpha, \beta]$ stores one of three bound flags:
  1. EXACT (PV-Node, $\alpha < v < \beta$): True minimax value is $v$.
  2. LOWER_BOUND (Cut-Node / Beta-Cutoff, $v \ge \beta$): True value is $\ge v$.
  3. UPPER_BOUND (All-Node / Fail-Low, $v \le \alpha$): True value is $\le v$.
• Iterative Deepening ($d = 1, 2, \dots, D$): Searching depths $1 \dots D-1$ adds only $\frac{1}{\sqrt{b} - 1}$ overhead, while populating the Transposition Table with the best move (TT-move) at every node—guaranteeing near-optimal move ordering for depth $D$!

3. Complexity Matrix

4. Reference C++20 Implementation

#include <algorithm>
#include <cstdint>
#include <vector>

enum class BoundFlag : std::uint8_t { NONE = 0, EXACT = 1, LOWER = 2, UPPER = 3 };

struct TTEntry {
    std::uint64_t key = 0;
    int value = 0;
    int depth = -1;
    int best_move = -1;
    BoundFlag flag = BoundFlag::NONE;
};

// Generic Negamax with Alpha-Beta Pruning and Zobrist Transposition Table
template <typename GameState>
class AlphaBetaEngine {
    std::vector<TTEntry> tt;
    std::size_t mask;
    static constexpr int INF = 1'000'000'000;

public:
    explicit AlphaBetaEngine(std::size_t power_of_two_entries = (1ULL << 20))
        : tt(power_of_two_entries), mask(power_of_two_entries - 1) {}

    int negamax(GameState& state, int depth, int alpha, int beta) {
        const int alpha_orig = alpha;
        const std::uint64_t h = state.zobrist_hash();
        TTEntry& entry = tt[h & mask];

        // 1. Transposition Table Lookup
        int tt_move = -1;
        if (entry.flag != BoundFlag::NONE && entry.key == h) {
            tt_move = entry.best_move;
            if (entry.depth >= depth) {
                if (entry.flag == BoundFlag::EXACT) return entry.value;
                if (entry.flag == BoundFlag::LOWER) alpha = std::max(alpha, entry.value);
                else if (entry.flag == BoundFlag::UPPER) beta = std::min(beta, entry.value);
                if (alpha >= beta) return entry.value; // TT Cutoff!
            }
        }

        // 2. Base Case: Terminal State or Horizon Depth
        if (depth == 0 || state.is_terminal()) {
            return state.evaluate_for_side_to_move();
        }

        // 3. Move Generation + Move Ordering (Prioritize TT Best Move first!)
        std::vector<int> moves = state.generate_moves();
        if (tt_move != -1) {
            auto it = std::find(moves.begin(), moves.end(), tt_move);
            if (it != moves.end()) std::iter_swap(moves.begin(), it);
        }

        int best_val = -INF;
        int best_move = moves.empty() ? -1 : moves[0];

        for (int m : moves) {
            state.make_move(m);
            int score = -negamax(state, depth - 1, -beta, -alpha);
            state.undo_move(m);

            if (score > best_val) {
                best_val = score;
                best_move = m;
            }
            if (score > alpha) {
                alpha = score;
            }
            if (alpha >= beta) {
                break; // Beta-Cutoff (Fail-High)
            }
        }

        // 4. Transposition Table Store with Correct Bound Classification
        entry.key = h;
        entry.value = best_val;
        entry.depth = depth;
        entry.best_move = best_move;
        if (best_val <= alpha_orig) {
            entry.flag = BoundFlag::UPPER;
        } else if (best_val >= beta) {
            entry.flag = BoundFlag::LOWER;
        } else {
            entry.flag = BoundFlag::EXACT;
        }
        return best_val;
    }
};