Cool Chess Engine Bit Twiddling Trick

While having a go at writing my own chess engine I came across a ridiculously beautiful bit twiddling trick…

So, I’m on my second weekend of trying to write a chess engine from scratch, having been thoroughly nerd-sniped by Lichess and their generous hosting of the Chess Programming Wiki.

I’ve come across the Most Ridiculously Cool bit twiddling trick that I’m fairly sure all the engines use.

Certainly the Not Quite A Tutorial As Such But Very Close To It that I am working through has it (see rustic-chess.org - it’s excellent) and I bet they all do.

It’s to do with the en passant rule in chess, and how you can quickly calculate the target square for that rule, given either an en passant capture or a pawn move that may allow en passant on the following move.

The thing is, in chess engines, most moves involve a start square A and an end square B, so a piece starts on A and ends up at B.

In en passant, however, there’s a third square involved - the square behind the pawn that moved two squares on its first move.

Engines need to calculate a bajillion moves a second, so we need a quick way to find the en passant square in the move(piece, from, to) function.

That’ll be the square behind the pawn that moved two squares or is making an en passant capture, and it’s in a different direction depending on which and whether it’s White or Black.

Turns out you can use the following code for all cases, and it Just Works:

ep_square = to_square ^ 8

The ^ sign means XOR (see here for explanation of that) and this code works whether we are talking about a capture (and want to find the pawn to remove) or a double-step pawn move (and want to find the possible EP capture square).

This is some serious bit-twiddling voodoo.

To explain why this works, you need to understand something about how chess engines represent the chessboard internally.

For speed, they tend to use either (or both of) an array of 64 squares each containing a piece, or a set of 64 bit numbers representing the current board position.

Either way, we get a situation where each of the squares from A1 to H8 gets represented by a number from 0 to 63.

That looks like this:

8  56 57 58 59 60 61 62 63
7  48 49 50 51 52 53 54 55
6  40 41 42 43 44 45 46 47
5  32 33 34 35 36 37 38 39
4  24 25 26 27 28 29 30 31
3  16 17 18 19 20 21 22 23
2   8  9 10 11 12 13 14 15
1   0  1  2  3  4  5  6  7

    a  b  c  d  e  f  g  h

The ranks we care about are the third and sixth ranks, where a pawn capturing en passant must land, and the fourth and fifth ranks, where pawns being captured en passant must be.

Look at the third rank, from 16 to 23. Turns out that 16 in binary is 10000 and 23 is 10111. And 8 is 1000.

But! 16 XOR 8 is 24, and so on up to 23^8 = 31. For each square on the third rank, sq^8 gives you the corresponding square on the fourth rank, ie it adds eight.

XOR is reversible - apply it twice and you get back what you started with.

So for each square on the fourth rank, sq^8 gets you the corresponding third rank square, ie subtracts eight.

Now look at the sixth rank, 40 to 47. 40 is 101000 and 47 is 101111.

Now when we XOR with 8 we remove that fourth bit - 40^8 = 32 and 47^8 = 39 - giving us the right fifth rank square.

Similarly, we can also use sq^8 on any fifth rank square to get the sixth rank square we want.

So the same calculation still works, without change, even if we are going in the opposite direction.

We don’t need to care whose pawns we are talking about.

This completely blew my mind when I figured it out a couple of hours ago - if you’re in the tiny demographic of people who are into coding and chess and didn’t already know this, perhaps yours too?

I’m sure there’s a page for this on the Chess Programming Wiki (there should be!) but couldn’t find it.

I bet this goes back to the earliest chess programs and has been handed down over decades, now reaching you.

What’s your favourite bit twiddling trick?