Chess, Bitboards, and Benchmarks: From 24 Seconds to 11 Milliseconds

Perhaps the very first "proper" piece of software I wrote was a chess engine for one of my university courses, back in 2024. I was quite proud of it, and much of what I learnt while building it has carried me throughout my degree.

I was a bit bored a few weeks ago and, not wanting to prepare for my exams, I decided that now was probably a good time to jog old memories. Primarily, I was just curious to see what I've learnt in the past years and how it would shape my decisions if I were to start over. It would also help me understand how far I had come, and potentially expose more flaws in my thinking (it did). In summary, I ended up rewriting the entire engine.

The old engine needed 24 seconds to choose a move at depth 3. The new one reaches depth 10 in 11 milliseconds. Between those two numbers sit a benchmark harness, multiple measured steps, a neural network trained on 38.7 million positions, matches against Stockfish, a bot on Lichess, and a long list of ideas that did not work.

You can play against it Nhere.

Priors

Before I can even begin to explain the series of terrible decisions I made back then, I think I should still pay some tribute.

I named the first engine Horizon (after the horizon effect) and its last release, v5.2.3, should still be playable on Windows. I wrote it as a desktop chess app, with a built-in engine, written in C++, with raylib for the window, pieces, and sounds. This was the first mistake. My initial goal was to build a chess engine. I ended up with a chess app.

The release notes said:

In case you're able to run the engine at higher depth (depths > 5), do let me know.

I meant it as a polite request (I blamed the slow performance on my laptop...).

Anyway, going over the code again made things very obvious. A class called GameModes owned a GraphicalBoard, a ChessBoard and the engine. The ChessBoard held 64 pointers to pieces, and every piece carried its own texture and screen rectangle. The window drew the board it was given, and the engine searched on a copy of it.

The problems fell into four groups:

• Search: it played well only as Black, scored every checkmate the same and never detected stalemate.
• Rules: castling stayed legal after a rook had moved away and back.
• Memory: every node copied 64 heap objects and leaked captured pieces, so a game of 40 moves reached 1GB.
• Threading: making a move in the search set screen positions, and the engine thread was a loop that never slept and shared the board with the UI thread without a lock.

Baseline

I benchmarked this original engine by creating a small adapter that compiles the code against a stand-in raylib.h (with empty functions), and wrote a simple benchmark harness that it (and future improvements) could be tested against. The harness included 15 positions (searched to a fixed depth) and perft, which counts all the move sequences of a given length from a position¹. Correct counts are published for well-known positions².

At depth 3 it took 24 seconds on average, and at depth 4 I stopped waiting. Perft ran at about 70 thousand positions per second, and only 13 of 24 perft runs gave the correct count due to bugs in castling and promotion.

Optimisations

The baseline shows where the time goes. The board is 64 objects on the heap, and every node of the search copies them and leaks the captured ones. A move passes through string parsing and sets screen positions on the way. The search shuffles its moves and tests for checkmate at every node, and with no move ordering and no pruning it looks at nearly every move of the tree: 159,004 positions at depth 3.

Chess programmers have well-known answers to each of these. They fall into three groups: how the board is represented, how the search chooses what to look at, and how a position is evaluated. A benchmark says what a change costs, and a match says whether the engine plays better, and the two can disagree, so every technique gets both. A match is 200 games or more from random openings, with the colours swapped, at 50ms per move, and its score gives a rating difference through the logistic model of Elo³.

• Bitboards. A bitboard is a 64-bit integer with one bit per square: one integer holds all the white pawns, another all the black knights, and so on. The questions that a move generator asks all the time ("which squares does this pawn attack?", "is this square occupied?") become a shift and an AND⁴. A position can then be a small struct, and making a move copies it and changes the copy, so nothing has to be undone or freed. The search itself is plain negamax alpha-beta⁵.

• Magic bitboards. A rook, bishop or queen attacks along lines until a piece blocks the line, so the attacked squares depend on the pieces in the way. Walking each line takes a loop, and a magic bitboard replaces the loop with one multiplication and one table read⁶.

  // the squares a rook attacks, given all the occupied squares
  const Magic &m = rook_magics[square];
  return m.attacks[((occupied & m.mask) * m.magic) >> m.shift];

• Move ordering. Alpha-beta prunes more when the best move is searched first, and with a perfect order it searches about the square root of what plain minimax needs. The cheapest good ordering tries captures first, the most valuable victim taken by the least valuable attacker⁷, and then promotions.

• A transposition table. Different move orders can reach the same position, so a hash table keyed by a Zobrist hash can store a result and reuse it⁸⁹. It pays when it is reused, across the passes of iterative deepening and across the moves of a game.

• Quiescence search. A search to a fixed depth stops wherever the depth runs out, even in the middle of an exchange, and may conclude that a pawn was won when the opponent's next move captures the queen. This is the horizon effect¹⁰. Quiescence search fixes it by continuing with captures only, until the position is quiet¹¹.

