Bits ain't nothing but bytes and tricks

Ones and zeros - you're either a somebody or you're a nobody.

We're all familiar with the fact that computers think in terms of ones and zeroes. The computer is either on or it's off. The program works or it doesn't. It's true or it's false. There's a one or it's just a zero. It's bits - 1's and 0's. If you have any education in computer science or programming there is a high chance that you might have touched binary numbers- those are numbers that are only composed of 1's and 0's. Other than that it is the same as the decimal system that we use in our daily lives. We often assume that the decimal system is somehow more natural and easy. And if not for the fact that we have ten fingers then there is nothing natural or easy about it and we actually would be better off using numebers in base12:
base 12

Small note on updates.

...or the lack of updates really. I have done some small improvements in code quality and lichess API implementation but as far as chess playing goes I have hit a massive roadblock. I put in plenty of work into improving its play and performance but sadly without much to show for it. Whenever I tried to push it's playing capabilities it was too slow and often would run out of memory. And when I pushed for performance it would barely make a dent. So being a little frustrated I am now working on rewriting the whole thing ground up.

BitBoards

How would you go about representing a chess position in terms of computer code? We have a 8x8 board where every square can be occupied by a piece. So the most natural choice sounds like a two-dimensional array:

var board [8][8]int

This is a simple an natural idea. You would access the a1 square by using board[0][0] and you would probably have 0 denote an empty square and say 1-6 being the white pawns to white king and 6-12 for the black pieces.

This is actually exactly what I did in my code because it's very intuitive and it's easy to read. However, what is natural for the human reader and programmer is completely foreign to the computer.

Doing some research I found out that a common implementation of chess programs use BitBoards. These are not arrays or any other advanced data structures they are simply numbers from 0 to 18,446,744,073,709,551,615.

That's a big number right there. This is simply 2^64 -1. I think you can already see where this might be going. Whenever you use a variable in code you need to specify two things- the value and the type. The value is obvious. The type tells the program how to interpret that value. Remember- it's all ones and zeroes. So we need to define the type to tell our program- I want you to take this list of ones and zeros and think of them as a whole number and these ones and zeros are to be read as text and these as some composite object.

The numbers we use for BitBoards are uint64, this means Unsigned Integer with length 64- composed of 64 bits. 64 = 8x8. That's the exact size of our chess board.

Before we continue I need to make a small side note. While we are going to use these 64 bit numbers to describe chess positions we mustn't think of these numbers as we are used to think of numbers in terms of their arithmetic properties. It makes zero sense of counting, adding, subtracting and anything like that. While all those are valid things to do with numbers for our purpose these operations make zero sense. They are just there to store 1's and 0's and the actual numeric values no longer are of any use to us.

Back to the bitboards. Now we have 64 bits stored in a number but if you remember our initial implementation of the [8][8]intarray. While it is pretty easy to think of a mapping from a two dimensional space of 8x8 to a one dimensional space of 64, there is another problem here. In our array we used 0 for empty squares and then 1-12 for various pieces. In our uint64storage method we're only allowed 0 and 1. So either empty or occupied we lost the ability to describe what actually occupies those squares. Solution- we use different variables to store different pieces. One for the white pawns, one for the white knights, bishops etc...

Boolean logic

Now that we have all these numbers we actually need to figure out how to make use of them. 64 bits are a lot and to make sense of it let us first look at 4. If you have ever used the lichess analysis board you might have seen the outlandish looking FEN codes bellow the board. One might look exactly like this:

r1bqk2r/pppp1ppp/2n2n2/2b1p3/2B1P3/2PP1N2/PP3PPP/RNBQK2R b KQkq - 0 5

Actually you can copy-paste it into the analysis board and get the position. Let's quickly break this down:

r1bqk2r/pppp1ppp/2n2n2/2b1p3/2B1P3/2PP1N2/PP3PPP/RNBQK2R

The first part always consists of eight strings separated by "/". These represent the ranks starting from 8 to 1 from left to right and hold the information of what pieces are located where. Lowercase letters denote black pieces upper case white and numbers are the number of empty squares between pieces.

b KQkq - 0 5

The next part is either a lowercase b or w, indicating the side to move. KQkq are the castling rights. K standing for white king-side and Q white queen-side and lower case for black, if no castling rights are preserved it will be replaced by a placeholder "-". The small "-" is a placeholder for en passant capture square. If on the last move white had played e2e4 this would be e3. The last two numbers are the halfmove clock- number of moves since the last pawn move or capture - used for 50 move draw calculation. And finally the full move clock - the number of moves incremented after black moves.

Let's look at the castling rights part and let's talk bits. This will be a small introduction with a real life example of how we can encode information with numbers using their bits. We could of course use the actual string representation KQkqand before castling we would check if it contains either a K or Q, meaning we still hold the rights to castle. However, we're going to describe the castling rights with a 4-bit number very similar how our 64-bit bitboards work but on a smaller scale where we can easily look at some examples.

The full set of castling rights will be represented by numbers from 0000 to 1111 mimicking the string KQkq. Reading from left to right a 1 in the first position stands for K being present, the second bit for Q and so on... For example 0000 means no castling (-) is allowed and 1111 (KQkq) all castling rights are present and say 0110 (Qk) means white has the right of queen side castling and black king side castling. Again at any point we can translate these binary numbers back to their decimal ones. Binary numbers work very much like decimal where from right to left we read them as 2^0 + 2^1 + 2^2....
So 1111 = 2^3 + 2^2 + 2^1 + 2^0 = 8 + 4 + 2 + 1 = 15 (which is 2^4 -1)
So the arbitrary number 15 represents all castling rights present.
Take 0110 = 2^2 + 2^1 = 5. This arbitrary number represents the castling rights Q and k.

