How basic Chess Engines work
Overview of the key parts of chess engines
For a long time, I wanted to write my own chess engine. But I never found the time and motivation to do it. Now I want to actually do it and share the process here.
But before I start with the more detailed posts, I think it's helpful to give an overview of how basic chess engines work.
There are 4 major components which every engine has:
board representation
move generation
evaluation
search
In this post, I'll give a brief overview of these components. I'll write more detailed posts about each of them, including how to implement them, as I write my own engine.
Board Representation
The first thing to do when writing a chess engine is to choose how the board and pieces should be represented internally. Apart from the pieces, the program should also keep track of castling rights, the 50-move rule and en-passant squares.
There are many different ways to do this, but it's very important to consider efficiency. If the internal representation of the board in pieces is slow, everything that comes afterwards will also be slow and the engines won't be as strong as it could be.
Move Generation
Now that the engine is able to "see" the board, it needs to be able to make moves. This is where the move generation comes in. Again, speed is every important at this stage. Also, it's essential to make sure that there aren't any bugs in the move generation code. Especially castling and en-passant can lead to problems which can be hard to find.
Evaluation
After the basics are done the fun stuff can begin.
The task of the evaluation function is to evaluate a single position. The evaluation function can either be quite simple and therefore quick to execute, which lets the engine calculate deeper, or it can be more complicated, so hopefully more accurate, but this comes at the cost of speed.
Search
Finally the engine needs to calculate ahead. It does this with its search function. The idea is to start at the current position and build a tree with all future positions. The search function then needs to find the best possible position (i.e. the position with the highest evaluation) for the side which is currently playing, while assuming that the opponent plays perfectly.
Since there are so many possibilities in chess, it's impossible to search through every legal move at a reasonable depth. This is where so-called pruning comes into play. In order to keep the number of possibilities somewhat low while searching to a reasonable depth, some options must be discarded (pruned) right away. Humans do this all the time which is why you don't even consider playing most legal moves.
There are various techniques for search and pruning. I'll discuss them in my more detailed posts later.
Putting everything together
Now that all pieces are in place, it's left to see how they work together in order to evaluate a chess position and find the best move.
When analysing a position, an engine first generates all legal moves up to a certain depth in order to build the tree of variations. Then to find the best branch in the tree, the positions get evaluated by the evaluation function. After that, the search algorithm can be applied which gives the best resulting position, assuming best play by both sides.
The evaluation you see of the initial position is then actually evaluation of the final position (which is the reason why evaluations often seem very high or quickly go to 0.00). The line which the engine suggests is the branch in the tree which gets you from the starting position to the final position.
Note that I haven't mentioned pruning because there are various techniques which can be applied at different stages in the process.
My engine project
As mentioned in the beginning, I want to create my own chess engine and write about it here. My main goal is to get a working chess engine, so I'll start with the basics and will leave optimizations for the end.
I aim to write weekly update posts where I share my progress and explain all the techniques I used. These posts will be in addition to my usual posts (which will resume next week).
I hope you're as excited as me about the project.
I'm interested. Which programming language will you use?
will you follow all the forward pruning heuristics on top of alpha-beta pruning. Previous examples of engine building from scratch I followed, seem to have gone that way toward ELO objective within the engine tournaments mostly mimicking human tournament performance objectives.
They view any "how does the engine work" user interface access, as getting in the way of speed. Is my current take home. would need ramblings.. I am saying this, just in case your objective is more didactic. In that you will keep interpretability back to chess through and through, and will not converge to the basic same architecture as most exhaustive search engine still keep, even if NNue, is it self making a better quality leaf evaluation and reduce the breadth of search for same ELO.
You can do whatever, I am just curious of goals.