Thread: How to rotate a 64-bit BitBoard?

  1. #1
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229

    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.
    Last edited by cyberfish; 07-19-2007 at 08:59 AM. Reason: clarifying question

  2. #2
    Registered User
    Join Date
    Feb 2006
    Posts
    312
    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.
    Last edited by Bench82; 07-19-2007 at 02:50 PM. Reason: Correction: Getting left and right confused

  3. #3
    Registered User
    Join Date
    Feb 2006
    Posts
    312
    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.

  4. #4
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    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;
    }
    Callou collei we'll code the way
    Of prime numbers and pings!

  5. #5
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    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.

  6. #6
    Registered User manofsteel972's Avatar
    Join Date
    Mar 2004
    Posts
    317
    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.
    Last edited by manofsteel972; 07-19-2007 at 09:31 PM.
    "Knowledge is proud that she knows so much; Wisdom is humble that she knows no more."
    -- Cowper

    Operating Systems=Slackware Linux 9.1,Windows 98/Xp
    Compilers=gcc 3.2.3, Visual C++ 6.0, DevC++(Mingw)

    You may teach a person from now until doom's day, but that person will only know what he learns himself.

    Now I know what doesn't work.

    A problem is understood by solving it, not by pondering it.

    For a bit of humor check out xkcd web comic http://xkcd.com/235/

  7. #7
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    thank you, I will look it up

  8. #8
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    Quote Originally Posted by cyberfish View Post
    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.
    Callou collei we'll code the way
    Of prime numbers and pings!

  9. #9
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    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

  10. #10
    Registered User
    Join Date
    May 2008
    Posts
    1

    There's another dirty trick

    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.

  11. #11
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Whoa, ancient thread!
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 16
    Last Post: 11-23-2007, 01:48 PM
  2. 64 bit programs
    By learning in forum C++ Programming
    Replies: 17
    Last Post: 05-10-2007, 11:26 PM
  3. A Question About Unit Testing
    By Tonto in forum C++ Programming
    Replies: 2
    Last Post: 12-14-2006, 08:22 PM
  4. bit patterns of negtive numbers?
    By chunlee in forum C Programming
    Replies: 4
    Last Post: 11-08-2004, 08:20 AM
  5. Array of boolean
    By DMaxJ in forum C++ Programming
    Replies: 11
    Last Post: 10-25-2001, 11:45 PM