But again we need to forget these 15 and 5 values they are meaningless to us. And from here on I will no longer translate them back to base-10 values as it adds nothing of value apart from illustrating that these numbers have no significance in their base-10 notation. Apart from one value - zero, which is 0 in any base and is very useful.
Let's actually write some pseudo code. We will create one variable which will contain the castling rights and we will create four constants - one for each castling right.

var castling // A 4-bit number
const (
    K = 1000
    Q = 0100
    k = 0010
    q = 0001
)

Setting, removing and checking.

We now need to be able to set, unset and check whether any of those four rights are present in our variable castling. To do that we need to introduce bit-wise logic operators on our numbers. If you have done any programming you will be very familiar with boolean logic and their truth tables. Bit-wise operators are exactly the same but they work on not singular true and false values but the entire set of bits where the logic is applied to pairs of bits of two numbers occupying the same position.

Let's define three operators we will need - AND (&), OR (|) and NOT (^) and their logic tables

Bit-wise AND &
a & b = c

Bit-wise OR |
a | b = c

Bit-wise NOT ^
^a = b

Let's look at few examples:
a = 0101
b = 0001
a & b = 0001
a | b = 0101
a & ^b = 0100
This should be quite simple to understand with only the last example being a bit more tricky since you first need to flip all the 0's and 1's to their opposites.

It can actually be much easier to see when you write out the bytes on top of each other, like you do with long multiplication or division.
a & b =
0101 &
0001 =
0001

This way the proper bits line up nicely and you can do them bit by bit - bitwise!

Okay let's go back to our sample code. How do we check if our variable castling contains any of the four castling rights defined as constants?
It's actually very simple: castling & K != 0 this checks if the white king side castle bit is present in our variable. Where ==checks for equality and !=for inequality. Let's do the math with two examples one where it is allowed and one where it's not- 1111 and say 0011 with K = 1000
1111 & 1000 != 0 -> 1000 != 0 -> true.
0011 & 1000 != 0 -> 0000 != 0 -> false.

Now let's take some arbitrary castling rights and set or unset a certain right without touching anything else.
Say castling = 1001 and we want to set k = 0010 and unset q = 0001. What operations do we need?
Setting is very simple we just use the | operator - castling = castling | k. And let's do the example:
1001 | 0010 = 1011, so we added a new right. Now let's unset q. This is a little more tricky. The operation we need here is castling = castling & ^q. Let's try:
1001 & ^0001 = 1001 & 1110 = 1000. And we successfully got rid of the black queen side castling right bit.

These are the most basic bit manipulations there are many more but this will be enough to look at a very naive bitboard use case.

Back to BitBoards...

So with a basic understanding how bit-wise operations and bitmasks work. I can hopefully wrap it all up and show you a basic example how they are used in actual chess.

We will use the following position to illustrate a simple principle.

So I mentioned that bitboards are used to represent piece placement on a board. While true, they actually are used for many other things- indicating threats, generating possible moves of pieces etc. Let us write the position of the white queen on the board in the form of a 64-bit number. I will write the number out in 8 lines of 8, so we can easily see the number as a position on a board:

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

The queen occupies the square b3 and everything else is zero. Let's call this number wQueen. Imagine we have a function in our code generateMoveVector(piece unit64) uint64, this function takes a unit64 of a piece position and returns a uint64 of the available moves for that piece. For now let's leave this function as a magical black box and let's just concern ourselves with the output and not how we got it. Say we got this as a return value from our function:

0 0 0 0 0 0 0 0
0 1 0 0 0 1 0 0
0 1 0 0 1 0 0 0
0 1 0 1 0 0 0 0
1 1 1 0 0 0 0 0
1 0 1 1 1 0 0 0
0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0

The ones indicate all the squares the Queen can move to. We can see that the square b3 the queen occupies is now a 0, Since it can't move to it's current position and it has some 1's along the ranks, files and diagonals.

Let's come up with another number bPawns. I think it's obvious what this means.

0 0 0 0 0 0 0 0
1 1 1 0 0 1 1 0
0 0 0 1 0 0 0 1
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

We have all the ingredients now to ask a very simple question about chess in terms of bitboards - which black pawns does the white queen threaten to capture?
The question in code would look like this: threats = generateMoveVector(wQueen) & bPawns
In human this means give us all those squares that the white queen can move to AND that are occupied by black pawns.

0 0 0 0 0 0 0 0
0 1 0 0 0 1 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

So we can see that the pawns on b7 and f7 are being attacked by the Queen. And we did this using our bit-wise operations.

... yeah, all that just to state the obvious of two pawns being attacked.

In conclusion

If you read through all of this, please accept my deepest apologies. While this is only scratching the surface of bit manipulation that is needed to build a chess engine, I hope it gave you some digestible view into the basics of what bits are and how to work with them. In my entire career as a software developer I have only encountered this sort of bit logic a few times and only the on the very surface. While again computers only understand ones and zeroes. It is hard for humans to deal with and we avoid them as much as possible by using abstractions that keep them hidden below many layers of logic. However, to truly unlock the power of computing sometimes you just have to dive right into them.

While I still have to invest a lot of work and learning to implement the bitboard logic in my chess program. I hope that it will unlock a lot of raw power. But raw power is just dumb raw power and helps you do dumb things faster. On my next blog post I hope to delve into the intricacies of improving the search of moves by working smarter instead of harder. And raw power plus smarts... that could actually come together to something good.