[Guide] The 0x88 representation

0x88: This approach fascinates me and I can only congratulate whoever came up with it (maybe one of my countless readers(!) can enlighten me).

It goes something like this.

Instead of having a 8x8 array, you make it a 16x8 array. Basically what happens is you'll get two boards next to each other (like the picture above). The left board represents the real board, and the right a dummy board used to check for off the board moves (amongst other things).

As you can see the first rank (a1..h1) have the index numbers 0..7. Then comes the dummy board with indexes 8..15. Then the second rank (a2..h2) with index 16..23, and then the dummy board again with indexes 24..31. Etc.

Now what does this do?

Well, it's not obvious at first, but the hexadecimal number 0x88 (136 in decimal form) is written 1000 1000 in binary form. As you can see the 4th and 8th bits are "set". If you play around a bit with this you can get a table:

Real board       Dummy board      Real..Dummy     
Index    Binary  Index    Binary  Index    Binary 
0        0000    8        1000    117      0111 0101     
1        0001    9        1001    118      0111 0110       
2        0010    10       1010    119      0111 0111       
3        0011    11       1011     .              
4        0010    12       1100    120      0111 1000       
5        0101    13       1101     .
6        0110    14       1110    180      1011 0100       
7        0111    15       1111    222      1101 1110   etc.

Notice how, without exceptions, the dummy board has the 4th (or 8th) bit set to 1, while on the real board those particular bits are always 0. This works all the way up to index 127.

Actually it works all the way up to 255 since the 8th bit takes care of the numbers from 128 to 255, after that squares appears to be on the real board again (like index 256 = 0001 0000 0000), but really you shouldn't check these higher numbers in the first place. Just keeping it in mind.

Great, so what?

The nifty thing is you can now do an extremely simple (and fast) check to see if the square is on the board or not. Like this:

if((aSquareIndex & 0x88) != 0)
    System.out.println("Square not on the board");

This simple check will return true if the square is off the board, and false if it's on the board.

The & operator

The '&' operator compares every bit in the aSquareIndex to the 0x88 hexadecimal. All the zeros in 0x88 will return a zero in the resulting answer, and all the ones in 0x88 will return whatever is on that position in aSquareIndex.

So let's say we're comparing the index 1 (0000 0001 in binary form) with the 0x88 (1000 1000 in binary form). The result we get will be:

0x88   1000 1000
1      0000 0001

First take all the zeros from 0x88

Result ?000 ?000

Now add the last two places from '1'
(since 0x88 has ones there)

Result 0000 0000 -> 0 (in decimal form)

Let's try this instead; compare 14 (0000 1110) with 0x88

0x88   1000 1000
14     0000 1110

First take all the zeros from 0x88

Result ?000 ?000


Now add the last two places from '14'
(since 0x88 has ones there)

Result 0000 1000 -> 8 (in decimal form)

So you can see that the indexes that represent the real board will always result in a 0 in this check, while indexes on the dummy board will result in a non-zero value (actually 8 or 136 depending on the index).

Moving on

This will be a very important part of the move generating process further on.

So now on to some actual coding, making the Board-class.