• Iterative deepening and PVS. Iterative deepening searches depth 1, then 2, then 3, and so on. Each pass orders the moves by the result of the one before, and a move is always ready when the clock runs out¹². Principal variation search (PVS) assumes that the first move is the best, searches it with a full window and every other move with a zero window, and searches again only when one of them turns out to be better¹³.

• Pruning and reductions. Null move pruning passes the turn and cuts the branch if the position is still good enough¹⁴. Late move reductions search the moves that come late in the order to a smaller depth¹⁵. Killer moves and the history heuristic remember which quiet moves caused cutoffs, so that they are tried early¹⁶¹⁷, and a check extension searches one ply deeper when the side to move is in check.

The literature has many more techniques than these. Each one became a switch in the search options and had to pass the same gate: it had to solve all 1,404 mate puzzles, and then win a match against the engine without it, with a sequential test¹⁸ that stops as soon as it can tell whether the change is at least 10 Elo better.

• Exchange evaluation plays out the captures on one square, so that quiescence skips a capture that loses material¹⁹.
• Losing captures last tries the captures that lose material after the quiet moves.
• Futility pruning skips a quiet move near the leaves that cannot raise alpha²⁰, and reverse futility pruning cuts a position near the leaves whose static score is already far above beta²¹.
• Razoring sends a shallow position that is far below alpha straight to quiescence, and delta pruning skips a capture in quiescence that cannot reach alpha even with a margin.
• Late move pruning skips the last quiet moves of a shallow position, internal iterative reduction searches a position with no table move to a smaller depth, and singular extensions search the table move deeper when every other move is much worse.
• A logarithmic reduction table and a null move reduction by margin decide how much a reduction takes.
• Aspiration windows start each pass in a window around the score of the pass before it²², and counter moves order a quiet move by the move that came before it.

Results

Each engine in the table adds one idea to the engine before it.

