A chess engine in Rust

Crust is a small chess engine I wrote in Rust over a few weeks this October. It generates moves with bit operations, looks four moves ahead and runs in the browser through WebAssembly. You can play against it here.

The board as numbers

A chessboard has 64 squares, and a u64 has 64 bits. Crust keeps one number per piece type and color, where a set bit means a piece stands on that square. The white knights are one number, the black pawns another, and every empty square is just the bits that none of them set.

The payoff is that moves become arithmetic. Shifting a number by one moves every piece on it one file over; shifting by eight moves them a rank. Here are the attacks of every knight on the board at once, with no loop and no lookup:

fn knight_attacks(knights: u64) -> u64 {
    let l1 = (knights >> 1) & 0x7f7f7f7f7f7f7f7f;
    let l2 = (knights >> 2) & 0x3f3f3f3f3f3f3f3f;
    let r1 = (knights << 1) & 0xfefefefefefefefe;
    let r2 = (knights << 2) & 0xfcfcfcfcfcfcfcfc;
    let h1 = l1 | r1;
    let h2 = l2 | r2;
    (h1 << 16) | (h1 >> 16) | (h2 << 8) | (h2 >> 8)
}

The masks stop pieces on the edge from wrapping around to the other side of the board. Everything else is shifting a knight one file and two ranks, or two files and one rank.

Bishops, rooks and queens slide until something blocks them. For those Crust uses a Kogge-Stone fill, which spreads each piece along a direction by one square, then two, then four, stopping at the first occupied square. Three steps cover the whole board.

Counting to check

Move generators are easy to get almost right. The standard test, called perft, counts every position reachable a given number of moves from the start and compares it with known results: 20 after one move, 400 after two, 8,902 after three and 197,281 after four.

Crust matches the first three exactly. At four it finds 197,698, which is 417 too many, so a few illegal moves still slip through. Moves are generated freely and then thrown away if they leave the king under attack, and that check is where the remaining bugs live.

Thinking ahead

To choose a move, Crust searches four moves deep with alpha-beta pruning, which skips any line that can’t beat one it has already found. Positions are scored by material alone: a pawn is worth 1, a knight or bishop 3, a rook 5 and a queen 9.

That is enough to take free pieces and avoid losing its own. It knows nothing about position, though, so in quiet moments its moves can look arbitrary.

In the browser

The engine compiles to WebAssembly with wasm-bindgen, and a small Svelte page draws the board. When you pick up a piece, the squares it can reach are marked. The search runs in a web worker, so the page stays responsive while Crust thinks.

The board crosses between JavaScript and Rust as JSON on every call. It is not the fastest way to do it, but it costs almost nothing next to a four-move search.

Play a game or read the source on GitHub.