# 0x88

History
When I was at the Hong Kong WCCC in 1995, I had some conversations with David Kittinger.  He told me about a move generation scheme, whose name I promptly forgot.  When I came back home, I explained this scheme online many times.  Since I didn't know the name, I couldn't give it the proper name, and it kind of acquired a name.  The name that seems to have stuck is "0x88", which is means hexidecimal 88.

The reason it's called 0x88 is that this constant is critical in the implementation of the scheme.

The advantages of the 0x88 scheme are:

It's acceptably fast.
The code is small and not complex.
You get a good in-check routine as a side-effect.
Board representation and basic mechanics
A regular chessboard is 8 x 8 squares.  The "standard" numbering of these squares is 0..63, with a1 being 0, b1 being 1, a2 being 8, h8 being 63, and you can fill in the rest for yourself.  Note that this is zero-based, since we are not using Pascal here, of course.

0x88 uses a board that is a bit different.  The board is 128 squares.  a1..h1 are still 0..7, but there are un-used files i-p to the right of the h-file.  Essentially it's as if you take a dummy chessboard and put it to the right of the "real" chessboard.

So a2 ends up being 16, a8 ends up being 112, and h8 is element 119.

The formula for any square is:

index = rank * 16 + file

You are probably wondering why this is done.  There are a couple of reasons, but I'll only discuss the most critical in this section.   The reason it is done is so you can detect if an iterated ray traversal has reached the left or right edges of the board.

I'm sure that was clear as mud.  Let's assume that you have an 8 x 8 board, and we want to consider a rook on the square a3, which is index 16 on an 8 x 8 board.  Let's generate destination squares for this rook.  We'll start by going up the a-file.  To go up a file, we'll add 8 to the index.  So we start from 16, add 8, and get 24.  Is this on the board?  With this 8 x 8 board, we can check to see if the index is less than 64.  24 is less than 64, so we're on the board.  Next destination is 32, then 40, then 48, then 56, then 64.  64 is not less than 64, so this one is off the board, and we stop.

Okay, let's go down the a-file from a3 now.  a3 is 24, subtracting 8 gets us 16.  Is that on the board?  The test here is greater than or equal to zero, and 16 is.  So index 16 (a2) is on the board.  The next destination is 8, that's on the board, then 0, which is on the board, then -8, which is less than zero, so that is off the board.

We've used a different test in each of these cases, which is annoying.  It would be much better if we could use one piece of code to do this, which would require one test.  The test can be:

if ((index < 0) || (index >= 64))

That's really two tests, which is inefficent.  We can do this in one test, since the board size is a power of two:

if (!(index & 0x40))

This catches both the case where the index has gone off the bottom of the board, and the case where it's gone off the top.  In the top case, the 0x40 bit is set because we've exceeded 64, and in the bottom case it's set thanks to the way in which negative numbers are represented in two's-complement binary.

If you don't understand this, you'd better stop and figure it out, because unless you understand it, the rest of this page is going to read like hash.

If you are paying attention, you will have noticed that in my example, the rook went up the file and down the file, but it didn't go left or right.  The reason it didn't go left or right is that this system fails if you try to go left or right.  The system cannot detect if an iterated ray traversal has gone off the right or left edges of the board.  If you start on a3, and you increment your index by one until you end up on h3, you can increment the index again, which gets you to a4.  a4 is still on the board, and there is no elegant trick you can use to figure out if you've gone past the h-file.  You have the same problem if you try to go left -- if you start on a3 and decrement, you are on h2, which is still on the board, but there is no piece  that moves like this in chess.

So the problem with a 64-square board is that it is difficult to detect that you have "wrapped around" from left to right and vice versa.

The 0x88 system solves this problem.  By using a 16 x 8 board, you get a marker bit.  You can tell if you've gone off into the unused right board, because the 0x08 bit is set if you've done this.  h1 is 7, if you add one you get 8, which has the 0x08 bit set.  None of the "left" (real) board squares has the 0x08 bit set, and all of the "right" (dummy) board squares have this bit set.   If you are on a3 and you try to go to the left one square, you're on p2, which is in the dummy board, which has the 0x08 bit set.

You can combine the 0x08 test with the 0x80 test (0x80 rather than 0x40, since things have changed a bit since there are 128 squares), and do both tests at the same time.  0x80 combined with 0x08 is 0x88, hence the name of the scheme.

If you understand what I'm talking about, it should be clear now how 0x88 works.  Your move generation loop looks like this:

while (!(index & 0x88)) {

    GenerateMove(index);

    index += delta;

}

This is extremely elegant.  You can do something like this:

void GenerateMoves(int square, int * ptab)

{

    for (; *ptab; ptab++) {

        int    index;

 

        for (index = square; !(index & 0x88); index += *ptab)

            GenerateMove(index);

    }

}

 

int argdBishop[] = { 17, 15, -17, -15, 0 };

 

void GenerateBishopMoves(int square)

{

    GenerateMove(square, argdBishop);

}

This is fast enough, and there is very little code.  The only thing that distinguishes a bishop from a rook or a queen is the data in the little table, so obviously you can add in the rest of the pieces in a few seconds without adding any significant code.

Of course you still have special code for  with pawns and castling, but every system has those problems.

A bonus
Another thing you get from the 0x88 system is quick detection of attacks, and this is the other reason for the 16 x 8 board.  If you subtract two indexes of squares on that board, you get a value that accurately describes the relationship between the two squares.

For example, if you subtract the index of square A, from the index of square B, and you get the answer 1, you know that A is one square to the left of B.  If you get 16, you know that A is immediately below B on the board.

This is not true if you are using an 8 x 8 board.  It's true that d1 - c1 = 1, but a2 - h1 is also 1.  This problem of confusion due to "wrap-around" is solved if you use a 128-element board.

You can make use of this if you are trying to write an in-check function or something else that needs to know if a piece on one square attacks another.

You can make an array of approximately 257 elements (-128 ... +128), which is appropriately filled in with bit-fields that describe which pieces can conceivably move between two squares separated by some delta.  You can use a few less  than 257 elements, but I won't spend time working that out here.

For example, in the element corresponding to a delta of 1, you have the king, queen, and rook bits set, since these pieces can all move one square sideways.  If the delta is 17, you have bits set for king, queen, bishop, and white pawn, since these can all move one up and to the right.

This can be used to make an acceptably fast in-check routine.  You get a delta by subtracting the attacker's square from the target's square, add 128 to it so you avoid a negative index, and look up in the pre-computed attack array to see if a piece of the attacker's type could conceivably get to the destination square in one move.

If you determine that it's possible to get to the destination square, you check to see if you are looking at a sliding piece (queen, rook, bishop).  If not, you are done.

If the piece is a sliding piece, you can use your delta value to index another array to get a value that you can use to traverse the ray from the source to destination square, looking for intervening pieces.

For example, let's say that you are trying to see if a rook can get from a1 to h1.  h1 is 8, a1 is 0, and 8 - 0 is 8.  You look up the value in the "attacks" array, and you see that a rook and a queen can both get from a1 to h1.  So you know that you have to traverse the ray.  You look up another value in a "vector" array, and you discover that in order to traverse this vector you add 1 to your index each time.

If you were trying to go from a1 to h8, you would have found a 17 in the vector array.

The resulting routine, which I won't provide code for, is fairly easy to write and is acceptably fast.

 
Send mail to brucemo@seanet.com with questions or comments about this web site.
Copyright © 2001 Bruce Moreland
Last modified: 01/24/03
