Negascout

Purpose: A refinement of alpha-beta that uses null-window searches to prove most moves are inferior cheaply, re-searching only when one turns out to be better. Typically 10-20% faster than plain alpha-beta on well-ordered trees. Also called Principal Variation Search (PVS).

The Idea

Alpha-beta already prunes; Negascout adds a bet:

If the moves are well ordered, the first move is almost always the best. So search the first move with the full window $[\alpha ,\beta ]$, and search every other move with the null window $[\alpha ,\alpha +1]$, which is much cheaper. A null-window search cannot return an exact value — only "$\le \alpha$" or "$>\alpha$". If it says $\le \alpha$ (the usual case), the move is refuted and we are done. If it says $>\alpha$, the bet failed and we re-search that move with the full window.

Code

int negascout(Node& n, int depth, int alpha, int beta) {
    if (depth == 0 || n.terminal()) return evaluate(n);
 
    bool first = true;
    for (Move m : orderedMoves(n)) {
        n.apply(m);
        int score;
        if (first) {
            score = -negascout(n, depth - 1, -beta, -alpha);
            first = false;
        } else {
            score = -negascout(n, depth - 1, -alpha - 1, -alpha);   // null window
            if (alpha < score && score < beta)                      // bet failed
                score = -negascout(n, depth - 1, -beta, -score);    // re-search
        }
        n.undo(m);
 
        alpha = max(alpha, score);
        if (alpha >= beta) break;                                   // cutoff
    }
    return alpha;
}

Complexity

• Same worst case as alpha-beta: $O(b^d)$
• Best case (perfect move ordering): $O(b^{d/2})$ — the alpha-beta optimum
• In practice: 10-20% fewer nodes than alpha-beta given good ordering; worse than alpha-beta given bad ordering, because of re-searches

Move ordering is everything

Negascout only pays off when the first move really is usually best. Without good ordering, the re-searches cost more than they save. The standard ordering tools are:

• transposition table move from a previous, shallower search;
• iterative deepening — search depth 1, 2, 3, …, using each result to order the next;
• killer moves — moves that caused a cutoff at the same ply elsewhere;
• history heuristic — a global score per move based on past cutoffs;
• MVV-LVA for captures in chess.

The family of alpha-beta refinements

Technique	Idea
Negamax	one code path instead of separate min/max
Negascout / PVS	null-window all but the first move
MTD(f)	all searches are null-window, driven by a bisection on the root value
Aspiration windows	start with a narrow window around the previous iteration’s score
Quiescence search	extend past the horizon on captures to avoid the horizon effect
Null move pruning	give the opponent a free move; if still winning, prune
Late move reductions	search later (presumed worse) moves at reduced depth

MTD(f) takes the null-window idea to its conclusion and is elegant, but is highly dependent on a good transposition table; PVS is the more robust default and is what most engines use.

Variants / Use Cases

• Alpha-Beta Pruning — the algorithm being refined
• Minimax — the foundation
• MCTS — the alternative when no good evaluation function exists
• Minimax — the topic page