Minimax

For partizan games (different moves per player) or games with scores, where Grundy numbers do not apply: one player maximises, the other minimises.

$V(s)=\{\begin{array}{ll}\text{eval}(s)& s\text{ terminal or at the depth limit}\\ {\max }_{t}V(t)& \text{maximiser to move}\\ {\min }_{t}V(t)& \text{minimiser to move}\end{array}$

Negamax — one code path

Because $\min (a,b)=-\max (-a,-b)$, the two cases collapse if every value is expressed from the perspective of the player to move:

int negamax(Node& n, int depth) {
    if (depth == 0 || n.terminal()) return evaluate(n);   // from n's mover's view
    int best = -INF;
    for (Move m : n.moves()) {
        n.apply(m);
        best = max(best, -negamax(n, depth - 1));
        n.undo(m);
    }
    return best;
}

Halves the code and removes an entire class of sign errors.

Alpha-beta pruning

Prune branches that cannot affect the result. See Alpha-Beta Pruning.

int alphabeta(Node& n, int depth, int alpha, int beta) {
    if (depth == 0 || n.terminal()) return evaluate(n);
    for (Move m : orderedMoves(n)) {
        n.apply(m);
        alpha = max(alpha, -alphabeta(n, depth-1, -beta, -alpha));
        n.undo(m);
        if (alpha >= beta) break;                          // cutoff
    }
    return alpha;
}

With perfect move ordering this searches $O(b^{d/2})$ nodes instead of $O(b^d)$ — effectively doubling the reachable depth. With random ordering the gain is much smaller, which is why move ordering matters more than any other optimisation.

Move ordering — the highest-leverage optimisation

Technique	Idea
Iterative deepening	search depth $1,2,3,\dots$; use each result to order the next
Transposition table	cache positions by hash; the stored best move orders the next search
Killer moves	moves that caused a cutoff at the same ply elsewhere
History heuristic	a global per-move score based on past cutoffs
Domain heuristics	captures first, checks first, central squares first

Iterative deepening sounds wasteful but is not: the last ply dominates the node count, so re-searching shallower depths costs $O(1/(b-1))$ extra — and the ordering it provides more than pays for itself.

Refinements

Technique	Idea
Negascout / PVS	null-window search for all but the first move
MTD(f)	all searches are null-window, driven by bisection
Aspiration windows	start with a narrow window around the previous 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 moves at reduced depth
Transposition table	avoid re-searching identical positions

Transposition tables and Zobrist hashing

uint64_t zobrist[BOARD][PIECES];                          // random 64-bit values
// hash ^= zobrist[square][piece] on placing or removing a piece

Zobrist hashing makes the position hash incrementally updatable in $O(1)$ per move — XOR the piece out of the old square and into the new one. This is what makes transposition tables practical, and the same trick hashes any set that changes by single-element updates.

When to use what

Situation	Method
Impartial game, W/L only	Grundy numbers
Partizan, small state space	memoised minimax
Scored game on an array	advantage DP
Large tree, good evaluation available	alpha-beta + ordering
Large tree, no good evaluation	MCTS
Proving a forced win exists	proof-number search
Positions can repeat (draws)	retrograde analysis
Chance nodes	expectiminimax

Expectiminimax

With randomness, add chance nodes that take the expectation:

$V(\text{chance})={\sum }_t{p}_{t}V(t).$

Alpha-beta pruning is much weaker here (bounds propagate poorly through expectations); “star” pruning variants exist but the practical answer for games with chance is usually MCTS.

See also: Alpha-Beta Pruning · Minimax Algorithm · Game DP