How to rotate a 64-bit BitBoard?

Hi,
I am currently programming a chess game using bitboards.
From what I have read on the internet, the best way (at least the most commonly used way) to generate moves for sliding pieces (rooks, bishops, and queens), involves the use of rotated bitboards. However, I cannot seem to come up with or find an efficient way to rotate bitboards.

For people not into chess programming, what I want to achieve is to transform something like:

Code:

11111111 00000000 00000000 00000000 00000000 00000000 00000000 00000000

to:

Code:

10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000

and:

Code:

00000001 00000001 00000001 00000001 00000001 00000001 00000001 00000001

and:

Code:

00000000 00000000 00000000 00000000 00000000 00000000 00000000 11111111

Is there any efficient way to do this?

Thank you very much.

Perhaps the best way would be to treat your bitboard as a virtual "2D matrix". If you perform all your calculations based on x and y, (Where Y is a vertical coordinate from 0-7, and X is horizontal 0-7), the position in your 1D bit board will be y*8 + x

From there, its a simple mathematical translation, using the relationship between X and Y

eg, for a translation which rotates 90 degrees right, the bit at the virtual coords [ X, Y ] translates directly to [ 7-Y, X ]

a left-rotation would be the opposite, [ X. Y ] mapped on to [ Y, 7-X ]


Here's a short program to illustrate (using a nonstandard MSVC++ type, unsigned __int64 as a bitboard.. this snippet may not compile on anything other than MSVC++)

Code:

#include <iostream>

typedef unsigned __int64 bitboard;

bool get(bitboard const board, int x, int y)
{
    int pos = y * 8 +x;
    return ( board >> pos ) & 1 ;
}

bitboard set(int x, int y, bool val)
{
    int pos = y*8+x;
    return static_cast<bitboard>(val) << pos;
}

int xrot(int x, int y)
{
    return 7-y;
}

int yrot(int x, int y)
{
    return x;
}

bitboard rot(bitboard const from)
{   
    bitboard to(0);
    for(int y(0); y<8; ++y)
        for( int x(0); x<8; ++x)
            to |= set( xrot(x,y), yrot(x,y), get(from, x, y) );
    return to;
}

void print(bitboard const board)
{   
    for(int y(0); y<8; ++y)
    {
        for( int x(0); x<8; ++x)
            std::cout <<  get(board, x, y) << " " ;
        std::cout << "\n";
    }
}

int main()
{
    bitboard board = static_cast<bitboard>(255)<<32;
    print(board);
    std::cout << "\n\n";
    print( rot(board) );

}

If the code doesn't compile for you, then hopefully you'll be able to see what's going on to some extent. It causes the bitboard to 'rotate right' 90 degrees.

Note for the above post - if I were to do that program properly, i would almost certainly wrap the X and Y coords into a class of their own (as i would for the bitboard.. which might be better represented as a std::bitset<64> ), that was abit of a crude C-like example.

Depends on how you define 'efficient'. You're not going to be able to avoid doing about 64 bit comparisons for every rotation.

Code:

#include <stdio.h>

void rotbits (unsigned char bits[8]) {
   int i, j;
   unsigned char i_mask, j_mask;

   // Change the direction of the rotation by changing the direction of the masks
   for (i = 0, i_mask = 0x01; i < 8; ++i, i_mask <<= 1)
      for (j = 7, j_mask = 0x80; j > i; --j, j_mask >>= 1)
         // If the bits are not the same, flip both bits
         if (((bits[i] & j_mask) != 0) != ((bits[j] & i_mask) != 0)) {
            bits[i] ^= j_mask;
            bits[j] ^= i_mask;
         }
   return;
}

int main (void) {
   unsigned char foo[8] = {0xFF, 0x00, 0x00, 0x00, 0x0F, 0x00, 0x00, 0x00};
   int i;

   for (i = 0; i < 8; ++i) {
      printf ("&#37;2X\n", foo[i]);
   }

   printf ("rotate...\n");
   rotbits (foo);

   for (i = 0; i < 8; ++i) {
      printf ("%2X\n", foo[i]);
   }

   return 0;
}

to Bench82:
thank you for your demonstration, I only need to subsitude in "long long int" (the equivalent non-standard type in gcc) for "__int64" for the code to compile. This is the algorithm that I initially came up with, too, but I wasn't sure if this is the most efficient way.

to QuestionC:
thank you for the code. Took me a while to get the algorithm, but I think I get it now.

Depends on how you define 'efficient'. You're not going to be able to avoid doing about 64 bit comparisons for every rotation.

that was what I was afraid of. I was kind of hoping for some kind of magic =) I guess one doesn't exist then.

I want to find the most efficient algorithm because the board has to be rotated 3 times at every node of the minimax tree.

