How the Checkers AI Works: Negamax, Alpha-Beta and Forced Captures

The opponent on LK Forge Checkers (American / English draughts) is a genuine game-tree search engine — the same family of algorithm behind chess programs — running entirely in your browser. Checkers has a feature that makes it especially well-suited to search, and the engine leans on it.

Negamax with alpha-beta pruning

To choose a move the engine runs negamax — minimax in its compact single-function form, valid because checkers is zero-sum — with alpha-beta pruning. It plays possible futures out for both sides, scores the leaf positions on material and king count, keeps track of the best each side can already force, and discards any line that provably cannot beat it.

Compulsory captures do the pruning for you

Here is the twist that makes checkers cheap to search: captures are mandatory. Whenever a jump is available, it is the only kind of move allowed — and multi-jumps chain automatically. That collapses the number of legal moves in exactly the sharp, tactical positions that matter most, so the engine can look several plies deeper for the same effort. A branching factor that is small to begin with, and often forced, is why a modest search already plays a strong tactical game.

// mandatory captures: if any jump exists, only jumps are legal
function legalMoves(pos) {
  const jumps = captureMoves(pos);
  return jumps.length ? jumps : simpleMoves(pos);   // forced when a jump exists
}

Capture-aware quiescence

A fixed-depth search must not stop counting in the middle of an exchange. So at the leaves the engine keeps following forced jump sequences until none remain — a capture-aware quiescence search — so the score reflects the end of a multi-jump, not its first step. Men that reach the far row are crowned as kings that move and capture in every diagonal direction, and the evaluation counts them at a premium.

How much is one more move of lookahead worth?

We measured it by pinning the shipped engine to a fixed depth and self-playing 120 colour-balanced games between adjacent depths. As in most games, the first extra ply is worth a fortune — +546 Elo, because a depth-1 engine barely beats random play — and every later ply adds a smaller, game-specific amount.

That is the whole engine: forced-capture move generation that keeps the tree small, negamax with alpha-beta, and capture-aware quiescence so exchanges are never left half-counted. Want to watch the search decide? Read minimax and alpha-beta, step by step, or compare four engines in What One Ply of Search Is Worth.

FAQ

How does the Checkers AI choose a move?

The Checkers AI runs a negamax game-tree search with alpha-beta pruning and a capture-aware quiescence search. It plays out sequences of moves for both sides, scores the resulting positions on material and king count, and picks the move with the best guaranteed outcome. Everything runs in your browser; nothing is sent to a server.

Why do compulsory captures make the AI stronger and faster?

In checkers a capture is mandatory, so whenever one exists the player has far fewer legal moves to consider. That narrows the search tree dramatically, which lets the engine look further ahead in the same amount of time — one of the reasons a checkers search reaches useful depth so cheaply. The forcing lines this produces are also exactly where tactics happen, so even a modest search catches multi-jump combinations that a slower, unconstrained search would need extra depth to find.

What is capture-aware quiescence?

At the leaves of the main search the engine keeps following forced jump sequences until none remain, so it never stops counting in the middle of a multi-jump exchange. Without it the search could grab a piece and miss that it is jumped straight back. This capture-aware quiescence pass only extends on forced jumps, so it stays cheap while keeping the evaluation accurate at exactly the moments a fixed-depth cutoff would otherwise misjudge.

How much does one more move of lookahead help in checkers?

In a seeded self-play benchmark, the first extra ply of checkers search was worth +546 Elo, because a depth-1 engine barely beats a random mover. Each later ply added far less — between +49 and +100 Elo per step out to depth 7. That steep early payoff is why even Medium, which only searches a few plies deep, already plays a solid tactical game.