Negamax Framework, in depth: the side-to-move contract, window negation, fail-soft bounds, transposition-table flags, mate scores and PVS measured

The side-to-move contract

Every negamax engine rests on one rule: every score is from the point of view of the side to move at the node where it is computed. A positive number means good for whoever is about to play. Everything else follows from it.

• The evaluation function must return a side-relative score. If your evaluator naturally scores for White, wrap it as return e if side == WHITE else -e. That one line is the most common negamax bug when it is missing or applied twice.
• A terminal loss for the side to move scores −MATE + ply, because the side to move is the one that has been checkmated. Adding the ply makes slower losses and faster wins score better.
• The game must be zero-sum, with players strictly alternating. If a move can leave the same side to move (a pass in some games, or a multi-part turn), negate only when the side actually changes.

def negamax(pos, depth):
    if depth == 0 or pos.is_terminal():
        return pos.evaluate()              # side-to-move relative
    best = -INF
    for move in pos.moves():
        pos.make(move)
        best = max(best, -negamax(pos, depth - 1))
        pos.unmake(move)
    return best

Deriving the negated window

Alpha-beta passes a window (α, β): α is what the side to move is already guaranteed elsewhere, and β is the most the opponent will allow. A child returns v from its own point of view, so the parent's score is −v. The parent cares only whether α < −v < β. Multiplying through by −1 flips the inequalities: −β < v < −α. So the child is searched with window (−β, −α). The bounds swap places as well as signs, and writing (−α, −β) is a classic bug that still returns plausible numbers.

The cut-off test is then the same at every node. If −v ≥ β, the opponent already has a line that holds the side to move to β or less, so they will never enter this position, and the remaining moves can be skipped. If −v > α, α rises, and later children are searched with the tighter window (−β, −α).

Fail-hard versus fail-soft

There are two ways to return from a node whose true value lies outside the window. Fail-hard clamps: it returns exactly α on a fail-low and exactly β on a fail-high. Fail-soft returns the best score it actually saw, which may lie outside (α, β) but is still a valid bound.

def alphabeta(pos, depth, alpha, beta):          # fail-soft negamax
    if depth == 0 or pos.is_terminal():
        return pos.evaluate()
    best = -INF
    for move in ordered(pos.moves()):
        pos.make(move)
        score = -alphabeta(pos, depth - 1, -beta, -alpha)
        pos.unmake(move)
        if score > best:
            best = score
            if score > alpha:
                alpha = score
                if alpha >= beta:
                    break                        # fail high: best is a lower bound
    return best                                  # best <= alpha_orig: an upper bound

Both versions visit the same nodes in a pure alpha-beta search. On 20 random trees with branching 8 and depth 6, both averaged 13,560 nodes, against 299,593 for plain negamax. The difference is in the information returned. On one tree with true value −7, a window placed above the truth, (+20, +40) relative to it, made fail-hard return +20 ("at most +20"). Fail-soft with children ordered by a static estimate returned +12 ("at most +12"). With a window below the truth, at (−40, −20), fail-hard returned −20 and ordered fail-soft −19. In tree order, fail-soft happened to return exactly the window edges on this tree, so the gain is not guaranteed, but it is never worse. Tighter bounds help everything that consumes them. Aspiration windows re-search from a closer starting point, and transposition-table entries cut off more often later.

Ordering matters far more than either choice. Sorting children by a cheap static estimate cut fail-soft from 13,560 to 2,691 nodes on the same trees, five times fewer. Ordering here meant searching the child whose own estimate is lowest first, since that child is best for the parent.

Transposition tables in negamax form

A transposition table caches results by position hash, usually a Zobrist hash. In negamax every entry is stored from the side to move at that node, which is also how it is probed. No extra negation is needed, provided the hash includes the side to move. The flag depends on the window the node was searched with:

MATE, MAX_PLY = 30000, 256

def to_tt(score, ply):        # make mate scores relative to this node
    if score >  MATE - MAX_PLY: return score + ply
    if score < -MATE + MAX_PLY: return score - ply
    return score

def from_tt(score, ply):      # make them relative to the root again
    if score >  MATE - MAX_PLY: return score - ply
    if score < -MATE + MAX_PLY: return score + ply
    return score

# store, after searching with original window (alpha0, beta)
flag = UPPER if best <= alpha0 else LOWER if best >= beta else EXACT
tt[key] = (depth, flag, to_tt(best, ply), best_move)

# probe, before searching
d, flag, s, mv = tt[key]
if d >= depth:
    s = from_tt(s, ply)
    if flag == EXACT or (flag == LOWER and s >= beta) or (flag == UPPER and s <= alpha):
        return s

