A chess engine must search millions of positions per second. Move generation is often a bottleneck. Generating moves for knights, kings, and pawns are computationally cheap (~1 nanosecond). However, rooks, bishops, and queens (aka "sliding pieces") present a unique challenge: their movement depends on the placement of other pieces. This makes on-demand generation too slow (20+ nanoseconds) and naively-implemented lookup tables impractical (requiring zettabytes of RAM).
We will start by reviewing the core data structures in a chess engine and the logic behind move generation. Then, we will explore "magic bitboards", a perfect hashing technique that enables sliding piece move generation in ~1 nanosecond. We will look at how to implement this in modern C++, comparing hardware-specific instructions like PEXT (Parallel Bits Extract) against a portable software approach. Finally, we will discuss the practical challenges of generating the data structures required for magic bitboards, including the limitations of consteval and how to integrate build-time table generation into the build process using Bazel.
To ground these concepts, we will be referencing implementation details and code from my C++ chess engine, FollyChess.
View Slides
Aryan Naraghi is a Staff Software Engineer at Google specializing in distributed systems. Over the past 14 years, he has built critical infrastructure across Google (including BigQuery, Cloud Run, Compute Engine, and Vertex AI) and previously led data strategy as Head of Data Analytics at Restaurant Brands International. He holds a B.S. in Computer Engineering from the University of Washington.
A dedicated C++ practitioner, Aryan is the creator of FollyChess, a C++ chess engine focusing on low-latency search and modern C++ design patterns.