The architecture of a chess engine

Most people assume a chess engine thinks the way a person does. It doesn't, and the gap between the two is the whole story.

A strong human player looks at a position and asks questions. What is my opponent trying to do? Where are the weaknesses? Which pieces are sitting on the wrong squares? An engine looks at exactly the same position and asks something far blunter: what happens if I try everything?

The remarkable part isn't that this works. It's that it works quickly enough to beat the best humans who have ever lived.

When people first meet an engine like Stockfish, they tend to picture some sleek artificial mind behind the curtain, something that understands chess the way a grandmaster understands it. The truth is less romantic and a good deal more interesting. Modern chess engines are among the finest pieces of performance engineering ever written: search algorithms, caching strategies, heuristics and optimisation techniques, all bolted together and driven at a ferocious clock speed.

They are also, almost by accident, one of the best ways to understand a large slice of computer science.

The impossible problem

Start with the bad news. Chess is absurdly large.

From a typical middlegame position you have around twenty legal moves. Your opponent then has around twenty replies. Then you have twenty again, and so on down. Each layer multiplies the one before it, so the number of distinct positions doesn't grow so much as detonate.

Depth 1   ≈            20 positions
Depth 2   ≈           400 positions
Depth 3   ≈         8,902 positions
Depth 4   ≈       197,281 positions
Depth 5   ≈     4,865,609 positions

That is exponential growth, and exponential growth is the recurring villain of this entire article. Every extra layer of depth multiplies the work rather than adding to it. Drag the depth below and watch the count run away from you, then ask how long it would actually take to look at every position.

The job facing an engine, then, is not really to decide which move is best. It is to decide which moves are not worth looking at in the first place.

That distinction turns out to be everything.

Why brute force doesn't work

The obvious first instinct is to ask why we don't simply analyse every possible game and pick a line that wins. The answer is that there are more possible chess games than there are atoms in the observable universe. Estimates vary, but the total sits somewhere around ten to the power of a hundred and twenty, a figure known as the Shannon number. The observable universe holds roughly ten to the power of eighty atoms.

Possible chess games   ≈ 10^120   (the Shannon number)
Atoms in the universe  ≈ 10^80

The gap between those two numbers is not the kind of thing intuition is built to handle. Even if every atom in the universe were itself a supercomputer that had been running since the Big Bang, you would not be close. The engine cannot search everything. It has to cheat.

The rest of this article is really just a catalogue of the cheats, in roughly the order someone discovers they need each one.

Building a naive engine

Picture the simplest engine you could write. For every legal move: make the move, score the resulting position, keep the highest score.

function findBestMove(position) {
  let bestScore = -Infinity;
  let bestMove = null;

  for (const move of legalMoves(position)) {
    const score = evaluate(applyMove(position, move));

    if (score > bestScore) {
      bestScore = score;
      bestMove = move;
    }
  }

  return bestMove;
}

Congratulations: you have built a genuinely terrible chess engine. It will grab a free piece. It will spot a one-move tactic. It will also cheerfully give up its queen for a pawn, provided the bill doesn't arrive until the move after the one it bothered to look at.

The engine has no way to think ahead. Fixing that is where the real work, and the real cost, begins.

Search trees

To see further into the future, the engine has to model it. A move produces a position. That position invites replies. Those replies invite responses of their own. What you end up with is a tree.

position
├── move A
│   ├── reply A1
│   └── reply A2
├── move B
│   ├── reply B1
│   └── reply B2
└── move C
    └── reply C1

The deeper you search, the stronger the engine plays. The deeper you search, the more impossible the arithmetic from two sections ago becomes. Almost every chess engine ever written is, at heart, a long argument with that single tension.

Evaluation functions

At some point the engine has to stop descending and make a judgement, because the game is far too large to play all the way out to checkmate. It needs a way to look at a position it has only half-explored and estimate whether it is good or bad. That estimate is the evaluation function.

The simplest version is just a weighted sum:

score =
  material +
  kingSafety +
  mobility +
  pawnStructure;

Material is the easy part, and the textbook values have barely shifted in a century:

Queen  = 9
Rook   = 5
Bishop = 3
Knight = 3
Pawn   = 1

A side with an extra queen is, generally speaking, having a nice day. From there the function grows teeth: piece activity, king safety, space, passed pawns, control of key squares. Hundreds of small observations, each reduced to a number and folded into the total. The engine never understands any of it. It understands the number.

Making the engine stupid

The fastest way to feel how an evaluation function works is to break one on purpose.

Suppose we decide a queen is worth fifteen instead of nine. Nothing else changes, just the one constant. The engine promptly develops a personality, and not a pleasant one. It hoards its own queen, hunts the enemy's, and happily wrecks its position and its pawn structure to do either. Every objectively bad decision traces back to a single number we nudged.

Take a position where one side has a queen and the other has a rook, a bishop and a knight, then drag the queen's value and watch the engine's verdict on that same fixed position flip from sober to deranged.

There is a lesson hiding in that slider, and it is not really about chess. The behaviour of an intelligent-looking system is mostly a reflection of how it is told to keep score. Change what you reward and you change what it does. Engineering organisations rediscover this constantly, usually the hard way, the first time a well-meaning metric teaches everyone to do the wrong thing.

Alpha-beta pruning

By now the engine can search and it can evaluate. It is also painfully, uselessly slow. This is where one of the most elegant ideas in computer science walks in.

Alpha-beta pruning. The concept is almost embarrassingly simple. Imagine sitting through a terrible film. Twenty minutes in, you already know it's awful, and you do not need to watch the remaining two hours to confirm the rating. The verdict is in. Carrying on would only be gathering evidence for a conclusion you have already reached.