• Bitboards. At depth 3, engine 01 took 0.82ms against 24,379ms, which is 29,560 times faster. The factor has two sources: 27 times fewer positions (5,849 against 159,004, because the old search shuffled its moves and tested for checkmate at every node), and about 1,000 times faster per position, from no memory allocation, string parsing or UI calls.
• Magic bitboards. One lookup is 26 to 29 times faster than walking the rays, but the whole search is only 1.3 to 1.4 times faster, because attacks are one part of the work and the rest did not change (Amdahl's Law)²³. Perft shows the two steps in one number: 70 thousand positions per second for the old generator, 27.8 million for bitboards with rays and 44.2 million with magic lookups, with all six positions counted correctly from engine 01 on.
• Move ordering. At depth 6 it cut the node count from 10,959,617 to 178,062 and the time from 1,150ms to 29ms. It was the largest gain after the first change, and it is a small change to the code.
• Quiescence search. It is 1.7 to 4 times slower at equal depth, but it won 92% of the points against the engine without it (180 wins, 8 draws, 12 losses).
• Iterative deepening and principal variation search. Together they are 1.4 to 3.3 times faster and won 59% of the points (98 wins, 39 draws, 63 losses).
• Pruning and reductions. They are 1.5 to 4.6 times faster and won 75% of the points (135 wins, 29 draws, 36 losses). Engine 07 reaches depth 10 in 80ms, where engine 06 needs 5,306ms.

These are the verdicts of the techniques, each against the engine without it. The chart has every change that was tried, and the table the 13 search changes.

Seven of the 13 were kept. Reverse futility pruning was the largest, with 0.582 in only 390 games and 63% fewer positions, and futility pruning scored 0.552 with 45% fewer. Delta pruning searched 14% fewer positions and did not play better, while aspiration windows search more and win more games. Positions per move are a cost, and they are not the quantity that wins. With the kept changes, engine 08 reaches depth 10 in 17ms, against 80ms for engine 07, and won 72% of the points against it (252 wins, 74 draws, 74 losses).

Evaluation and tuning

Tuning

So far, I had not touched the evaluation, and it was still what I started with: material and one table of bonuses for each piece, copied from the chess programming wiki²⁴. A quick method of improving the evaluation is to tune its parameters (the piece values and the tables of bonuses) on self-play games²⁵. This is done by letting the engine play against itself, keeping the quiet positions of its games, and labelling each one with the result of its game. A tuner then changes one number by one point, keeps the change if the error falls, and repeats until nothing helps.

I let the engine play 24,000 games against itself and kept every third quiet position, 695,000 in all. Tuning the tables alone scored 0.626 against the old numbers in 254 games, about 90 Elo. The tuned evaluation costs 133ns per position against 62ns and scored 65% of the points (236 wins, 49 draws, 115 losses). The engine with the tuned evaluation is engine 09.

Neural Networks

Modern chess engines rarely rely on a hand-written or tuned evaluation anymore. Instead they have moved to efficiently updatable neural networks (NNUE)²⁶ or other deep-learning based approaches²⁷. I took the NNUE route. The engine with the network is engine 10.

The network has an input for every combination of a piece and a square, 768 in all, and a position switches on at most 32 of them. The first layer, 128 numbers for each side, is therefore a sum of at most 32 rows of weights, and when a move is made one row comes out and another goes in. That is what makes it cheap enough for millions of evaluations per second. The weights are 16-bit integers, and training is in floating point.

The training data came from two sources: the engine itself, and published games of Leela Chess Zero²⁸. Self-play games gave each quiet position with the score of a search and the result of its game. After three rounds, each trained on the games of the network before it, the network scored 82% of the points against the tuned engine, about 270 Elo from one change. Leela's games come with the evaluation of a far deeper search. A network trained on those alone was about 180 Elo weaker than one trained on self-play games.

A recipe that trains a network in 6 minutes and a test of 300 games make questions cheap, so I asked a lot of them. Letting the number of pieces choose one of eight output layers scored +97. Giving the network the half of the board that holds the king, with a mirror of the files, scored +109, the best of these (the red dot), while eight king buckets had too many inputs for the data and lost strength. A second layer and threat inputs lowered the error, but slowed the engine so much that the strength did not follow. Across the 18 stronger networks a lower error went with more Elo only loosely, a correlation of about -0.6.

The chart below shows the time per move for each engine, at depths 3 and 6,

and this one shows the number of positions searched at each depth. The plain search grows by a factor of 10 to 16 for each ply, which is the effective branching factor, and each improvement lowers it.

Hardware optimisations

A few ideas that can make a fast program faster, rely on taking the hardware it runs on into account. The search ran at about 3.9 million positions per second on one core, and none of the three below changes a node count.

• Prefetching. The transposition table is far larger than the processor's cache, so reading an entry stalls the processor. The program asks for the entry as soon as a move is made, and the memory is on its way while the rest of the work is done. It was 3% faster at a table of 16MB.
• SIMD with a choice at start. The network sums rows of 16-bit weights, and AVX2 adds 16 of them at a time. The program has two versions of these functions, one for AVX2 and one for the base instruction set, and chooses between them when it starts, so a release binary does not have to guess the processor of its user. With the prefetch it was 12% faster.
• Compiler flags. Building with -mpopcnt -mbmi2 lets the slider lookup use the PEXT instruction of the processor in place of the multiplication of a magic number²⁹, which searches 5% to 12% more positions per second. It is a build option, because a processor without BMI2 cannot run the binary.

Strength

Against Stockfish

I played the engines against Stockfish 19, limited in strength with its UCI_LimitStrength and UCI_Elo options, 50 games at each level, and fitted a rating to the scores of each engine.

The old engine at depth 3 rates about the same as my plain new search at depth 3. The new code did not make depth 3 better. It made depth 3 take 0.8ms instead of 24 seconds, and that opened the door to depth 10. The scale is Stockfish's UCI_Elo, which is calibrated for long time controls and ends at 3190, so 2931 is not a rating-list rating, and a rating near the top of the scale is the least certain.

Per position my engine is faster than Stockfish, 4.2 million per second against 0.6 to 1.6 million per core, but Stockfish reaches depth 10 about 4.4 times sooner because it needs 2,300 positions where I need 45,163. I made each position cheap, and the strong engines make most positions unnecessary. The last aim of the ideation document, to beat Stockfish, turned out to be possible up to a point. Horizon rated 1132 on this scale at depth 3, and the final engine scores 95% against Stockfish limited to 2400, 71% at 2800 and 18% at 3190.

Puzzles as a second ruler

A match gives a wide interval from a few hundred games, so I wanted a cheaper ruler. The Lichess puzzle database has about 6.2 million puzzles. The engine plays the moves of the solver from an empty table, and a puzzle is solved when every move is right. A move is right when it is the solution move or any other move that gives checkmate.

Meridian v1.0.0

The final engine (after more training) is released as Meridian 1.0.0. Against engine 10, it scored:

The gain grows with the time, as one would expect from a better evaluation and a faster search together.

Takeaways

Comparing the two engines, what stands out is the assumption behind the first one. I put usability and readability first without understanding what I was trading them for, and I wanted strength without knowing that speed is what drives it. A plain minimax search with unlimited time would reach the same or better conclusions, but nobody has unlimited time, so speed matters, and speed alone is not enough either. It has to come with a search that looks only at what is needed, and that has to be built into the engine. The original project also taught me to learn on my own, alongside my coursework, and not only from what is taught, though I could not apply that to the project then, and this rewrite is probably my remedy for it.

Goal 8

The goal of building the best chess engine in existence still stands, but I no longer expect to reach it in one jump. The engine now plays on Lichess, and a framework for evaluating and improving it continuously has been written (meristats). The path from here is more structured: first beyond 3000 Elo, then the Top Chess Engine Championship (TCEC). Underneath it all, is the same endless, unending pursuit of knowledge.

The source code can be found at https://github.com/syedtaha22/meridian.