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 = 7
0x17 = 7 + 16
0x27 = 7 + 16 +16
0x37 = 7 + 16 + 16 + 16
0x47 = 7 + 16 + 16 + 16 + 16
0x57 = 7 + 16 + 16 + 16 + 16 + 16
// etc

Similarly we can find out the squares on the same rank by repeatedly adding/subtracting 1 to the current square:

0x07 = 7
0x06 = 7 - 1
0x05 = 7 - 1 - 1
0x04 = 7 - 1 - 1 - 1
0x03 = 7 - 1 - 1 - 1 - 1
0x02 = 7 - 1 - 1 - 1 - 1 - 1
// etc

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 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 Binary
Decimal 63 = 0111111 Binary
Decimal 64 = 1000000 Binary
Decimal 65 = 1000001 Binary

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.

Decimal  2 = 00000010 Binary
Decimal  1 = 00000001 Binary
Decimal  0 = 00000000 Binary
Decimal -1 = 11111111 Binary
Decimal -2 = 11111110 Binary

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:

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:

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

I will try to document and discuss every small detail of the implementation so that a reader will not have any difficulty in writing his/her own chess playing program after reading this. At the same time, I don’t want to go into the details of the game itself.

Prerequisites: I would assume that you have a good grasp about the rules of the game and have experience in playing chess. You should definitely be experienced in computer programming. You need not be experienced in JavaScript itself. As long as you have experience in some programming language, I hope that you can read the JavaScript code here and understand what is going on. I am going to use a bit of HTML/CSS in this tutorial, but that will be mainly for drawing the chess board output to the screen. This is independent of the chess programming logic, so you need not worry much if you are not well versed in HTML/CSS.

Of course the fact that we are using JavaScript for this programming problem is a bit of a challenge. I am not sure that JavaScript is as fast as other languages in raw computation speed which we will require abundantly for number crunching in a chess playing program.

Our Goal

At the end of this exercise, we hope to have at least:

• A chess UI with which the user can interact with
• A chess AI against with the user can play

Note: I don’t have a completed source code for this article series (even though I have previous experience in chess programming). I am writing the code as I go. What this means is that I will make a lot of mistakes in the code and as well as in the decisions I make on how to go about structuring the whole application. If you find something wrong, let me know in the comments.

Okay now, lets dive in.

Displaying the board

First, let us draw a chess board on the screen. At the start of the game,  a chess board consists of 64 squares and 32 chess pieces arranged in a predefined manner. We are going to do two things here:

1. Find a way to represent the board and the chess pieces in our program.
2. Write a function to display the current board on the screen.

Here is our initial take on the HTML file:

<!doctype html>
<html>
    <head>
        <meta charset='utf-8'>
            <title>JavaScript Chess</title>
            <link rel="stylesheet" type="text/css" href="css/style.css">
    </head>
    <body>
        <div id='board'>
        </div>
    </body>

    <script src='scripts/jquery-1.7.1.min.js'></script>
    <script src='scripts/chess.js'></script>

</html>

There is nothing much in the file. We have a single div to hold the chess board. We have included style.css for giving styles to the chess board. We have included jQuery for DOM manipulation, which right now mainly means drawing the board. For this purpose, including the jQuery is definitely an overkill, but I used it anyway so that our code will be clean. It should be easy for you to remove jQuery and just plain JavaScript to duplicate our function to draw the board.

Board Representation

We need a way to represent the chess board and the chess pieces. We will represent the board as a two-dimensional array. This way we can refer to a piece in any row/column (also called rank/file). We have to think about this design decision for some time because there may be performance implications for this decision. For performance reasons, we may later decide to use bit-boards to represent the board and the pieces, so we should take to write code in such a way that it will be easy to switch between the array representation and bit-board representation.

So let us start by defining the different pieces in chess. We are just enumerating the possible pieces here:

var WHITE_KING = 100;
var WHITE_QUEEN = 90;
var WHITE_ROOK = 50;
var WHITE_BISHOP = 31;
var WHITE_KNIGHT = 30;
var WHITE_PAWN = 10;

var BLACK_KING = -WHITE_KING;
var BLACK_QUEEN = -WHITE_QUEEN;
var BLACK_ROOK = -WHITE_ROOK;
var BLACK_BISHOP = -WHITE_BISHOP;
var BLACK_KNIGHT = -WHITE_KNIGHT;
var BLACK_PAWN = -WHITE_PAWN;