Alpha-beta does the same thing to the search tree. If it can already prove that a branch is worse than something it has safely banked elsewhere, it abandons that branch. It does not matter exactly how bad the branch turns out to be; once it is provably not the best, the rest of it is wasted breath.

Step through it below. The same tree, evaluated with and without pruning, reaches the same answer. One of them simply refuses to do the pointless work.

The payoff is dramatic. A well-implemented alpha-beta search can examine orders of magnitude fewer positions and arrive at exactly the same move. Not a better move. The same move, just far faster.

Performance engineering rarely gets more satisfying than the identical answer for a fraction of the work.

Why move ordering matters

There is a strange and wonderful consequence buried in that last section. Because alpha-beta can only prune once it has found something good to compare against, the order in which you examine moves suddenly matters enormously.

Two engines can run the identical algorithm and reach the identical answer. The one that happens to look at the strongest move first finds its cut-offs early and prunes huge swathes of the tree. The one that looks at the weakest move first does almost no pruning at all, and grinds through a vast amount of pointless work for the same result. Flip the ordering toggle in the demo above and watch the number of evaluated leaves swing.

This is one of the oldest patterns in the discipline. Finding the right answer matters. Finding it quickly matters more, and surprisingly often the difference between the two is nothing more than the order you chose to look in.

Caching chess

Here is another piece of waste worth eliminating. You reach a position, you evaluate it, you move on. Five moves later, through a completely different sequence, you arrive at the very same position. Do you evaluate it again from scratch? Obviously not. You already know the answer.

That observation is the whole basis of the transposition table - a cache by another name.

position  ->  hash  ->  key  ->  stored evaluation

When the engine meets a position it has already analysed, it looks up the stored result instead of recomputing it. In a game where different move orders constantly collapse into the same arrangement of pieces, the saving is enormous.

If this is starting to sound familiar, it should. It is exactly the idea behind database caches, API caches, CDN caches and the browser cache sitting in front of you right now. Different domain, identical trick. I've argued before that caching is easy until it isn't, and the chess version is no exception: a cache is a controlled lie. The stored value isn't reality, it is reality as it was the last time anyone checked.

Chess engines get away with the lie because a given position's value never changes; the past stays true. Business systems are far less obliging, which is where the difficulty always creeps back in. The underlying trade is the same everywhere, though. Spend time recomputing, or spend memory remembering. Most systems, chess engines included, end up buying a bit of both.

Then neural networks arrived

For decades, engines leaned on evaluation functions tuned by hand. Developers spent careers nudging weights and refining heuristics, and the strongest programs were, in a real sense, monuments to human chess knowledge encoded as numbers.

Then machine learning turned up. Modern Stockfish scores positions with a technique called NNUE, an efficiently updatable neural network small and fast enough to run inside the search without dragging it to a crawl. The shape of the engine became, very roughly, a single substitution:

classical:  search + pruning + caching + handcrafted evaluation
modern:     search + pruning + caching + neural evaluation

Notice what didn't change. The search stayed. The pruning stayed. The caching stayed. The overwhelming majority of the engine stayed exactly where it was. The neural network replaced one component and left the architecture untouched.

That is worth holding onto when the conversation turns to AI more generally. The breakthrough is usually narrower than the headline suggests. The old machinery survives; the new capability gets slotted into a socket that was already there. It's the same reason I keep arguing that you shouldn't let AI borrow your brain: the impressive new layer sits on top of a great deal of unglamorous structure that still has to be understood and maintained by someone who knows how it works.

Chess engines are really search engines

This is the part people tend to miss. The lesson of the chess engine was never really about chess. It is about search.

The engine's apparent intelligence is an emergent property of a handful of plain mechanisms working together. Search the tree efficiently. Refuse to do provably useless work. Reuse answers you have already computed. Look at the promising moves first. Judge every position by a consistent yardstick.

apparent intelligence  =  search + pruning + caching + heuristics

Each ingredient is, on its own, fairly mundane. Run them together at a few million positions a second and the result feels uncannily like understanding. Anyone working in modern AI should find that familiar, because a great deal of what currently passes for intelligence is exactly this: simple mechanisms, composed carefully, operating at a scale the human imagination was never built to picture. The same performance instincts that keep a trading screen under a hundred milliseconds are the ones that turn a hopeless search space into a grandmaster.

The grandmaster and the machine

A grandmaster sees ideas: a weak square, a long-term plan, an imbalance worth steering towards for the next twenty moves. An engine sees possibilities - millions of them, almost none of them any good.

The human searches selectively because the human has no choice; the conscious mind simply cannot brute-force a position. The engine searches selectively because, over decades of being made faster, it has been taught that it has no choice either. They arrive, more and more often, at the same square. The journeys could not be less alike.

And that, in the end, is the part I find most interesting. We tend to file intelligence under mysterious: something magical, something that resists explanation. The chess engine disagrees. Its strength is search, optimisation, caching, evaluation and a refusal to waste effort, and those same five ingredients turn up everywhere in serious software.

Which means a modern chess engine isn't only a chess engine. It is one of the cleanest demonstrations of engineering trade-offs ever built, and somewhere inside a machine grinding through millions of positions a second is a lesson that reaches a long way past sixty-four squares.

Further reading

• Programming a Computer for Playing Chess (Shannon, 1950): the paper that started all of it, including the back-of-an-envelope estimate that now carries his name.
• Stockfish: the strongest open-source engine going, and refreshingly readable if you want to watch the theory survive contact with real C++.