Two details cause most bugs. First, compare the result with the original α. α rises during the loop, so testing against the final α marks every fail-low as exact. Second, mate scores encode distance from the root (MATE − plies to mate). The same position reached at a different ply has a different distance from the root, so store the score relative to the node and convert it back on probe, as above. Skipping this makes engines report the wrong mate length, or prefer a longer mate and never deliver it. Even with the table right, a hit can be wrong when the stored result depended on repetition history that the new path does not share. Most engines accept that small error.

Null windows: PVS and NegaScout

Principal variation search (PVS), and Reinefeld's almost identical NegaScout, assumes that move ordering is good. The first child gets the full window. Every later child is tested with a null window (α, α + 1), which can only answer "better than α or not". Only when the test fails high inside the window is that child re-searched with the full window.

for i, move in enumerate(ordered(pos.moves())):
    pos.make(move)
    if i == 0:
        score = -pvs(pos, depth - 1, -beta, -alpha)
    else:
        score = -pvs(pos, depth - 1, -alpha - 1, -alpha)      # null window
        if alpha < score < beta:
            score = -pvs(pos, depth - 1, -beta, -score)       # re-search
    pos.unmake(move)
    # ...same best/alpha/beta bookkeeping as fail-soft alpha-beta

In this model PVS did not win. Its re-searches cost slightly more than its null windows saved, likely because static-estimate ordering finds the best move first only some of the time. PVS pays off when ordering is very good, which in real engines comes from iterative deepening, a transposition-table best move and killer moves, and when the table makes re-searches cheap. Measure it in your own engine before keeping it. For scale, the theoretical best case for alpha-beta is b^⌈d/2⌉ + b^⌊d/2⌋ − 1 = 1,023 leaves here, against 262,144 leaves in the full tree.

Draws and contempt

Draws are where side-relative scoring needs care. A draw is 0 for both sides only if the engine is indifferent to it. With contempt, the engine scores a draw as −c for itself, which is +c for the opponent. In negamax the draw score therefore depends on who is to move: -contempt if pos.side == engine_side else +contempt. Returning a fixed −c everywhere gives the engine contempt on its own plies and love of draws on the opponent's. Repetition detection must also run before the table probe, so a cached score from a non-repeating path does not hide a draw.

Where negamax stops applying

Negamax depends on strict zero-sum alternation, and it breaks when either assumption fails.

• Chance. With dice or card draws, a chance node averages its children. That can be written in negamax form, but alpha-beta cut-offs at chance nodes need known bounds on the evaluation. Ballard's Star1 and Star2 pruning provide them. Plain negamax with pruning is wrong there.
• More than two players. Negation has no meaning. Use max^n, with a score vector per node, or the paranoid assumption that everyone else is one coalition.
• Non-zero-sum payoffs. If both players can gain together, the opponent is not minimising your score, and minimax play is overly pessimistic.
• Huge branching, weak evaluation. Monte Carlo tree search usually beats alpha-beta, as in Go. It still uses the same side-to-move convention when it backs up values.

Testing a negamax engine

A sign error rarely crashes anything. The engine just plays badly. So test negamax against an implementation whose correctness is obvious. The harness here builds random trees with depth 1 to 5 and branching 1 to 4, and computes plain two-function minimax from White's point of view, with leaf scores converted to White's view. It then checks that six variants return the same root value: plain negamax, fail-hard alpha-beta, fail-soft alpha-beta with and without ordering, and PVS with and without ordering. Over 2,000 trees there were 0 mismatches. Keep that test, and add invariants that apply to real positions. A position and its colour-mirrored twin must get the same score, and a full-window search must return the same value as a search whose window contains that value. The minimax deep dive shows how to obtain exact game values for small games, which make the strongest oracle.

Operational guidance and trade-offs

Operationally, keep one search function with a mode flag, not separate copies for each variant, because the copies drift. Log node counts per iteration and the fail-high rate on the first move, a direct measure of ordering quality. Higher is better, so track how it moves as you change ordering. When you switch from fail-hard to fail-soft, re-run the differential test, since the table now stores different bounds. Decide the trade-offs by measurement. Fail-soft costs nothing and gives better bounds. PVS needs good ordering. Aspiration windows save time when scores are stable and waste it on volatile positions.

What to do next

1. Write the side-to-move evaluation wrapper and a unit test showing that the same position evaluates to e for one side and −e for the other.
2. Implement fail-soft alpha-beta in negamax form and run the differential test against two-function minimax on 2,000 random trees.
3. Add a transposition table that stores the original-α flag, then test mate positions at several plies to confirm the reported mate distance stays correct.
4. Add PVS behind a flag and compare node counts with and without it on your real positions.
5. Implement contempt as a side-dependent draw score and check it from both sides.
6. Log the first-move fail-high rate each iteration and use it to drive move-ordering work.