Chess engine basics: alpha-beta search, quiescence and evaluation

Look ahead with negamax

Chess is a zero-sum game: what is good for White is exactly as bad for Black. That lets an engine use negamax, a compact form of minimax. To score a position for the side to move, try every legal move, ask “how good is the resulting position for my opponent?”, negate that score, and keep the best. Repeat until you reach the depth limit, then call an evaluation function.

The trouble is the size of the tree. A typical position has around 30 legal moves, so looking four plies (half-moves) ahead means on the order of 30⁴, about 810,000 positions, and every extra ply multiplies that again. Everything else in this article is about looking at fewer of them.

Alpha-beta pruning

Alpha-beta keeps two numbers while searching: the best score the side to move is already guaranteed (alpha) and the best score the opponent is already guaranteed (beta). If a move turns out to be so good for the mover that the opponent would never allow the position to arise, the search stops examining the rest of that move's siblings. That is a cutoff, and it is safe: the result is identical to plain minimax, just faster.

How much faster depends on move ordering. If the best move is tried first, most of the other moves are cut off almost immediately. Chessko orders moves with the classic set of cheap heuristics:

• Transposition-table move: the best move found for this position in an earlier, shallower search goes first.
• MVV-LVA (most valuable victim, least valuable attacker): capturing a queen with a pawn is tried before capturing a pawn with a queen.
• Killer moves: quiet moves that caused a cutoff at the same depth in a sibling branch are tried early.
• History heuristic: a running count of how often each quiet move has caused cutoffs, so moves that keep working keep being tried early. This is a small piece of online learning inside the search.

Iterative deepening and the clock

Instead of searching straight to depth 4, the engine searches depth 1, then 2, then 3, then 4. That sounds wasteful, but each shallow pass is cheap compared with the next one, and it pays for itself twice. The best move from depth n becomes the first move tried at depth n+1, which sharpens the ordering. And because there is always a finished result from the previous depth, the search can obey a time budget: when the deadline arrives it stops and plays the best move from the last completed depth. Chessko checks the clock inside the search, including inside quiescence, so a long capture sequence cannot overrun it.

Transposition tables and Zobrist hashing

The same position can be reached by different move orders (1.e4 Nf6 2.Nc3 and 1.Nc3 Nf6 2.e4 give the same board). A transposition table caches the result of searching a position, so the second visit is free. To look positions up quickly, each one is reduced to a number with Zobrist hashing: every (piece, square) pair gets a fixed random number, and the position's key is the XOR of the numbers for every piece on the board. Making a move only XORs out the piece from its old square and XORs it into the new one, so the key is updated incrementally instead of recomputed.

Chessko builds a key of roughly 53 bits from two 32-bit halves. That is the largest integer a JavaScript number can hold exactly, so it avoids BigInt and string keys in the hot loop.

Quiescence search: not stopping mid-fight

If the search stops at depth 4 right after your queen takes a pawn, the evaluation sees a free pawn. It cannot see that the queen is about to be recaptured on the next move. This is the horizon effect. Quiescence search fixes it: at the depth limit, instead of evaluating immediately, the engine keeps searching captures only, until the position is quiet. Only then does it score the board.

Evaluation: turning a board into a number

The leaf positions need a score, in centipawns (hundredths of a pawn), from the side to move's point of view. Chessko's hand-tuned evaluation adds three things: material (pawn 100, knight 320, bishop 330, rook 500, queen 900), piece-square tables (a knight on the rim is worth less than in the centre) and mobility (how many squares the pieces can reach), plus a small bishop-pair bonus.

That is enough to play recognisable chess at a few plies of depth. The interesting part is what happens when the evaluation is learned instead: see machine learning in a chess engine. And for an engine that has all of the above at industrial strength, see Stockfish in the browser.

Quick answers

What is alpha-beta pruning in chess?

Alpha-beta pruning is an optimisation of minimax search. It skips branches that cannot change the final decision because the opponent already has a better alternative elsewhere, so the engine reaches the same move while examining far fewer positions.

What is quiescence search?

Quiescence search extends the search at the depth limit by following capture moves only, until the position is quiet. It avoids the horizon effect, where an engine misjudges a position because it stopped in the middle of an exchange.

What is a transposition table?

A transposition table is a cache of positions already searched, keyed by a hash of the board (usually a Zobrist hash). When the same position is reached by another move order, the engine reuses the stored result instead of searching it again.