Testing move generation first in a Rust chess engine

When you start writing a chess engine, it is tempting to jump straight to alpha-beta pruning, killer moves, and evaluation tuning. The problem is that a single edge-case bug in move generation poisons every search ply above it. Miss a horizontal pin during an en-passant capture, or allow castling through an attacked square, and the search tree quietly fills up with illegal positions.

While building my Rust Chess Engine without external crates, I refused to touch search heuristics until move generation matched known perft counts down to the last leaf node.

Verifying 119,060,324 positions

The board uses twelve u64 piece bitboards alongside a 64-square mailbox array and incremental Zobrist keys. To make sure fast make/unmake state updates never drifted out of sync, I wrote a second, much slower move generator that clones the board struct on every move. Automated tests run both generators against tricky tactical positions and verify the full 119,060,324-node perft(6) tree from the starting board.

Whenever the two generators disagreed on a count, dividing the perft tree by root move isolated the exact broken position in seconds.

Portable sliding-piece lookups

Modern x86 chips often use the BMI2 PEXT instruction to index rook and bishop attack tables in a couple of cycles. Relying on hardware PEXT makes binaries awkward to ship across older Intel chips or ARM laptops, so I used precomputed software-PEXT occupancy tables instead. Lookup speed stayed close to magic bitboards while compiling cleanly everywhere with cargo build --release.

Search on a solid base

Once perft stopped finding bugs, adding Principal Variation Search (PVS), quiescence search, transposition tables with mate-distance normalization, MVV-LVA, static exchange evaluation, and late move reductions went much faster than I expected. Rust’s borrow rules also caught a mistake I used to make in C++: holding a reference into a transposition table slot while a recursive call overwrote it.

I ended up taking the same approach later in Ro-Physics. Get the low-level rules right under a repeatable test harness first, then worry about speed.


Linked mentions

You might also enjoy