As you can see we are trying to give different values for each piece in the chess board. I am using ALL_CAPS notation for the variable names to denote that they are constants. JavaScript does not have a way to denote constants (yet).

The pieces are given values based on their relative importance. The Pawn is given a value of 10 and then each other piece is given a value based on how valuable the piece is compared to a Pawn. Think – how many Pawns do we need to make up for a Queen?

You can see more discussion about it here. Normally the value of a Pawn is considered as 1 and the relative values of other pieces are calculated based on that. Here we are using a base value of 10 for Pawn, Just so that the relative values of the Bishop and the Knight can be different at the same time whole numbers. More about this later.

The value of the King is not important because there is no move in chess where you consider sacrificing your King. So you can use any value of the King. We are using 100 here. You can as well use 1.

As you can see, the values given for the black pieces are just the negative values of the values given for the same pieces in white. This is because later in the game when we evaluate board positions, we can just add up all the numbers and see who has an advantage.

Now we have the pieces and what we need is a board to place the pieces:

var 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,0,0,0,0,0,0,0],
             [0,0,0,0,0,0,0,0],
             [0,0,0,0,0,0,0,0]];

As we already discussed, the board is an 8×8 array. The values represent pieces. A zero value in a cell means that the square in the board is empty. As you can see, the whole board is empty at this point. Let us add the pieces to the board so that it resembles the starting position of a standard chess game:

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]];

I hope it is not difficult to guess what happened here. We are just placing the pieces we already defined on the chess board according to the rules of the game.

Now that looks awesome doesn’t it?

No. It does not.

We need to show this board in a better way so that people will be able to see the pieces rather than cryptic notations on the screen.

So we define a drawBoard() function which will draw the board to the screen.

function drawBoard(board){
    var str = '';
    for( var i = 0 ; i < 8 ; i++ ){
        str += '<div class="row">';
        for( var j = 0 ; j < 8 ; j++ ){
            str += '<div class="column ' +
            ( (i + j) % 2 === 0 ? 'light': 'dark') + '">' +
            '<div class="' + getPieceName(board[i][j]) + '"></div>' +
            '</div>';
        }
        str += '</div>';
    }
    $('#board').append(str);
}

Here I am constructing an HTML string that will paint the board and then append that HTML string to the board div that we have in our index.html file.

In the first loop (row loop) we are creating a row and in the inner loop (column loop) we are inserting 8 columns to the row.

To understand the code inside the inner loop better, let us see an example output of a single iteration of the inner loop:

<div class="column dark">
    <div class="WHITE_KNIGHT"></div>
</div>

In this example, the outer div has two classes associated with it. One is column, which is generic and it just means that this is a column. The second one is dark which denotes that this is a dark square. As you already know, a chess board contains two different types of squares, dark and light. We use this class to give a dark background color to this square. Similarly, lighter cells will have a light class and will be styled accordingly. To alternate between the dark and light squares, we use the test (i + j) % 2 === 0 and it is easy to understand why if you work it out using pen and paper.

The inner div also has a class. This time the class says WHITE_KNIGHT. This denotes the piece which is present in that square in the board. We use this class to show the corresponding piece on the screen:

#board .column .WHITE_KNIGHT {
    background: url('../images/wKnight.png');
}

Similarly we style all the classes so that the icons for the pieces will be loaded whenever the class for corresponding piece is present.

Okay so how did we get this class value as WHITE_KNIGHT ? It is done by this piece of code: getPieceName(board[i][j])

What does it do? It gets the value of the piece at the board position [i,j] and then passes this value to a function called getPieceName(). What does getPieceName() do? Well it just returns the name of the piece in string format:

function getPieceName(pieceValue){
    switch (pieceValue) {
        case WHITE_KING:
            return 'WHITE_KING';
            break;
        case WHITE_QUEEN:
            return 'WHITE_QUEEN';
            break;
        case WHITE_ROOK:
            return 'WHITE_ROOK';
            break;
        case WHITE_BISHOP:
            return 'WHITE_BISHOP';
            break;
        case WHITE_KNIGHT:
            return 'WHITE_KNIGHT';
            break;
        case WHITE_PAWN:
            return 'WHITE_PAWN';
            break;
        
        case BLACK_KING:
            return 'BLACK_KING';
            break;
        case BLACK_QUEEN:
            return 'BLACK_QUEEN';
            break;
        case BLACK_ROOK:
            return 'BLACK_ROOK';
            break;
        case BLACK_BISHOP:
            return 'BLACK_BISHOP';
            break;
        case BLACK_KNIGHT:
            return 'BLACK_KNIGHT';
            break;
        case BLACK_PAWN:
            return 'BLACK_PAWN';
            break;
        
        default:
            return 'EMPTY';
            break;
    }
}

