Developing a chess engine

Jul 2023
<--- six mins reading time
In this article I'll give a brief introduction to programming for computer chess. I'll assume some knowledge about chess and how a chess engine operates under the hood. I'm by no means an expert on the topic, but I recently created a chess engine and wanted to prevent others from making some of the mistakes I did.
A major issue I ran into was different parts of my engine failing silently. This means that often, you don't know when systems break, which parts are broken, and in what ways. At the end, I'll give some high level tips for developing a chess engine in the early stages.
Computer Chess Fails Silently
Algorithmic game theory is an extremely complicated topic and often requires lots of in-depth thought to fully realise simple concepts. Take minimax/alphabeta - it's simple on the surface, but requires you to think recursively and track multiple changing variables as well as understanding the underlying game. Pen and paper at this stage is invaluable - take notes, draw doodles and sketch toy examples which can all make a problem tractable.
When a search algorithm doesn't work, it often compiles but spits out moves which to us humans are incomprehensible.
The most common causes of this are
  1. forgetting to account for the toggling sides as each player makes their move (analagous to accounting incorrectly for min/max) and
  2. mixing up perspective based evaluations.
A less common cause of this is move generation which fails loudly and is easily tested.
With chess there is no perfect play but moves are made at an extremely high level - this has a few consequences:
  1. Small differences in high level play can be hard to distinguish as a human
  2. Edge cases are often hard to test and can change the outcome of a game can be dependant on understanding a position rarely seen in the training data
  3. The source of booms and moobs can be hard to find, considering the extreme depth modern chess engines work to.
Neural Networks Fail Silently
Neural networks are frequently used to replace the traditional hand crafted evaluations used in early chess engines (pre-alphazero). In about 2020, Stockfish absorbed a type of neural network called NNUE which aimed to be sparse and efficiently updatable. These have been invaluable in improving computer chess, however while developing one I encountered a few footguns and avoidable traps.
One of the initial problems which come with any machine learning project is the idea that neural networks fail silently - and often, will work 90% as well as the network learns to adapt Andrej Karpathy. This could be as innocuous as a flipped feature set but could be eating away at free accuracy.
Getting one to train is more of an art to a science. What I found for chess engine development was to copy the simple NNUE layout detailed in this document and once that was working with no issues, to proceed to more complicated layouts. A mistake I made was going too complicated too quickly, and having my network fail to generalize due to a small error in my code which was impossible to spot due to unnecessary complexity I'd added too soon.
Another issue you'll run into with creating a NNUE is sourcing data - you can't participate in TCEC with training data generated by a different engine, so you'll have to generate evaluations yourself. This is often done by using a hand crafted evaluation (HCE) function at a low depth to create training data. You'll find there's a trade off between quality training data and positions which are fast to generate.
Chess is a really complicated game with a pretty large branching factor. When your network is operating at 90% potential, there's essentially no way to know apart from to go through each step and scrutinise every connection, activation and regularization. Don't do what I did and start complicated and wonder why your network is performing subpar.
Double Trouble
The difficulties of developing a computer chess program and a neural network compound. This means that, whenever one fails silently, it'll often be difficult to discover the source of the issue. I found that working on a simple evaluation network first before writing the search code made it easier to track down the source of an error.
Furthermore, encoding chess feature sets for neural networks to digest is extremely complex and requires you to balance sparsity with information density. Stockfish's HalfKA and HalfKP are common feature sets but each come with unique implementation difficulties.
When it comes to training a chess network, both the "efficiently updatable" and quantisation methods can make backpropagation difficult. This is not a time to write fast-and-loose code - slow down, and start simple.
General Advice
Visualise everything in any way that is human readable
The human brain is amazing at picking out patterns in visual data. Exploit this! Visualise how your training data is distributed, create renders of your search tree, create a histogram of position evaluations. When I did this, I found a couple of silent failures in my engine.
Try edge cases
Make sure your training data has plenty of edge cases - concepts like zugzwang, fortresses, and tempo. Just look at a list of specific exceptions that some chess engines fail to understand.
Create an end-to-end implementation
This one has more to do with time management than technical prowess. Don't create the best evaluation, and forget to create an equally strong search algorithm. Creating a UCI interface will take longer than you think. When I created my first prototype, I should have created a bare-bones skeleton implementation before diving into the finer details
Use sanity checks
I made this mistake in early stage development. Actually look at a lot of training positions and how your engine evaluates them. Actually play your engine. Do not look at numbers and assume your engine is functional. Compare your engine to Stockfish and see where it differs and why.
Look at how other engines do things
Read before you write. The chess programming wiki is a great source for learning about search algorithms and evaluation functions. Join the Stockfish/LC0 Discord servers and ask questions. Sometimes, documentation for open source chess engines is messy and lacking but provides a good starting point for creating your engine.
Thanks for reading.
<--- Home