Thank you all for your help.

You might want to look up Darkthought. There is an intersting article called How Darkthought Plays chess that might be of interest.

[edit] perhaps you can create multiple bitboards that are already rotated and just update them instead of having a single bitboard that you manipulate.

thank you, I will look it up

Originally Posted by cyberfish

to Bench82:
thank you for your demonstration, I only need to subsitude in "long long int" (the equivalent non-standard type in gcc) for "__int64" for the code to compile. This is the algorithm that I initially came up with, too, but I wasn't sure if this is the most efficient way.

to QuestionC:
thank you for the code. Took me a while to get the algorithm, but I think I get it now.


that was what I was afraid of. I was kind of hoping for some kind of magic =) I guess one doesn't exist then.

I want to find the most efficient algorithm because the board has to be rotated 3 times at every node of the minimax tree.

Thank you all for your help.

Well... there is one trick, but it's pretty dirty.

Code:

class bitboard {
   unsigned char bit[8];
   bool flipbit;

public:
   void lazyflip() { flipbit = !flipbit; }

   unsigned char at (unsigned int x, unsigned int y) {
      if (flipbit)
         return bit[y] & (1 >> x);
      else
         return bit[x] & (1 >> y);
   }
};

Forgive syntax errors. I am sure the idea is clear from the code.

Depending on the ratio of flips to board accesses, this may be faster.

Well... there is one trick, but it's pretty dirty.

Code:

class bitboard {
   unsigned char bit[8];
   bool flipbit;

public:
   void lazyflip() { flipbit = !flipbit; }

   unsigned char at (unsigned int x, unsigned int y) {
      if (flipbit)
         return bit[y] & (1 >> x);
      else
         return bit[x] & (1 >> y);
   }
};

Forgive syntax errors. I am sure the idea is clear from the code.

Depending on the ratio of flips to board accesses, this may be faster.

wow, this is amazing =) never thought of this

however, I think I will stick to manofsteel972's suggestion of maintaining rotated bitboards because the ratio of flips to board accesses is pretty low.

Thank you

For all those who (like me) stumble upon this thread and can't believe there's no alternative to testing every single bit, here's a version that reduces the number of instructions a bit (at the cost of readability).

Code:

#include <stdio.h>

// gcc
typedef unsigned long long bitboard;
// msvc
//typedef unsigned __int64 bitboard;

// rotate bitboard 90° to the left
inline bitboard rotate(register bitboard b) {
        register bitboard t; // temporary

        // reflect b against diagonal line going through bits 1<<7 and 1<<56
        t = (b ^ (b >> 63)) & 0x0000000000000001; b ^= t ^ (t << 63);
        t = (b ^ (b >> 54)) & 0x0000000000000102; b ^= t ^ (t << 54);
        t = (b ^ (b >> 45)) & 0x0000000000010204; b ^= t ^ (t << 45);
        t = (b ^ (b >> 36)) & 0x0000000001020408; b ^= t ^ (t << 36);
        t = (b ^ (b >> 27)) & 0x0000000102040810; b ^= t ^ (t << 27);
        t = (b ^ (b >> 18)) & 0x0000010204081020; b ^= t ^ (t << 18);
        t = (b ^ (b >>  9)) & 0x0001020408102040; b ^= t ^ (t <<  9);

        // reflect b against vertical center line
        t = (b ^ (b >>  7)) & 0x0101010101010101; b ^= t ^ (t <<  7);
        t = (b ^ (b >>  5)) & 0x0202020202020202; b ^= t ^ (t <<  5);
        t = (b ^ (b >>  3)) & 0x0404040404040404; b ^= t ^ (t <<  3);
        t = (b ^ (b >>  1)) & 0x0808080808080808; b ^= t ^ (t <<  1);

        return b;
}

void dump(bitboard b) {
        int x,y;
        for (y=0; y<8; y++) {
                for (x=0; x<8; x++) {
                        printf(b&1 ? " X" : " -");
                        b >>= 1;
                }
                printf("\n");
        }
}

int main() {
        bitboard test = 0x40F858187E3C1800;
        dump(test);
        printf("=================\n");
        dump(rotate(test));
}

If you want to understand why this works, I suggest you

1. Read http://www-cs-faculty.stanford.edu/~knuth/fasc1a.ps.gz, which explains why every one of the bit-twiddling lines above swaps all the bits that are set in the hex constant with those 63, 54, 45, ... positions to the left.
2. Grab a piece of squared paper, mark off 8x8 squares, fill in the corresponding bit positions and convince yourself that the swappings in the two blocks do what the comments say.
3. Convince yourself that the two reflections indeed are the same as the desired rotation.

Whoa, ancient thread!