Pretty straight forward. Ain’t it?

Now that we have all the classes ready, we need to style these so that all the icons come up on the board. Let us take a look at the complete style.css file:

#board {
    height: 400px;
    width: 400px;
}

#board .column {
    height: 50px;
    width: 50px;
    background: #fee472;
    float: left;
    font-size: 45px;
}

#board .column.dark {
    background: #00B392;
}

#board .column div {
    height: 50px;
    width: 50px;
}

#board .column .WHITE_KING {
    background: url('../images/wKing.png');
}

#board .column .WHITE_QUEEN {
    background: url('../images/wQueen.png');
}

#board .column .WHITE_ROOK {
    background: url('../images/wRook.png');
}

#board .column .WHITE_BISHOP {
    background: url('../images/wBishop.png');
}

#board .column .WHITE_KNIGHT {
    background: url('../images/wKnight.png');
}

#board .column .WHITE_PAWN {
    background: url('../images/wPawn.png');
}


#board .column .BLACK_KING {
    background: url('../images/bKing.png');
}

#board .column .BLACK_QUEEN {
    background: url('../images/bQueen.png');
}

#board .column .BLACK_ROOK {
    background: url('../images/bRook.png');
}

#board .column .BLACK_BISHOP {
    background: url('../images/bBishop.png');
}

#board .column .BLACK_KNIGHT {
    background: url('../images/bKnight.png');
}

#board .column .BLACK_PAWN {
    background: url('../images/bPawn.png');
}

#board .column .EMPTY {
    background: none;
}

Even though the style.css file is ready, we don’t have images/icons of the pieces ready yet. So our next task is to get hold of a few images of the chess pieces. You can probably take it from Wikipedia page for chess pieces:

Save these as separate image files. Name them as given in the css file.

We are almost done with Part 1 of this tutorial !!!

The last piece of the puzzle is to call the drawBoard() function on the page load. This is done using the jQuery ready function:

$(function(){
    drawBoard(board);
});

So we are ready to see the output of our great program. Go to your favorite web browser (Google Chrome) and then open the index.html file. You will see the following beautiful chess board:

Congratulations. You have completed the first part of this series. It may not seem like much, but in a few small steps like these, you will be ready to write your own little chess program!

You can download the final source code from this tutorial here. The latest source code will also be available in the github repository.

Next – Part 2: The 0x88 board representation

Let me know if you are following this so that I can gauge the interest in these type of articles.

User-agent: *
Disallow: /wp-admin
Disallow: /wp-includes

The problem with this is that there are many bots which will hit you very hard if you don’t specifically block them. Here is a better robots.txt file:

User-agent: *

Disallow: /wp-content/
Disallow: /wp-icludes/
Disallow: /trackback/
Disallow: /wp-admin/
Disallow: /archives/
Disallow: /category/
Disallow: /tag/*
Disallow: /tag/
Disallow: /wp-*
Disallow: /login/
Disallow: /*.js$
Disallow: /*.inc$
Disallow: /*.css$
Disallow: /*.php$

User-agent: All
Allow: /

User-agent: Googlebot-Image
Disallow: /

User-agent: ia_archiver
Disallow: /

User-agent: duggmirror
Disallow: /

User-agent: Yandex
Disallow: /

User-agent: moget
User-agent: ichiro
Disallow: /

User-agent: NaverBot
User-agent: Yeti
Disallow: /

User-agent: Baiduspider
User-agent: Baiduspider-video
User-agent: Baiduspider-image
Disallow: /

User-agent: sogou spider
Disallow: /

User-Agent: Slurp
Disallow: /

Feel free to fork and create better versions.

Just keep in mind that there are still a lot of other bad/useless bots out there which will consume your resources, but many of them do not respect robots.txt. You will have to block their IPs in your .htaccess (or other similar conf files depending on your server).

Progress is made by lazy men looking for easier ways to do things

- Robert A. Heinlein

Once while waiting for a badly coded, often-crashing Javascript-heavy page to load I leaned back on my chair too far and smacked my head on a file cabinet. To this day it’s the most immersive experience I’ve had on the web”

- mrmessiah