How to Build your own Chess Engine! (Overview)
Today I’m going to talk about one of my favourite hobbies: chess engines. There’s nothing like seeing an engine that you’ve made rise up in ELO until it’s finally able to beat you. It’s also, as I’ve found, incredibly addictive - you won’t be able to stop searching for small tweaks and optimisations to speed up and strengthen it! As some background, I made my first chess engine in Java around 3 years ago. It made … moves, to say the least, but it wasn’t significantly better than choosing random ones. To it’s credit, it never flouted the rules of chess, but I wanted something that could at least match my Elo (not a seemingly tall order, given that I was only around 1200 Lichess rating). Eventually I started from scratch in C and managed to achieve this, because instead of the naïve but intuitive methods used in the Java version, I used a faster, more modern framework to form the backbone of the engine. Around late 2019, I was rather inspired by the Rust community, so I translated it to idiomatic Rust and tacked on some improvements. Later on, I made a new engine in C, ported that to C++, then started focussing on incrementally upgrading it after it knocked the Rust version out of the park in a head-to-head. While optimising for speed is one thing, optimising for program size is another area that I’ve been interested, so predictably I am a huge fan of H. G. Mueller and Oscar Toledo.
There aren’t a huge number of dedicated resources for chess programming: there is the eponymous Chess Programming Wiki, which is quite hit-and-miss with its explanations, as well as a few questions on Chess Stack Exchange and Stack Overflow - but the best place to look is the old talkchess forums, where you could actually talk to pioneers of computer chess. Unfortunately its webpages seem to load far less frequently than they used to. That said, exploring and learning to debug properly for yourself (I made a series of ridiculously specific debugging tools) is a fantastic learning experience - and seeing your chess engine come to life for the first time is exhilarating.
Fair warning: I’m going to assume hereon that you’re familiar with the fundamental rules of chess (though I’ll definitely explain the more obscure tournament rules)$^1$. Also, rest assured that making a basic, miniproject chess engine is definitely doable, but in that case the methods in this blog series might be overkill. Here I’ll be explaining the tools and techniques in professional, state-of-the-art chess engines - so that you can make your own one!
But enough history - what actually goes into a chess engine? It goes without saying that the ultimate purpose of a chess engine is to input a position and get back the optimal move for the side to play, hopefully leading to checkmate. This takes some work: we need to be able to define what “position”, “move” and even “optimal” mean! To this end, there are four main components of a chess engine: the main data structure being Position, and the main algorithms being Move generation, Evaluation and Search. There’s also some bureaucratic stuff regarding standardisation with a chess playing interface, but everybody just puts it off until the last minute, so I’ll ignore it.
-
Position: This is the data structure that represents the state of the chess board at any given moment. It forms the basic framework of the chess engine that I alluded to earlier. Getting this stage right is integral to a solid engine, because no matter how optimised and clever the three functional stages are, they all ultimately have to interface with the Position and its bottlenecks. Anyway, here’s a riddle for you: what do chess boards and CPU registers have in common? Find out in this blog post.
-
Move generation: Given any chess position, the first stage to finding the best move is to know which moves we’re even allowed to play in the situation. Considering that 4-year olds can learn the rules of chess fairly simply, this doesn’t sound like a huge challenge. Oh, but it is. A lot of intuitive notions regarding pins, checks, castling, promotion are both tedious and annoyingly fiendish to implement without having your clock cycles biting on granite. And dare I mention en passant? This stage is actually the only purely objective routine, and so competition for fast move generation is commonplace. I personally found optimising this quite fun, but you don’t need to worry: move generation typically takes up only 5-10% of the total cycles, so it’s not a deal-breaker. Read more …
-
Evaluation: Now that we have a position, we need some way of determining how “good” some position is. Somewhat unintuitively, we have to determine this without thinking about what future positions will look like! In contrast to move generation, evaluation is wildly subjective, and you can employ whichever heuristics you want to find a good balance between accuracy and speed. In practice, this is the hardest stage to get right, amusingly because it’s the one aspect of the game that relies largely on human understanding of the game (and also because of its many free parameters)$^2$. Read more …
-
Search: You might already be familiar with this stage if you’ve ever made AI for other turn-based games! This stage has the largest amount of material available (at least for the fundamental features), much of it taught at CS courses at universities. Imagine the starting position - there are 24 legal moves you can make as White. If you play, say, e2-e4, then Black has 24 different ways to respond, and so on. It’s not difficult to imagine that the set of possible chess games can be represented as a tree with its root at the starting position. Now here’s where the concept of “looking ahead” comes in: to determine the best move, we shouldn’t just rely on the “static” evaluation at the root, we should probe deeper into the game tree to see what actually ends up happening to us. In other words, we search the game tree. This stage involves some simply beautiful algorithms to do this rapidly, and so it’s my favourite part of the engine. Read more …
$^1$ For the love of god, pinned pieces can still give check
$^2$ Actually, AlphaZero doesn’t do this - only traditional engines like Stockfish and Komodo do. But the fact that AlphaZero would have gotten its motherboard handed to it by Stockfish 13 shows that human intuition about chess is reasonably good