Ghess: How to write a Chess Engine?
Creation date: 2021-04-17
I wanted to program a chess engine for many years now as I'm playing since I'm a child and well programming is my hobby for a long long time now.
Imagined that it is a reasonable choice as a project for learning a new programming language. Not so sure about the reasonable anymore but it's definitely a lot of fun. A few weeks back I decided to learn Go as I'll finish my master thesis soon and finding jobs where I can use Julia is not the easiest in the world. I'm not sure whether Go makes it much easier but my choices are not always the most practical ๐
Anyway, I learn programming languages the best when I have a project which is suitable and I think writing a chess engine is a suitable project for Go. I wanted to have a website where one can play against the engine and websocket stuff might not be the best supported in Julia at the moment. Additionally as I later found out it's nice to have it as a binary to use it as a real engine.
I'm not really good with go yet and don't want to spread my weird code much in this blog so this part will be about my journey of ideas, weird chess rules and future ideas.
Before we go into chess: I've recently started to create an email subscription list to send you the newest posts as I blog now not only about Julia but also this series in Go. It's often a bit hard to keep track of new posts when they don't get posted on a regular schedule. So if you want to get informed about new posts roughly twice a month consider subscribing to the list for free. Thanks a lot also to the ones who already subscribed ๐
Before we start: If you wanna check out the currently undocumented code... Ghess So how does one write a chess engine?
The representation
My initial thought was something like: How can the engine know how good the position is? How to include some strategy and game plan? After a while I realized that I should focus on the rules of chess first. Then the questions are:
How to represent the board?
How to find out which moves are legal?
Best way to implement pseudo legal moves (how the piece can move without accounting for checks)
I basically went through three different phases which I'll roughly explain in the next sub sections.
Two dimensional array
I think the first idea that comes to mind for everyone who isn't involved in computer science that much, well and people like me who should know better ๐, is to represent the board in the same way as we humans experience it. A simple 8x8 array where each cell represents a piece or an empty field. Then one writes some loops for sliding pieces (bishop, rook & queen) and everything is quite simple. Well yeah it's relatively simple to write the basics but it's not very efficient for the computer. Looping and indexing to figure out which fields are free and where pieces can move to.
One dimensional array
How about using a one dimensional array where we deal with indices our way and do some calculations but I have the feeling go doesn't have good support for multi dimensional arrays so this might be faster. I nevertheless gave this one a go as well and tried out several things to get a better idea of how the language works and what is fast and what isn't. I'm writing this in only a few sentences here but it actually took me quite a while to get out of this bubble of thinking into the next way more practical approach.
Binary representation
64! That's the answer. Does that ring a bell? A chess board has 64 squares. Anything else you as a computer scientist know about 64? That's how I felt after a week trying those other things... A normal 64 bit computer works with 64 bits ๐. Always checking whether a square is empty or not with loops. Would be soo easy to do it with just binary &, well as it turns out you CAN. The idea that probably thousands of people had before me, was actually a good one.
The hardest part before was always: How to efficiently check whether we can actually move a piece legally or whether it will violate the rule:
You can't move a piece when afterwards your king can be captured
That's kinda the way I always tried to program it. Let's move the piece in this pseudo legal way first and then check whether my king can be eaten. If yes, okay don't save it as a legal move and in both cases revert that move. Reverting a move and making all those checks, like for every piece of the opponent checking whether it can capture my king is kinda tedious. It costs the most time in trying to calculate the number of moves possible.
At this stage I think it's a good idea to talk about testing as it is a huge part in writing something like a chess engine, but actually for every software. For chess it's actually quite simple to write powerful tests though which isn't the case for my ConstraintSolver at least that's what it feels like.
Testing
As mentioned we first want to make sure that our engine works with the proper chess rules and not doing super weird things as I'll show you in the next section ๐
An easy way to do this is to let the engine calculate the number of moves in a certain position some moves down the road.
That's the start position of chess as you probably know and white can start with 20 different moves in this position. Therefore one test case will look like
{"rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1", 1, 20}which consists of the FEN which is a notion for chess positions, the number of half moves we want to look ahead and the number of actual moves. The FEN string might look a little bit cryptic but it's actually quite easy to understand.
We start in the upper left corner (looking from white's perspective) and we go rank by rank. In chess notation ranks 8 -> 1 and files a - h. Then "rnbqkbnr" stands for rook, knight, bishop, queen, king, bishop, knight, rook in lower case for black. The slash denotes jumping to a new rank. 'p' means pawn in the next rank, 8 of them in fact. In rank 6 we encounter the first digit which stands for the number of empty squares (here 8). For the last two ranks (rank 2 and 1) we have the same but with upper case letters for white. After this we already know how the board looks like but it's not completely described yet. We need to know whose turn it is: "w" - white or "b" - black.
Then we add the castling rights, which we'll come to later again. In the starting position we can castle king side 'k' (upper case for white) and queen side 'q' for both sides. After that the en passant position is described which isn't active at the beginning and I'll get to en passant in the next section ๐
The last two numbers are for the number of half moves (ply) made after a capture and pawn push. That's important for the 50 move rule which basically means, if there is no activity for 50 half moves and everyone is bored the game ends in a draw.
The last one is just the number of the next move. This increases after a move by black.
There you can see all the 20 possible moves (actually the gif refuses to show the a2a3 move...). For that it's easy to count by hand and as black has the same responses we have 400 different moves for the first 2 ply. Now if we increase that to 3 ply it's getting harder to count and at a certain stage it's kinda impossible for us mortal humans.
Therefore we use other engines to help us out, in particular I use the famous engine stockfish. It has a command line interface such that it can be used for all kinds of user interfaces. In a future post I might talk about that as well, as my engine can now be played against on lichess.
Anyway... let's run stockfish in the command line:
> stockfish
Stockfish 13 by the Stockfish developers (see AUTHORS file)
position startpos
d
+---+---+---+---+---+---+---+---+
| r | n | b | q | k | b | n | r | 8
+---+---+---+---+---+---+---+---+
| p | p | p | p | p | p | p | p | 7
+---+---+---+---+---+---+---+---+
| | | | | | | | | 6
+---+---+---+---+---+---+---+---+
| | | | | | | | | 5
+---+---+---+---+---+---+---+---+
| | | | | | | | | 4
+---+---+---+---+---+---+---+---+
| | | | | | | | | 3
+---+---+---+---+---+---+---+---+
| P | P | P | P | P | P | P | P | 2
+---+---+---+---+---+---+---+---+
| R | N | B | Q | K | B | N | R | 1
+---+---+---+---+---+---+---+---+
a b c d e f g h
Fen: rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
Key: F2D9D78C7F65C073
Checkers:I typed in
position startposto set the position and d for drawing.
Now we can run go perft 2 to get the number of moves from this position 2 ply into the future.
go perft 2
a2a3: 20
b2b3: 20
c2c3: 20
d2d3: 20
e2e3: 20
f2f3: 20
g2g3: 20
h2h3: 20
a2a4: 20
b2b4: 20
c2c4: 20
d2d4: 20
e2e4: 20
f2f4: 20
g2g4: 20
h2h4: 20
b1a3: 20
b1c3: 20
g1f3: 20
g1h3: 20
Nodes searched: 400The nice thing here is that one can see the first half move and the resulting number of possible moves after that. So for three ply forward we see:
go perft 3
a2a3: 380
b2b3: 420
c2c3: 420
d2d3: 539
e2e3: 599
f2f3: 380
g2g3: 420
h2h3: 380
a2a4: 420
b2b4: 421
c2c4: 441
d2d4: 560
e2e4: 600
f2f4: 401
g2g4: 421
h2h4: 420
b1a3: 400
b1c3: 440
g1f3: 440
g1h3: 400
Nodes searched: 8902Which means that after pawn from a2 to a3 there are 380 possibilities for the next two half moves and for pawn e2 to e4 we have the most possible continuations (600).
Going up to 5 ply was a good test for my engine to check whether I account for check and en passant correctly.
For different starting positions this Chess Programming Wiki page was immensely helpful.
Implementation details
Let's talk a bit about implementation details without going tooo far into it. I want to give enough details to make it interesting for someone interested in building an engine but not too detailed to bore everyone else.
I have two different representation types of the board state.
Storing the piece on each square
Storing a bit set for white and black piece positions
The first one is the representation to access everything about a piece. I get into detail with what kind of infos I store for each piece in a second. The later representation is a fast way to check whether a piece can move to a position or whether there is already another piece of the same color.
For each piece I store an id, the color, the position as a set bit in a uint64, the movement possibility of that piece in a uint64 as well and some more.
The sliding pieces can be implemented easily by having an & for each position direction I want to travel to and stopping if there is a piece of my own color or stopping right after, if there is a piece of the opposite color, as I can capture that piece. For this I created a loop which iterates over the 8 possible directions of the queen and limited it to 4 directions for the bishop and the other 4 for the rook.
Next up is the knight which is kinda simple as we only have to check the 8 possible positions and don't need to check for any blocking behavior. It is however important that we don't jump out of the board and somehow jump back into it on the other end. That's also important for the sliding pieces btw. As we kinda use a one dimensional array approach even if we represent it in a single uint64 number we need to calculate a bit whether it's actually a possible move or whether we somehow try to move 6 moves to right when we are already in rank h. Therefore, I created a helper array which tells me how many squares there are left for each of the 64 squares in all of the 8 directions.
Let's get to the pawn where weird things can happen! First of all:
we can move 2 squares sometimes but mostly 1
we capture differently than we move
we can change our type to queen, rook, bishop or knight when we reach the other side of the board
we don't like if pawn of the opponent tries to run right next to us
then we can capture them even though we normally couldn't (check the rules: en passant)
They seem simple at first but damn they are complicated little creatures.
I don't want to go into the implementation details as mentioned but well you should be careful when you implement their movement ๐
And our favorite piece the king:
seems like I can move in all directions by only one square
but actually I can also do some fancy stuff sometimes. It's called castling and it's allowed if:
I'm still at my starting square
can see my rook
the rook didn't move
I'm not attacked
and I don't be attacked during my route of moving two squares closer to my rook
and then the rook just jumps over me
I mean who invented these rules? ๐
Sometimes I thought that those people thousands of years ago just wanted to make the life of chess engine programmers harder.
Oh yeah and now I haven't talked about that "check" thing.
As you probably know the king can't be captured which means each player has to either move their king when in check or block it. It's also not possible to move a piece in such a way that your king could be captured in the very next move.
Let that sink in for a bit...
My idea at first as mentioned was:
make the move we think is possible
check for the opponent if it can now capture your king
if it can -> move not possible
make that move back
This takes a while and speed is quite important for chess engines ๐
Do we humans think that way? Well kinda but kinda not. We don't check whether the queen far far away behind pawns can capture our king when we move a pawn not even in line. We additionally often have the thought: We can't move this knight as it's pinned by the bishop.
Therefore let's talk about pinned pieces.
In this position we can't move the knight. This can be determined with: Take the sliding piece "bishop" and check whether we can capture a piece and if that piece wouldn't be there we could capture the king. Then mark that possible capture piece as pinned and tell them where it could move. In this current situation it can't move anywhere as it is a knight but in this case:
we can actually move with the bishop but only in the direction of the pin.
Okay doesn't sound that complicated, right?
In this position we can not capture the rook that is giving check because the pieces who could are pinned.
Then normally when we are in check we have the option of blocking the check or moving the king but here:
we are in double check so we can't block the check.
For the next one I go into the nice little bugs section as most of this stuff I at least considered when thinking about it.
Bugs I encountered
Let's show some bugs where my engine "thought" yeah I can move this why not:
I think we start with my all time favorite chess position, which was probably invented just for engine testing.
It looks kinda normal right? But now let's make a move for black: Pawn c7-c5. If you have checked the en passant page you might know that the white pawn next to the king could take that pawn as it was trying to run past. But then there is the black rook on the other side of the board which disallows this behavior as then it could capture the king and the rules of chess are broken.
The thing is for my engine the pawn next to the white king is currently pinned, but when the black pawn blocks that pin it should be free to do whatever, right? Nope! One always has to check whether there is a check...
BTW the same is true for the white pawns in this position when they move two steps forward. They can't be captured by the black pawn due to more or less the same logic.
How about the next one?
Well I told my engine that normally we can castle if we haven't moved the king or rook and are neither in check nor walk through it.
Therefore my engine... Well so I can castle with a black piece?
That is what could happen in the above position. I fixed the bug already so I can't directly demonstrate it but I hope you get the idea.
I probably missed ten other stupid bugs like the one time I didn't account for the edge of the board for pawns such that it was possible to en passant at the other side of the board. Well humans don't play chess on a cylindric board normally but actually... why not?
Playing against the Engine
After I implemented all those bugs oh and fixed them I was finally able to start working on the engine. I wanted to start with silly engines like:
move randomly
capture whenever you can
before diving into the actual work.
You can see some of that in my two YouTube videos Two silly chess engines! and the more powerful one in Is it all about check?.
After some thinking I was able to implement a decent engine using alpha beta pruning which we might discuss in a future post. There are quite good YouTube videos about it though so maybe I'll talk about some specifics for which I wasn't able to find too much information. Algorithms Explained - minimax and alpha-beta pruning by Sebastian Lague
Then I implemented the universal chess interface (UCI) for my engine and created a Lichess bot which was surprisingly simple.
Here you can see it playing against some other bots and me: Ghess: Playing against other bots and me
Future ideas
Chess engine programming is quite an interesting subject and there are lot of things one needs to consider:
How far do I need to search?
How do I evaluate a position?
counting material
activity
...
pawn structure
How do I manage my time?
What do I do while my opponent moves?
After the stream I worked a bit on time management and the horizon effect which might be a good start for another post.
For now thanks everyone for checking out my blog. Hope you enjoyed the post and please consider subscribing to my email list if you haven't already.
Thanks to my 11 patrons!
Special special thanks to my >4$ patrons. The ones I thought couldn't be found ๐
Site Wang
Gurvesh Sanghera
Szymon Bฤczkowski
Colin Phillips
For a donation of a single dollar per month you get early access to these posts. Your support will increase the time I can spend on working on this blog.
There is also a special tier if you want to get some help for your own project. You can checkout my mentoring post if you're interested in that and feel free to write me an E-mail if you have questions: o.kroeger <at> opensourc.es
I'll keep you updated on Twitter OpenSourcES.
Want to be updated? Consider subscribing and receiving a mail whenever a new post comes out.
