Back Up Next

0x88 Move Generation

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 the point of the whole scheme.

The advantages of the 0x88 scheme are:

  1. It's acceptably fast.
  2. The code is small and not complex.
  3. 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.

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.

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 the rook when 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.

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 combine 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.  The 0x88 system helps you a little with this, but the code is still ugly.

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 the result of the subtraction is 1, you know that the second square was to the right of the first square.  If your result was 16, you were one square up the file from the first square.

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 fewer than 257 elements, but I won't get into that trivial detail.

For example, in the element corresponding to a delta of 1, you have the king, queen, and rook bits set.  If the delta is 17, you have bits set for king, queen, bishop, and white pawn.

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 traverse the ray from the source to destination square, looking for intervening pieces.

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: 11/04/02