Welcome back. Sorry that this installment is a little late. I’ve got a day job you know.
This is part 2 of the series: Chess programming. Read part 1 here.
In this part we will be discussing the 0×88 board representation method.
Some major changes
When I said we will be changing the design decisions if required, I did not anticipate that I will be changing these too soon; but there you go – We have to change the board representation of our game. I will tell you why.
If you remember, we were using a two-dimensional array representation for our chess board:
This was an obvious choice because it is so simple and it is the first data-structure that comes to mind when you think about representing a chess board in memory. The problem with this approach is that a two-dimensional array is not very efficient when we want to do a lot of number crunching.
In chess programs, every cycle we save is very important. Later when discuss game trees and search you will see that the performance of your chess engine depends on the ability of the program to crunch numbers. The faster it can calculate, the better the chess engine will do. Keeping this in mind, we are going to use the 0×88 representation for our chess board.
The 0×88 board representation
The first difference is between 0×88 representation and the two-dimensional array representation is that the 0×88 is a one-dimensional array. This gives us a little bit of performance improvement over the two-dimensional arrays because since there is only one index, the CPU will have to do less work to do the look-up.
The second and the most important difference is that the 0×88 representation contains 128 squares instead of the 64 squares in our previous representation. This means that it has double the number of squares of a normal chess board. What are these extra squares and why are they used? Let us see how it looks:
It looks like the previous representation, except that we have an extra hidden (empty) chess board fused to the right of the original board.
Since this is a one-dimensional representation, the squares are numbered sequentially from 0 to 127. The first row starts from 0 and the second row starts from 16. The numbers 8 through 15 belong to the hidden board squares. Let us see how this numbering scheme looks on the board in hexadecimal notation:
Let us see how this bizarre scheme is better than the two-dimensional array approach. Let us say you looking at a rook on square 7. You want to find out where this rook can move to. As you know, a rook can move to any square in the same file or in the same rank. We can find out the squares on the same file by repeatedly adding/subtracting 16 to the current square:
Similarly we can find out the squares on the same rank by repeatedly adding/subtracting 1 to the current square:
So instead of working with the row numbers or column numbers in the two-dimensional approach, we just work with the square number in the 0×88 approach. But the major advantage of the 0×88 representation has something to do with the hexadecimal number 0×88. You see, when we search for squares in the same file or the same rank, we will eventually overflow the numbers in the current rank/file and go beyond the valid chess board.
If you are using two-dimensional array notation, you have to multiple checks to figure whether your newly calculated row and column are inside the board or not:
Here we have 4 comparison operations – which means 4 branches in the machine opcode and that can be a huge performance hit.
If you are using a single-dimensional array representation with just 64 squares, you will have to do:
That is still two tests. Can we reduce it to a single test? Turns out, we can.
It is easy to know if you are in the current board by just checking whether the 7th bit is set or not:
As you can see, for the immediate numbers greater than 63, the 7th bit is 1 while for numbers smaller than or equal to 63, the bit is 0. Turns out that this test is enough to check whether the number is lesser than 0 too. This is attributed to the the way numbers are represented in Two’s complement representation.
This means that just by checking whether the 7th bit is set, we can decide whether a square is inside the chess board or not:
With this simple test we can now figure out whether a square is inside the chess board or not. Even with this simple test, there are some other problems we want to address. Assume that our rook is in the square 7 and you want to generate all the rook moves from this position. If you add 1 to 7, you wrap around to the next rank (row) and this is not a valid square where your rook can move to.
There is no elegant way to solve this wrapping around problem using the 64-square board. This is where the 0×88 representation comes into picture.
In the 0×88 representation, since we have 128 squares instead of 64, we will have to check whether the 8th bit is set or not to know whether a square is inside the chess board or not. For this purpose we use the constant 0×80 instead of 0×40. Further, if you look closely at our initial representations of the 0×88 boards, you can see that the squares numbers in the hidden board has the 4th bit set while the square numbers in the actual valid board all have the 4th bit as 0. So we can use the constant 0×08 to test whether a square is in the valid part of 0×88 representation or not. Combining both the constants 0×80 and 0×08 we get the new constant 0×88.
So using a simple elegant test, we are able to figure out whether the square is valid or not. The wrap-around problem is also solved here in this case because even if you move right from the square 7, you get to square 8 which is an invalid square and your move in that direction will end there.
Another advantage of using the 0×88 representation is that it is easy to figure out the relationship between two squares if you have the square numbers. For example, if the difference between two squares is 1, you can always assume that they are next to each other in the same rank. If the difference is 16, they are next to each other on the same file (column). Look at our initial 0×88 representation to verify this. This is an important concept which we will use throughout the chess program.
Taking into account a comment from Alejandro on Part 1, I am changing the values of the chess pieces. The idea is that the value of chess pieces should not be substituted for the pieces themselves. We can figure out the values of the pieces later as required when we do evaluation. Right now we want better values to represent the pieces so that the representation will some way help us write better/faster code for the chess program.
Here are the new values that I am going to use:
Notice that we are no longer using negative values for the black pieces.
Notice two things:
- The difference between any white piece and the corresponding black piece is that the 4th bit is set in the binary representation of the numbers. This means that I can find out whether a piece is black or white by doing something like
piece & 0x8
- The sliding pieces (the Queen, the Bishop and the Rook ) all have the 3rd bit set. This allows us to use the test
piece & 0x4to find out whether a piece is a sliding piece or not.
As always, get the latest code from the Chess.js repository.
Wait for the next episode – Part 3: Validating User Moves