Chess programming – The 0×88 board representation

Jan 11 2012

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.

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:

Notice that we are no longer using negative values for the black pieces.

Notice two things:

  1. 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
  2. The sliding pieces (the Queen, the Bishop and the Rook ) all have the 3rd bit set. This allows us to use the test piece & 0x4 to 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

36 responses so far

  • Kendall says:

    you lost me with the bitwise stuff. guess i have some studying to do.
    looking forward to the next chapter :)

    • Niyaz says:

      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.

      • Kendall says:

        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 & 0×1) ^ ((i >> 4) & 0×1) ? ‘light’: ‘dark’) +

        this puts “white on right” and both queens on her proper color.

        just in case you hadn’t noticed already :)

  • Hugo Lopes Tavares says:

    Very nice!

    I hope you keep writing these posts :-)

    Congratz.

  • Kendall says:

    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

    • Niyaz says:

      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?

      • Kendall says:

        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.

        • Kendall says:

          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 & 0×04){ // sliding piece

          to this:
          if(fromPiece & 0×04 || (fromPiece & 0×01) === 0×01){ // sliding piece

          it might not be the best on performance, but it seems the simplest.

          • Niyaz says:

            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.)

  • Kendall says:

    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 80×80 pixels) so the css for the border won’t agree with yours, just a heads up :)

  • Kendall says:

    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.

  • Linda says:

    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.

  • John says:

    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 0×88, because I’m unfamiliar with the javascript for using 0×88,
    But I think using 0×88 in my game will solve a lot of the programming problems I am facing.
    Thanks and I’m looking forward to your next entry.

  • anonim says:

    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

  • Andrzej Swaton says:

    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

  • archmage says:

    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

  • Michal P says:

    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.

  • Anil says:

    complicated O_o

  • Patrik says:

    Thank you for your tutorial is very good. I don `t know if you work at this script anymore, and if it is important or not, is a minor rule in chess called EN-PASSANT, unfortunatly this script Do Not know about that rule.

  • bm2012 says:

    learn a lot from this.thanks, when you will be posting the part 3?

  • Richard says:

    Hi
    Nice couple of posts on javascript chess engine programming-thanks.
    I’m looking forward to the next posts in the series-searching/evaluation etc.
    :-)

  • ajax333221 says:

    I don’t think using bit-wise operators and all slide-pieces is advisable, I mean at best it just saves you couple of “if elses”, but it is risking trading code readability and maintainability.

    I started a proj (https://github.com/ajax333221/JavaScript-Chess) and I am 90% done, and I did just fine using lots of if-elses.

    Some great tips I found are:
    1) store things in an array like_this[][] (0-7 x 0-7)
    2) create a function to convert e4 to coordinates, and viceversa
    3) have 8 directions N, NE, etc… (also for knights)
    4) have an array with X and Y changes for every direction, then loop using these values (e.g +1 -1) and also a inBoard() is handy to check if you are less than 0 or more than 8
    5) to see if king is checked, run this function in all 16 directions (8 for knights)

    hope these tips help

  • kaloxy says:

    Hi

    I am new to this and just crawling the new to get started. This is very informative.

    Though i am lost here: “We can find out the squares on the same file by repeatedly adding/subtracting 16 to the current square:”

    Is it 16 or 10?

    For the rank its clear, but for the file i am totally lost on that one. Kindly clarify, please!?

  • utvcable says:

    This design is incredible! You obviously know how to keep
    a reader entertained. Between your wit and your videos, I was almost moved to
    start my own blog (well, almost…HaHa!) Excellent
    job. I really enjoyed what you had to say, and more than that, how you presented it.
    Too cool!

Leave a Reply