The tree of useless optimization yields questionable fruit.

For the last two years, I’ve been building a chess engine called Fiddler. It’s not very good by chess engine standards, but that’s not the point - I mostly work on it for funsies.

Right now, I’m reworking my move generator to more heavily use static, precomputed data rather than runtime generation. Most recently, I’m moving from dynamically generating and heap-allocating the magic move generation table to making it a statically allocated constant. Along the way, I’ll take this opportunity to explain how magic move generation works, and hopefully have a little fun.

Update 2023-06-22: I’ve added a few updates to handle questions that people in the comments on the Orange Website found confusing.

A crash course in magic moves

Chess engines are usually extremely high-performance pieces of software, and their move generators are some of the most high-performance parts of them. Most move generators can generate hundreds of millions of moves, per core, per second. Mine included!

The majority of moves are made by sliding pieces - the bishop, rook, and queen - so we’ll dedicate most of our effort toward making that fast. The most naive approach would be to represent a board as an array of pieces, and then, for each piece, iterate outward along a ray, adding moves until we encounter a blocker. The problem with that approach is simply that it’s far too slow. In the worst case, finding the set of legal moves for a queen on E4 would require 27 different array accesses - and that’s just the moves for one piece! We’re going to need a different approach.

Bitboards

We can start by representing the occupancy of a board using a bitboard: a set of squares represented by a unique 64-bit integer. Convention dictates that the least-significant bit should be set if the square A1 is occupied, the second-least-significant to represent B1, and so on until the most significant bit which represents H8.

Here’s a quick map displaying which bit in a bitboards corresponds to a square, indexed from the LSB:

8 | 56 57 58 59 60 61 62 63
7 | 48 49 50 51 52 53 54 55
6 | 40 41 42 43 44 45 46 47
5 | 32 33 34 35 36 37 38 39
4 | 24 25 26 27 28 29 30 31
3 | 16 17 18 19 20 21 22 23
2 |  8  9 10 11 12 13 14 15
1 |  0  1  2  3  4  5  6  7
--+------------------------
|  A  B  C  D  E  F  G  H

For example, consider a board with a piece on B1, G3, and C7. B1 has index 1, G3 has index 22, and C7 has index 50, so the bitboard uniquely representing {B1, G3, C7} is , which is equal to 1125899911036930.

We can use our bitboards to compute setwise operations in time. Here’s a short (but not exhaustive) list of operations we can do:

Mathematical representation	Bitboard operation
	`a
	a & b
	a ^ b
![](data:image/svg+xml,%3Csvg%20class%3D%22typst-doc%22%20viewBox%3D%220%200%209.75%2021.878999999999998%22%20width%3D%229.75pt%22%20height%3D%2221.878999999999998pt%22%20xmlns%3D%22http%3A%2F%2Fwww.w3.org%2F2000%2Fsvg%22%20xmlns%3Axlink%3D%22http%3A%2F%2Fwww.w3.org%2F1999%2Fxlink%22%20xmlns%3Ah5%3D%22http%3A%2F%2Fwww.w3.org%2F1999%2Fxhtml%22%3E%0A%20%20%20%20%3Cg%3E%0A%20%20%20%20%20%20%20%20%3Cg%20transform%3D%22translate%280%200%29%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%3Cg%20class%3D%22typst-group%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cg%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cg%20transform%3D%22translate%280%2015.379%29%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cg%20class%3D%22typst-text%22%20transform%3D%22scale%281%2C%20-1%29%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cuse%20xlink%3Ahref%3D%22%23g1E02A02FEB5BC955D50D979EB2112A78%22%20x%3D%220%22%20fill%3D%22%23000000%22%20fill-rule%3D%22nonzero%22%2F%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cg%20transform%3D%22translate%280%204.199000000000001%29%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cpath%20class%3D%22typst-shape%22%20fill%3D%22none%22%20stroke%3D%22%23000000%22%20stroke-width%3D%220.624%22%20stroke-linecap%3D%22butt%22%20stroke-linejoin%3D%22miter%22%20stroke-miterlimit%3D%224%22%20d%3D%22M%200%200%20L%209.75%200%20%22%2F%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%3Cdefs%20id%3D%22glyph%22%3E%0A%20%20%20%20%20%20%20%20%3Csymbol%20id%3D%22g1E02A02FEB5BC955D50D979EB2112A78%22%20overflow%3D%22visible%22%3E%0A%20%20%20%20%20%20%20%20%20%20