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 0x88 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:
var board = [[BLACK_ROOK, BLACK_KNIGHT, BLACK_BISHOP, BLACK_QUEEN, BLACK_KING, BLACK_BISHOP, BLACK_KNIGHT, BLACK_ROOK], [BLACK_PAWN, BLACK_PAWN, BLACK_PAWN, BLACK_PAWN, BLACK_PAWN, BLACK_PAWN, BLACK_PAWN, BLACK_PAWN], [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], [WHITE_PAWN, WHITE_PAWN, WHITE_PAWN, WHITE_PAWN, WHITE_PAWN, WHITE_PAWN, WHITE_PAWN, WHITE_PAWN], [WHITE_ROOK, WHITE_KNIGHT, WHITE_BISHOP, WHITE_QUEEN, WHITE_KING, WHITE_BISHOP, WHITE_KNIGHT, WHITE_ROOK]];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 0x88 representation for our chess board.
The 0x88 board representation
The first difference is between 0x88 representation and the two-dimensional array representation is that the 0x88 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 0x88 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:
0x07 = 70x17 = 7 + 160x27 = 7 + 16 +160x37 = 7 + 16 + 16 + 160x47 = 7 + 16 + 16 + 16 + 160x57 = 7 + 16 + 16 + 16 + 16 + 16// etcSimilarly we can find out the squares on the same rank by repeatedly adding/subtracting 1 to the current square:
0x07 = 70x06 = 7 - 10x05 = 7 - 1 - 10x04 = 7 - 1 - 1 - 10x03 = 7 - 1 - 1 - 1 - 10x02 = 7 - 1 - 1 - 1 - 1 - 1// etcSo instead of working with the row numbers or column numbers in the two-dimensional approach, we just work with the square number in the 0x88 approach. But the major advantage of the 0x88 representation has something to do with the hexadecimal number 0x88. 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:
if (row > 0 && row < 8 && column > 0 && column < 8 ){ // valid move}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:
if (square > 0 && square < 64){ // valid move}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:
Decimal 62 = 0111110 BinaryDecimal 63 = 0111111 BinaryDecimal 64 = 1000000 BinaryDecimal 65 = 1000001 BinaryAs 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.
Decimal 2 = 00000010 BinaryDecimal 1 = 00000001 BinaryDecimal 0 = 00000000 BinaryDecimal -1 = 11111111 BinaryDecimal -2 = 11111110 BinaryThis means that just by checking whether the 7th bit is set, we can decide whether a square is inside the chess board or not:
if (!(square & 0x40)){ // valid move}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 0x88 representation comes into picture.
In the 0x88 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 0x80 instead of 0x40. Further, if you look closely at our initial representations of the 0x88 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 0x08 to test whether a square is in the valid part of 0x88 representation or not. Combining both the constants 0x80 and 0x08 we get the new constant 0x88.
if (!(square & 0x88)){ // valid move}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 0x88 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 0x88 representation to verify this. This is an important concept which we will use throughout the chess program.
Piece Values
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:
var WHITE_PAWN = 0x01;var WHITE_KNIGHT = 0x02;var WHITE_KING = 0x03;var WHITE_BISHOP = 0x05;var WHITE_ROOK = 0x06;var WHITE_QUEEN = 0x07;
var BLACK_PAWN = 0x09;var BLACK_KNIGHT = 0x0A;var BLACK_KING = 0x0B;var BLACK_BISHOP = 0x0D;var BLACK_ROOK = 0x0E;var BLACK_QUEEN = 0x0F;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.
We will have to use all these small things to our advantage if we want a decent chess playing program. The scariest part is that bit-wise operations are not very fast in JavaScript thanks to a few terrible things it does in the background to convert numbers between 64-bit and 32-bit before applying bit-wise operations. We will see how it goes.
As always, get the latest code from the Chess.js repository.
Wait for the next episode – Part 3: Validating User Moves
you lost me with the bitwise stuff. guess i have some studying to do.
looking forward to the next chapter
Bit-wise operations are going to be a major part of what we are going to do. That said, I too am learning bit-wise operations as I go, so the code I write probably can be further optimized by an expert.
well i’m no expert, but i did notice the dark square is on the right in the latest code. you had it opposite (correct) in the first chapter. it’s just a matter of switching dark and light in the following line:
( (i & 0x1) ^ ((i >> 4) & 0x1) ? ‘light’: ‘dark’) +
this puts “white on right” and both queens on her proper color.
just in case you hadn’t noticed already
Oops. Will fix that. Thanks!
Very nice!
I hope you keep writing these posts
Congratz.
So, in an effort to make sense of all that is going on in the piece evaluations, I integrated a function to seek out all possible moves BEFORE moving a piece (onmousedown), and then highlight (add a border class to) all legal squares. In doing this, I found some possible errors.
Maybe I’m reading it wrong, or you’ve already changed some stuff but I figure it’s worth mentioning. The knights and rooks each have possible moves to the dummy board at any point in the game (including the very beginning). For example, the white rook on square 119, while pinned in by all its own pieces, can move to all eight squares 120-127, each of which is off the board. the white knight on square 113 can move to 80, 82, 95, and 127 (but 80 and 82 should be the only legal moves.) If you display the dummy board, you can even move these pieces to an off-board square.
I tried to figure out what in isPseudoLegal could be causing it, but that’s where I go: O_O
Hmm… I didn’t know the code was so bad… What did you find wrong with the code? The excessive use of bit-wise operations or is there anything just plain wrong?
Anyway thanks for the idea for the highlight feature. I will add it to the code.
You are correct in that I am not filtering away the hidden squares assuming that the user will not be able to drag-drop to those squares. The fix should be simple:
if (!(square & 0x88)){
// valid move
}
BTW is your code in github?
it is now: https://github.com/khstarr
this whole process is new to me.
we had a similar approach for the highlight function. i see your latest code has some multiplayer move fetching going on… i tried implementing that with my local copy but it killed the drag-drop and i didn’t have the energy to figure out why. but i did notice something after reverting back to the version i last tinkered with, and that is:
if you put a piece (say a knight) in front of a pawn still on its starting line, that pawn can do a 2-space move through the knight. illegal of course, and probably a simple fix. wasn’t trying to break your code, just messing with highlight colors and happened to have the board in that position to see it happen.
i’m slowing understanding your code better, and i came up with a quick fix for the pawn problem. i see you do a path check for sliding pieces. pawns need to be included in that classification, so just change this:
if(fromPiece & 0x04){ // sliding piece
to this:
if(fromPiece & 0x04 || (fromPiece & 0x01) === 0x01){ // sliding piece
it might not be the best on performance, but it seems the simplest.
Thanks for finding the issue. I would have missed that. This means that the move highlight feature is very useful indeed.
Even though your fix will solve the problem, I would rather fix the problem inside the pawn section itself than including pawn in the sliding pieces.
The simplest reason is that a pawn is not technically a sliding piece: http://chessprogramming.wikispaces.com/Sliding+Pieces
Later in the game, this distinction will allow us to pre-generate the moves for the sliding pieces. (… even though that it does not make much difference to the current method.)
I couldn’t pin point what’s wrong with the code because bit-wise operations still make my eyes hurt. I started looking into it but needed to better understand binary and hexadecimal first. I didn’t mean to infer that there was lots wrong with your code… mainly because I don’t even know what is wrong, if anything. Just saw some wrapping and am trying to get a grasp on how it’s happening.
I’ll plug in your fix and see what happens.
My code is not on github… never used it before. I’ll sign up and post the additions I made if you want to see them.
I’m using a larger board (squares are 80x80 pixels) so the css for the border won’t agree with yours, just a heads up
I’m not surprised at all, in fact I first tried to fix it within the pawn section, but being the novice I am, I fumbled ideas around and didn’t come up with anything short… so I figured you’d handle it better, hah.
Should of read properly that there is a part 1..
Now it makes a lot more sense, and development seems to be going ok. Haven’t run into any (major) issues so far. Creating a chess game is something I always really wanted to do. This makes it quite a bit easier, so a big thank you to you!
I am in the process of writing my own chess site, and found your blog very interesting. Looking forward to your future articles on chess programming.
I’m writing a chess-like game and I’m still using a two-dimensional array.
The game is on a 10 by 10 board, so I found it to be a headache in creating piece classes and legal move functions.
I still don’t understand your notation in using the 0x88, because I’m unfamiliar with the javascript for using 0x88,
But I think using 0x88 in my game will solve a lot of the programming problems I am facing.
Thanks and I’m looking forward to your next entry.
really interesting, I am working on a PGN reader based on JS. I think I can take some tips from here.
don’t need to remind me to add a link to this tutorial as a reference
If this post was a chess move, it would be followed by the traditional “!!” notation, meaning great move!
The last post was pretty 101, but this post offers some advanced insight and deep analytical thought, as well as research going on and commitment to the project.
Looking forward to part 3
Hello!
Im working on a chess site and I came across this great blog. I was wondering what is the licence of your code and if I can use it in my commercial project. Please let me know.
Thank you
an easier way might be (2*9428)^(1/3) = 26.6164 are the bototm sides.i’ve no idea what the 8cm pieces have to do with the problem.unless you’re going to make the bototm 24 24, in which case, the height of the sides needs to be:9 428 / (24^2) = 16.3680556OH, OH, (9 428 / 8)^.5 = 34.3292878 ** this is what you want.base = (v/h)^.5 where height = 8you have a big old piece of tin, and you’re going to cut an 8 8 square out of each corner.if you want the box to be 9428 cm^3, how big does the bototm have to be?and how big does the piece of tin have to be to start with.16 + ((9 428 / 8)^.5) = 50.3292878that is, Size = 2H+(V/H)^.5
This is amazing stuff, a bit over my head but it definitly put me in the right direction. I’m making a chess game in Unity3d using javascript and was using a 2d array, and I knew there had to be a smarter way to represent everything.
Can’t wait to see more
Hi, I check your code and tried and I found bug. I don’t know if you know, that you check your casting if the rook and king but you shouldn’t be able casting if you move with king or rock before.
Yeah.. I am working on that part.
complicated O_o