Flipping Mirroring and Rotating

From Chessprogramming wiki
Jump to: navigation, search

Home * Board Representation * Bitboards * Flipping, Mirroring and Rotating

Barbara Mittman, Forever IV [1]

Flipping, Mirroring and Rotating
might be useful to transform bitboards in various ways. Considering the fourfold symmetry of the chessboard, the first paragraph covers the whole bitboard performing bit-twiddling-techniques. Various multiplications to flip or mirror certain subsets of the bitboard like files, ranks and even diagonals and anti-diagonals are mentioned in the second section.

The whole Bitboard

Following C-routines perform parallel prefix algorithms to swap bits in various ways. They are not intended to use extensively inside a chess program - e.g. to implement rotated or reverse bitboards on the fly - but may be used for initialization purposes. They may convert sets between the eight different square mappings, considering rank-file or file-rank endianness. An exception might be the vertical flipping, which could be done by one fast x86-64 byteswap (bswap) instruction [2] . See the bswap-application of hyperbola quintessence to determine vertical or diagonal sliding attacks. Flipping, mirroring and rotating is distributive over the basic bitwise operations such as intersection, union, one's complement and xor, as demonstrated in hyperbola quintessence as well.

Beside portable routines, there are optimized routines taking advantage of compiler intrinsics, to use x86-64 processor instructions like byteswap (bswap) as mentioned and rotate (ror, rol) [3] .

Flip and Mirror

This is about

. 1 1 1 1 . . .   . 1 1 1 1 . . .   . 1 1 1 1 . . .   . 1 1 1 1 . . .
. 1 . . . 1 . .   . 1 . . . 1 . .   . 1 . . . 1 . .   . 1 . . . 1 . .
. 1 . . . 1 . .   . 1 . . . 1 . .   . 1 . . . 1 . .   . 1 . . . 1 . .
. 1 . . 1 . . .   . 1 . . 1 . . .   . 1 . . 1 . . .   . 1 . . 1 . . .
. 1 1 1 . . . .   . 1 1 1 . . . .   . 1 1 1 . . . .   . 1 1 1 . . . .
. 1 . 1 . . . .   . 1 . 1 . . . .   . 1 . 1 . . . .   . 1 . 1 . . . .
. 1 . . 1 . . .   . 1 . . 1 . . .   . 1 . . 1 . . .   . 1 . . 1 . . .
. 1 . . . 1 . .   . 1 . . . 1 . .   . 1 . . . 1 . .   . 1 . . . 1 . .
       -                 |                  /               \
 flipVertical     mirrorHorizontal  flipDiagA1H8      flipDiagA8H1
       -                 |                /                   \
. 1 . . . 1 . .   . . . 1 1 1 1 .   . . . . . . . .   . . . . . . . .
. 1 . . 1 . . .   . . 1 . . . 1 .   . . . . . . . .   1 1 1 1 1 1 1 1
. 1 . 1 . . . .   . . 1 . . . 1 .   1 . . . . 1 1 .   1 . . . 1 . . .
. 1 1 1 . . . .   . . . 1 . . 1 .   . 1 . . 1 . . 1   1 . . . 1 1 . .
. 1 . . 1 . . .   . . . . 1 1 1 .   . . 1 1 . . . 1   1 . . 1 . . 1 .
. 1 . . . 1 . .   . . . . 1 . 1 .   . . . 1 . . . 1   . 1 1 . . . . 1
. 1 . . . 1 . .   . . . 1 . . 1 .   1 1 1 1 1 1 1 1   . . . . . . . .
. 1 1 1 1 . . .   . . 1 . . . 1 .   . . . . . . . .   . . . . . . . .

Vertical

. 1 1 1 1 . . .     . 1 . . . 1 . .
. 1 . . . 1 . .     . 1 . . 1 . . .
. 1 . . . 1 . .     . 1 . 1 . . . .
. 1 . . 1 . . .     . 1 1 1 . . . .
. 1 1 1 . . . .     . 1 . . 1 . . .
. 1 . 1 . . . .     . 1 . . . 1 . .
. 1 . . 1 . . .     . 1 . . . 1 . .
. 1 . . . 1 . .     . 1 1 1 1 . . .

Flipping a bitboard vertical reverses all eight bytes - it performs a little- big-endian conversion or vice versa. A scalar square may be flipped vertically by xor 56.

sq' = sq ^ 56;

The obvious approach with 21 operations, note that the shifts by 56 don't need masks:

/**
 * Flip a bitboard vertically about the centre ranks.
 * Rank 1 is mapped to rank 8 and vice versa.
 * @param x any bitboard
 * @return bitboard x flipped vertically
 */
U64 flipVertical(U64 x) {
    return  ( (x << 56)                           ) |
            ( (x << 40) & C64(0x00ff000000000000) ) |
            ( (x << 24) & C64(0x0000ff0000000000) ) |
            ( (x <<  8) & C64(0x000000ff00000000) ) |
            ( (x >>  8) & C64(0x00000000ff000000) ) |
            ( (x >> 24) & C64(0x0000000000ff0000) ) |
            ( (x >> 40) & C64(0x000000000000ff00) ) |
            ( (x >> 56) );
}

The parallel prefix-approach takes 13 operations, to swap bytes, words and double-words in a SWAR-wise manner, performing three delta swaps:

/**
 * Flip a bitboard vertically about the centre ranks.
 * Rank 1 is mapped to rank 8 and vice versa.
 * @param x any bitboard
 * @return bitboard x flipped vertically
 */
U64 flipVertical(U64 x) {
   const U64 k1 = C64(0x00FF00FF00FF00FF);
   const U64 k2 = C64(0x0000FFFF0000FFFF);
   x = ((x >>  8) & k1) | ((x & k1) <<  8);
   x = ((x >> 16) & k2) | ((x & k2) << 16);
   x = ( x >> 32)       | ( x       << 32);
   return x;
}

Using the x86-64 _byteswap_uint64 or bswap64 intrinsics only takes one processor instruction in 64-bit mode.

/**
 * Flip a bitboard vertically about the centre ranks.
 * Rank 1 is mapped to rank 8 and vice versa.
 * @param x any bitboard
 * @return bitboard x flipped vertically
 */
U64 flipVertical(U64 x) {
   return _byteswap_uint64(x);
}

Horizontal

. 1 1 1|1 . . .     . . . 1 1 1 1 .
. 1 . . . 1 . .     . . 1 . . . 1 .
. 1 . . . 1 . .     . . 1 . . . 1 .
. 1 . . 1 . . .     . . . 1 . . 1 .
. 1 1 1 . . . .     . . . . 1 1 1 .
. 1 . 1 . . . .     . . . . 1 . 1 .
. 1 . . 1 . . .     . . . 1 . . 1 .
. 1 . .|. 1 . .     . . 1 . . . 1 .

Horizontal mirroring reverses the bits of each byte. A scalar square may be mirrored horizontally by xor 7.

sq' = sq ^ 7;

The parallel prefix-algorithm swaps bits, bit-duos and nibbles in a SWAR-wise manner, performing three delta swaps, 15 operations:

/**
 * Mirror a bitboard horizontally about the center files.
 * File a is mapped to file h and vice versa.
 * @param x any bitboard
 * @return bitboard x mirrored horizontally
 */
U64 mirrorHorizontal (U64 x) {
   const U64 k1 = C64(0x5555555555555555);
   const U64 k2 = C64(0x3333333333333333);
   const U64 k4 = C64(0x0f0f0f0f0f0f0f0f);
   x = ((x >> 1) & k1) | ((x & k1) << 1);
   x = ((x >> 2) & k2) | ((x & k2) << 2);
   x = ((x >> 4) & k4) | ((x & k4) << 4);
   return x;
}

Replacing bitwise 'or' of disjoint sets by 'add' and shift left by appropriate multiply - taking advantage of x86 lea instruction for multiplication with 2 and 4:

/**
 * Mirror a bitboard horizontally about the center files.
 * File a is mapped to file h and vice versa.
 * @param x any bitboard
 * @return bitboard x mirrored horizontally
 */
U64 mirrorHorizontal (U64 x) {
   const U64 k1 = C64(0x5555555555555555);
   const U64 k2 = C64(0x3333333333333333);
   const U64 k4 = C64(0x0f0f0f0f0f0f0f0f);
   x = ((x >> 1) & k1) +  2*(x & k1);
   x = ((x >> 2) & k2) +  4*(x & k2);
   x = ((x >> 4) & k4) + 16*(x & k4);
   return x;
}

Using rotates instead of shifts in some clever way takes 13 operations (introduced by Steffan Westcott). Disadvantage is each operation depends on the previous one, while the lea-approach gains some parallelism with same number of instructions.

/**
 * Mirror a bitboard horizontally about the center files.
 * File a is mapped to file h and vice versa.
 * @param x any bitboard
 * @return bitboard x mirrored horizontally
 */
U64 mirrorHorizontal (U64 x) {
   const U64 k1 = C64(0x5555555555555555);
   const U64 k2 = C64(0x3333333333333333);
   const U64 k4 = C64(0x0f0f0f0f0f0f0f0f);
   x ^= k4 & (x ^ rotateLeft(x, 8));
   x ^= k2 & (x ^ rotateLeft(x, 4));
   x ^= k1 & (x ^ rotateLeft(x, 2));
   return rotateRight(x, 7);
}

Generalized

In Knuth's The Art of Computer Programming, Volume 4, Fascicle 1: Bitwise tricks & techniques, page 9, Knuth interprets the magic masks as 2-adic fractions [4] :

k1 = ...101010101010101010101010101010101 = -1/3
k2 = ...100110011001100110011001100110011 = -1/5
k4 = ...100001111000011110000111100001111 = -1/17

How the masks look on a chess board:

k1                  k2                  k4
-1/3                -1/5                -1/17
0x5555555555555555  0x3333333333333333  0x0F0F0F0F0F0F0F0F
1 . 1 . 1 . 1 .     1 1 . . 1 1 . .     1 1 1 1 . . . .
1 . 1 . 1 . 1 .     1 1 . . 1 1 . .     1 1 1 1 . . . .
1 . 1 . 1 . 1 .     1 1 . . 1 1 . .     1 1 1 1 . . . .
1 . 1 . 1 . 1 .     1 1 . . 1 1 . .     1 1 1 1 . . . .
1 . 1 . 1 . 1 .     1 1 . . 1 1 . .     1 1 1 1 . . . .
1 . 1 . 1 . 1 .     1 1 . . 1 1 . .     1 1 1 1 . . . .
1 . 1 . 1 . 1 .     1 1 . . 1 1 . .     1 1 1 1 . . . .
1 . 1 . 1 . 1 .     1 1 . . 1 1 . .     1 1 1 1 . . . .

A parametrized flip, mirror or reverse (mirror and flip) might be generalized to let the compiler produce mentioned routines with flip or mirror as constant (or template) parameter. Otherwise, without compile time constants, the division at runtime is too expensive.

/**
 * Flip, mirror or reverse a bitboard
 * @param x any bitboard
 * @param flip the bitboard
 * @param mirror the bitboard
 * @return bitboard x flipped, mirrored or reversed
 */
U64 flipMirrorOrReverse(U64 x, bool flip, bool mirror)
{
   for (U32 i = 3*(1-mirror); i < 3*(1+flip); i++) {
      int s(      1  << i);
      U64 f( C64( 1) << s);
      U64 k( C64(-1) / (f+1) );
      x = ((x >> s) & k) + f*(x & k);
   }
   return x;
}

The loop variable 'i' runs from following ranges based on the boolean (0,1) parameters 'flip' and 'mirror':

mirror:   for (U32 i = 0; i < 3; i++)
flip:     for (U32 i = 3; i < 6; i++)
reverse := mirror && flip
          for (U32 i = 0; i < 6; i++)

With following formula for the delta swaps constants ...

shift(i)  := s(i) := 1 << i
factor(i) := f(i) := 1 << s(i)
mask(i)   := k(i) := -1 / (f(i) + 1)

... and therefor following values for i = 0...5:

s(0)  1
f(0)  2
k(0)  0x5555555555555555 = 0xffffffffffffffff / (2+1)

s(1)  2
f(1)  4
k(1)  0x3333333333333333 = 0xffffffffffffffff / (4+1)

s(2)  4
f(2)  16
k(2)  0x0f0f0f0f0f0f0f0f = 0xffffffffffffffff / (16+1)

s(3)  8
f(3)  256
k(3)  0x00ff00ff00ff00ff = 0xffffffffffffffff / (256+1)

s(4)  16
f(4)  65536
k(4)  0x0000ffff0000ffff = 0xffffffffffffffff / (65536+1)

s(5)  32
f(5)  4294967296
k(5)  0x00000000ffffffff = 0xffffffffffffffff / (4294967296+1)

Diagonal

Flip about the Diagonal

. 1 1 1 1 . . /     . . . . . . . .
. 1 . . . 1 . .     . . . . . . . .
. 1 . . . 1 . .     1 . . . . 1 1 .
. 1 . . 1 . . .     . 1 . . 1 . . 1
. 1 1 1 . . . .     . . 1 1 . . . 1
. 1 . 1 . . . .     . . . 1 . . . 1
. 1 . . 1 . . .     1 1 1 1 1 1 1 1
/ 1 . . . 1 . .     . . . . . . . .

A scalar square needs to swap rank and file.

sq' = ((sq >> 3) | (sq << 3)) & 63;
sq' = (sq * 0x20800000) >>> 26; // unsigned 32-bit shift, zeros no sign bits from left

Performing three delta swaps:

/**
 * Flip a bitboard about the diagonal a1-h8.
 * Square h1 is mapped to a8 and vice versa.
 * @param x any bitboard
 * @return bitboard x flipped about diagonal a1-h8
 */
U64 flipDiagA1H8(U64 x) {
   U64 t;
   const U64 k1 = C64(0x5500550055005500);
   const U64 k2 = C64(0x3333000033330000);
   const U64 k4 = C64(0x0f0f0f0f00000000);
   t  = k4 & (x ^ (x << 28));
   x ^=       t ^ (t >> 28) ;
   t  = k2 & (x ^ (x << 14));
   x ^=       t ^ (t >> 14) ;
   t  = k1 & (x ^ (x <<  7));
   x ^=       t ^ (t >>  7) ;
   return x;
}

How the masks look on a chess board:

k1                  k2                  k4
0x5500550055005500  0x3333000033330000  0x0F0F0F0F00000000
1 . 1 . 1 . 1 .     1 1 . . 1 1 . .     1 1 1 1 . . . .
. . . . . . . .     1 1 . . 1 1 . .     1 1 1 1 . . . .
1 . 1 . 1 . 1 .     . . . . . . . .     1 1 1 1 . . . .
. . . . . . . .     . . . . . . . .     1 1 1 1 . . . .
1 . 1 . 1 . 1 .     1 1 . . 1 1 . .     . . . . . . . .
. . . . . . . .     1 1 . . 1 1 . .     . . . . . . . .
1 . 1 . 1 . 1 .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .

Anti-Diagonal

Flip about the Anti-Diagonal

\ 1 1 1 1 . . .     . . . . . . . .
. 1 . . . 1 . .     1 1 1 1 1 1 1 1
. 1 . . . 1 . .     1 . . . 1 . . .
. 1 . . 1 . . .     1 . . . 1 1 . .
. 1 1 1 . . . .     1 . . 1 . . 1 .
. 1 . 1 . . . .     . 1 1 . . . . 1
. 1 . . 1 . . .     . . . . . . . .
. 1 . . . 1 . \     . . . . . . . .

Flip about the Anti-Diagonal results in the bit-reversal of flip about the Diagonal. Thus, a scalar square needs not only swap rank and file, but also xor 63.

sq' = (((sq >> 3) | (sq << 3)) & 63) ^ 63;
sq' = ((sq * 0x20800000) >>> 26) ^ 63;  // unsigned 32-bit shift

Performing three delta swaps:

/**
 * Flip a bitboard about the antidiagonal a8-h1.
 * Square a1 is mapped to h8 and vice versa.
 * @param x any bitboard
 * @return bitboard x flipped about antidiagonal a8-h1
 */
U64 flipDiagA8H1(U64 x) {
   U64 t;
   const U64 k1 = C64(0xaa00aa00aa00aa00);
   const U64 k2 = C64(0xcccc0000cccc0000);
   const U64 k4 = C64(0xf0f0f0f00f0f0f0f);
   t  =       x ^ (x << 36) ;
   x ^= k4 & (t ^ (x >> 36));
   t  = k2 & (x ^ (x << 18));
   x ^=       t ^ (t >> 18) ;
   t  = k1 & (x ^ (x <<  9));
   x ^=       t ^ (t >>  9) ;
   return x;
}

How the masks look on a chess board:

k1                  k2                  k4
0xAA00AA00AA00AA00  0xCCCC0000CCCC0000  0xF0F0F0F00F0F0F0F
. 1 . 1 . 1 . 1     . . 1 1 . . 1 1     . . . . 1 1 1 1
. . . . . . . .     . . 1 1 . . 1 1     . . . . 1 1 1 1
. 1 . 1 . 1 . 1     . . . . . . . .     . . . . 1 1 1 1
. . . . . . . .     . . . . . . . .     . . . . 1 1 1 1
. 1 . 1 . 1 . 1     . . 1 1 . . 1 1     1 1 1 1 . . . .
. . . . . . . .     . . 1 1 . . 1 1     1 1 1 1 . . . .
. 1 . 1 . 1 . 1     . . . . . . . .     1 1 1 1 . . . .
. . . . . . . .     . . . . . . . .     1 1 1 1 . . . .

Rotating

This is about

Rotation can be deduced from flipping and mirroring in various ways.

                    mirrorHorizontal     flipDiagA1H8        flipDiagA8H1
. 1 1 1 1 . . .     . . . 1 1 1 1 .     . . . . . . . .     . . . . . . . .
. 1 . . . 1 . .     . . 1 . . . 1 .     . . . . . . . .     1 1 1 1 1 1 1 1
. 1 . . . 1 . .     . . 1 . . . 1 .     1 . . . . 1 1 .     1 . . . 1 . . .
. 1 . . 1 . . .     . . . 1 . . 1 .     . 1 . . 1 . . 1     1 . . . 1 1 . .
. 1 1 1 . . . .     . . . . 1 1 1 .     . . 1 1 . . . 1     1 . . 1 . . 1 .
. 1 . 1 . . . .     . . . . 1 . 1 .     . . . 1 . . . 1     . 1 1 . . . . 1
. 1 . . 1 . . .     . . . 1 . . 1 .     1 1 1 1 1 1 1 1     . . . . . . . .
. 1 . . . 1 . .     . . 1 . . . 1 .     . . . . . . . .     . . . . . . . .
 flipVertical         rotate180        rotate90clockwise rotate90antiClockwise
. 1 . . . 1 . .     . . 1 . . . 1 .     . . . . . . . .     . . . . . . . .
. 1 . . 1 . . .     . . . 1 . . 1 .     1 1 1 1 1 1 1 1     . . . . . . . .
. 1 . 1 . . . .     . . . . 1 . 1 .     . . . 1 . . . 1     . 1 1 . . . . 1
. 1 1 1 . . . .     . . . . 1 1 1 .     . . 1 1 . . . 1     1 . . 1 . . 1 .
. 1 . . 1 . . .     . . . 1 . . 1 .     . 1 . . 1 . . 1     1 . . . 1 1 . .
. 1 . . . 1 . .     . . 1 . . . 1 .     1 . . . . 1 1 .     1 . . . 1 . . .
. 1 . . . 1 . .     . . 1 . . . 1 .     . . . . . . . .     1 1 1 1 1 1 1 1
. 1 1 1 1 . . .     . . . 1 1 1 1 .     . . . . . . . .     . . . . . . . .

By 180 degrees - Bit-Reversal

. 1 1 1 1 . . .     . . 1 . . . 1 .
. 1 . . . 1 . .     . . . 1 . . 1 .
. 1 . . . 1 . .     . . . . 1 . 1 .
. 1 . . 1 . . .     . . . . 1 1 1 .
. 1 1 1 . . . .     . . . 1 . . 1 .
. 1 . 1 . . . .     . . 1 . . . 1 .
. 1 . . 1 . . .     . . 1 . . . 1 .
. 1 . . . 1 . .     . . . 1 1 1 1 .

Rotating by 180 degrees reverses all bits in a bitboard. A scalar square may be reversed by xor 63:

sq' = sq ^ 63; // 63 - sq;

Deduced from flipping vertically and mirroring horizontally. Both operation may be applied in different orders.

/**
 * Rotate a bitboard by 180 degrees.
 * Square a1 is mapped to h8, and a8 is mapped to h1.
 * @param x any bitboard
 * @return bitboard x rotated 180 degrees
 */
U64 rotate180 (U64 x) {
   return mirrorHorizontal (flipVertical (x) );
}

The resulting code applies six delta swaps:

/**
 * Rotate a bitboard by 180 degrees.
 * Square a1 is mapped to h8, and a8 is mapped to h1.
 * @param x any bitboard
 * @return bitboard x rotated 180 degrees
 */
U64 rotate180 (U64 x) {
   const U64 h1 = C64 (0x5555555555555555);
   const U64 h2 = C64 (0x3333333333333333);
   const U64 h4 = C64 (0x0F0F0F0F0F0F0F0F);
   const U64 v1 = C64 (0x00FF00FF00FF00FF);
   const U64 v2 = C64 (0x0000FFFF0000FFFF);
   x = ((x >>  1) & h1) | ((x & h1) <<  1);
   x = ((x >>  2) & h2) | ((x & h2) <<  2);
   x = ((x >>  4) & h4) | ((x & h4) <<  4);
   x = ((x >>  8) & v1) | ((x & v1) <<  8);
   x = ((x >> 16) & v2) | ((x & v2) << 16);
   x = ( x >> 32)       | ( x       << 32);
   return x;
}

By 90 degrees Clockwise

. 1 1 1 1 . . .     . . . . . . . .
. 1 . . . 1 . .     1 1 1 1 1 1 1 1
. 1 . . . 1 . .     . . . 1 . . . 1
. 1 . . 1 . . .     . . 1 1 . . . 1
. 1 1 1 . . . .     . 1 . . 1 . . 1
. 1 . 1 . . . .     1 . . . . 1 1 .
. 1 . . 1 . . .     . . . . . . . .
. 1 . . . 1 . .     . . . . . . . .

A scalar square swaps rank and file plus xor 56:

sq' = (((sq >> 3) | (sq << 3)) & 63) ^ 56;
sq' = ((sq * 0x20800000) >>> 26) ^ 56; // unsigned 32-bit shift

Deduced from flipping vertically and flipping along the antidiagonal.

/**
 * Rotate a bitboard by 90 degrees clockwise.
 * @param x any bitboard
 * @return bitboard x rotated 90 degrees clockwise
 */
U64 rotate90clockwise (U64 x) {
   return flipVertical (flipDiagA1H8 (x) );
}

Note that

flipVertical (flipDiagA1H8 (x) ) == flipDiagA8H1 (flipVertical (x) )

By 90 degrees Anti-Clockwise

. 1 1 1 1 . . .     . . . . . . . .
. 1 . . . 1 . .     . . . . . . . .
. 1 . . . 1 . .     . 1 1 . . . . 1
. 1 . . 1 . . .     1 . . 1 . . 1 .
. 1 1 1 . . . .     1 . . . 1 1 . .
. 1 . 1 . . . .     1 . . . 1 . . .
. 1 . . 1 . . .     1 1 1 1 1 1 1 1
. 1 . . . 1 . .     . . . . . . . .

A scalar square swaps rank and file plus xor 7:

sq' = (((sq >> 3) | (sq << 3)) & 63) ^ 7;
sq' = ((sq * 0x20800000) >>> 26) ^ 7;  // unsigned 32-bit shift

Deduced from flipping vertically and flipping along the diagonal.

/**
 * Rotate a bitboard by 90 degrees anticlockwise.
 * @param x any bitboard
 * @return bitboard x rotated 90 degrees anticlockwise
 */
U64 rotate90antiClockwise (U64 x) {
   return flipDiagA1H8 (flipVertical (x) );
}

Note that

flipDiagA1H8 (flipVertical (x) ) == flipVertical (flipDiagA8H1 (x) )

Pseudo-Rotation by 45 degrees

The chess-board is four-fold symmetry - thus there is no real 45 degree rotation in the mathematical sense. Anyway we may map diagonals and anti-diagonals to ranks, similar to rotated bitboards.

Clockwise

The 15 diagonals are enumerated by (file - rank) - nibble wise two's complement F == (16) -1, 9 == (16) -7. Two shorter diagonals are file-aligned packed into one rank each. Note that the three lower bits are equal in each rank and bit three (the sign-bit inside a signed nibble) indicates a "negative" diagonal north the main diagonal.

9 A B C D E F 0     9 1 1 1 1 1 1 1
A B C D E F 0 1     A A 2 2 2 2 2 2
B C D E F 0 1 2     B B B 3 3 3 3 3
C D E F 0 1 2 3     C C C C 4 4 4 4
D E F 0 1 2 3 4     D D D D D 5 5 5
E F 0 1 2 3 4 5     E E E E E E 6 6
F 0 1 2 3 4 5 6     F F F F F F F 7
0 1 2 3 4 5 6 7     0 0 0 0 0 0 0 0

We need to rotate the A-H files vertically by 0 to 7 ranks - done parallel prefix wise. One square is therefor mapped by:

sq' = (sq + 8*(sq&7)) & 63;

The main-diagonal is rotated clockwise to the first rank - thus 45 degrees.

On using xor, see bits from two sources by a mask. See rotate for the intrinsic routines.

/**
 * Pseudo rotate a bitboard 45 degree clockwise.
 * Main Diagonal is mapped to 1st rank
 * @param x any bitboard
 * @return bitboard x rotated
 */
U64 pseudoRotate45clockwise (U64 x) {
   const U64 k1 = C64(0xAAAAAAAAAAAAAAAA);
   const U64 k2 = C64(0xCCCCCCCCCCCCCCCC);
   const U64 k4 = C64(0xF0F0F0F0F0F0F0F0);
   x ^= k1 & (x ^ rotateRight(x,  8));
   x ^= k2 & (x ^ rotateRight(x, 16));
   x ^= k4 & (x ^ rotateRight(x, 32));
   return x;
}

Another pseudo rotation scheme was introduced by Robert Hyatt's rotated bitboards approach. While the 45 degree rotation looks more natural at the first glance, the calculations of this mapping is more complicated.

normal chess board bitmap          45 clockwise               45 clockwise crafty

A8 B8 C8 D8 E8 F8 G8 H8                                       C7 D8|A6 B7 C8|A7 B8|A8|
A7 B7 C7 D7 E7 F7 G7 H7                  A8                   F8|A4 B5 C6 D7 E8|A5 B6
A6 B6 C6 D6 E6 F6 G6 H6                A7  B8                 E6 F7 G8|A3 B4 C5 D6 E7
A5 B5 C5 D5 E5 F5 G5 H5              A6  B7  C8               E5 F6 G7 H8|A2 B3 C4 D5
A4 B4 C4 D4 E4 F4 G4 H4            A5  B6  C7  D8             E4 F5 G6 H7|A1 B2 C3 D4
A3 B3 C3 D3 E3 F3 G3 H3          A4  B5  C6  D7  E8           D2 E3 F4 G5 H6|B1 C2 D3
A2 B2 C2 D2 E2 F2 G2 H2        A3  B4  C5  D6  E7  F8        |G3 H4|D1 E2 F3 G4 H5|C1
A1 B1 C1 D1 E1 F1 G1 H1      A2  B3  C4  D5  E6  F7  G8       H1|G1 H2|F1 G2 H3|E1 F2
                           A1  B2  C3  D4  E5  F6  G7  H8
A8|B1 C2 D3 E4 F5 G6 H7      B1  C2  D3  E4  F5  G6  H7       A8|B1 C2 D3 E4 F5 G6 H7
A7 B8|C1 D2 E3 F4 G5 H6        C1  D2  E3  F4  G5  H6         A7 B8|C1 D2 E3 F4 G5 H6
A6 B7 C8|D1 E2 F3 G4 H5          D1  E2  F3  G4  H5           A6 B7 C8|D1 E2 F3 G4 H5
A5 B6 C7 D8|E1 F2 G3 H4            E1  F2  G3  H4             A5 B6 C7 D8|E1 F2 G3 H4
A4 B5 C6 D7 E8|F1 G2 H3              F1  G2  H3               A4 B5 C6 D7 E8|F1 G2 H3
A3 B4 C5 D6 E7 F8|G1 H2                G1  H2                 A3 B4 C5 D6 E7 F8|G1 H2
A2 B3 C4 D5 E6 F7 G8|H1                  H1                   A2 B3 C4 D5 E6 F7 G8|H1
A1 B2 C3 D4 E5 F6 G7 H8                                       A1 B2 C3 D4 E5 F6 G7 H8

45 clockwise                                                  45 clockwise

A parallel prefix solution to map the normal occupancy to the visual rotated approach is left to the ambitious reader.


Anti-Clockwise

We enumerate the 15 anti-diagonals by 7 ^ (file + rank), a nibble wise two's complement F == -1.

0 F E D C B A 9     1 1 1 1 1 1 1 9
1 0 F E D C B A     2 2 2 2 2 2 A A
2 1 0 F E D C B     3 3 3 3 3 B B B
3 2 1 0 F E D C     4 4 4 4 C C C C
4 3 2 1 0 F E D     5 5 5 D D D D D
5 4 3 2 1 0 F E     6 6 E E E E E E
6 5 4 3 2 1 0 F     7 F F F F F F F
7 6 5 4 3 2 1 0     0 0 0 0 0 0 0 0

We need to rotate the A-H files vertically by 7 to 0 ranks - done parallel prefix wise. One square is therefor mapped by:

sq' = (sq + 8*((sq&7)^7)) & 63;

The main anti-diagonal is rotated anti-clockwise to the first rank - thus 45 degrees. The shorter anti-diagonals are pairwise and properly file aligned packed into further ranks.

On using xor see bits from two sources by a mask. See rotate for the intrinsic routines.

/**
 * Pseudo rotate a bitboard 45 degree anti clockwise.
 * Main AntiDiagonal is mapped to 1st rank
 * @param x any bitboard
 * @return bitboard x rotated
 */
U64 pseudoRotate45antiClockwise (U64 x) {
   const U64 k1 = C64(0x5555555555555555);
   const U64 k2 = C64(0x3333333333333333);
   const U64 k4 = C64(0x0f0f0f0f0f0f0f0f);
   x ^= k1 & (x ^ rotateRight(x,  8));
   x ^= k2 & (x ^ rotateRight(x, 16));
   x ^= k4 & (x ^ rotateRight(x, 32));
   return x;
}

Rank, File and Diagonal

Those subsets may be flipped or mirrored in a more efficient way by multiplication-techniques with disjoint intermediate sums and no internal overflows. Unlike the whole board techniques, multiplication doesn't swap bits, but maps file to a rank or vice versa in different steps, which can not be combined in one step. Main application is to map file- or diagonal occupancies to ranks, to dense the line-occupancy to consecutive bits, further elaborated in Occupancy of any Line or Kindergarten Bitboards.

Flip about the Anti-Diagonal

Flipping about the anti-diagonal multiplies with the main-diagonal. Note that the set bits in the main-diagonal have a distance of 9 (2^0, 2^9,2^18,...,2^54, 2^63). We can therefor safely multiply it with a rank-pattern with 8 consecutive neighboring bits without overflows.

File to a Rank

Multiplying the masked A-file with the main-diagonal, maps the file-bits to the 8th rank, similar to a flip about the anti-diagonal A8-H1. Shifting down to the 1st rank, leaves the bits like a 90-degree anti clockwise rotation.

masked bits                             mapped to 8th rank
bits on A-file   *  main-diagonal    =  with garbage     -> 1st rank
A . . . . . . .     . . . . . . . 1     A B C D E F G H     . . . . . . . .
B . . . . . . .     . . . . . . 1 .     B C D E F G H .     . . . . . . . .
C . . . . . . .     . . . . . 1 . .     C D E F G H . .     . . . . . . . .
D . . . . . . .     . . . . 1 . . .     D E F G H . . .  >> . . . . . . . .
E . . . . . . .  *  . . . 1 . . . .  =  E F G H . . . .  56 . . . . . . . .
F . . . . . . .     . . 1 . . . . .     F G H . . . . .     . . . . . . . .
G . . . . . . .     . 1 . . . . . .     G H . . . . . .     . . . . . . . .
H . . . . . . .     1 . . . . . . .     H . . . . . . .     A B C D E F G H

Rank to File

Multiplying the masked 1st rank with the main-diagonal, maps the rank-bits to the H-file, similar to a flip about the anti-diagonal A8-H1. Shifting the H-file to the A-file plus mask acts like a 90-degree clockwise rotation.

masked bits                             mapped to H-file
bits on 1st rank *  main-diagonal    =  with garbage     -> masked A-file
. . . . . . . .     . . . . . . . 1     C D E F G H . A     A . . . . . . .
. . . . . . . .     . . . . . . 1 .     D E F G H . A B     B . . . . . . .
. . . . . . . .     . . . . . 1 . .     E F G H . A B C  >> C . . . . . . .
. . . . . . . .     . . . . 1 . . .     F G H . A B C D  7  D . . . . . . .
. . . . . . . .  *  . . . 1 . . . .  =  G H . A B C D E  &  E . . . . . . .
. . . . . . . .     . . 1 . . . . .     H . A B C D E F  A  F . . . . . . .
. . . . . . . .     . 1 . . . . . .     . A B C D E F G     G . . . . . . .
A B C D E F G H     1 . . . . . . .     A B C D E F G H     H . . . . . . .

Flip about the Diagonal

Flipping about the Diagonal is a bit more tricky. Since the Anti-Diagonal pattern as factor has the set bits with distance of 7 only (2^0,2^7, 2^14,...2^49, 2^56) with possible overflows, if multiplied with rank pattern of eight neighboring bits. Thus it can only be used to flip the H-file about the diagonal.

File to a Rank

Multiplying the masked H-file with the 7-bit right shifted (board left shifted) anti-diagonal, maps the file-bits to the 8th rank, similar to a flip about the diagonal A1-H8. Shifting it down to the 1st rank, leaves the bits like flip about the diagonal. Shifting down to the 1st rank, leaves the bits like a 90-degree clockwise rotation.

masked bits         Shifted             mapped to 8th rank
bits on H-file   *  anti-diagonal    =  with garbage     -> 1st rank
. . . . . . . A     . . . . . . . .     H G F E D C B A     . . . . . . . .
. . . . . . . B     . 1 . . . . . .     . H G F E D C B     . . . . . . . .
. . . . . . . C     . . 1 . . . . .     . . H G F E D C     . . . . . . . .
. . . . . . . D     . . . 1 . . . .     . . . H G F E D  >> . . . . . . . .
. . . . . . . E  *  . . . . 1 . . .  =  . . . . H G F E  56 . . . . . . . .
. . . . . . . F     . . . . . 1 . .     . . . . . H G F     . . . . . . . .
. . . . . . . G     . . . . . . 1 .     . . . . . . H G     . . . . . . . .
/ . . . . . . H     1 . . . . . . 1     . . . . . . . H     H G F E D C B A

Diagonals to Ranks

That is straight forward multiplication of a masked diagonal or anti-diagonal with the A-file. To mask the garbage off, we further shift down by 7 ranks.

masked diagonal  *  A-file              mapped
                                        to 8th rank      ->  1st rank
. . . . . . . H     1 . . . . . . .     A B C D E F G H     . . . . . . . .
. . . . . . G .     1 . . . . . . .     A B C D E F G .     . . . . . . . .
. . . . . F . .     1 . . . . . . .     A B C D E F . .  >> . . . . . . . .
. . . . E . . .     1 . . . . . . .     A B C D E . . .  56 . . . . . . . .
. . . D . . . .  *  1 . . . . . . .  =  A B C D . . . .     . . . . . . . .
. . C . . . . .     1 . . . . . . .     A B C . . . . .     . . . . . . . .
. B . . . . . .     1 . . . . . . .     A B . . . . . .     . . . . . . . .
A . . . . . . .     1 . . . . . . .     A . . . . . . .     A B C D E F G H

Mirror Horizontally

This is about bit-reversal of a byte.

rank1mirrored = (((rank1 * 0x80200802) & 0x0884422110) * 0x0101010101010101) >> 56;

This is how it works on a chessboard:

rank1            *  0x80200802          flipped
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     B C D E F G H .
. . . . . . . .  *  . . . . . . . 1  =  D E F G H . . A
. . . . . . . .     . . . . . 1 . .     F G H . . A B C
. . . . . . . .     . . . 1 . . . .     H . . A B C D E
A B C D E F G H     . 1 . . . . . .     . A B C D E F G

flipped          &  0x0884422110        reversedOnFiles
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
B C D E F G H .     . . . 1 . . . .     . . . E . . . .
D E F G H . . A  &  . . 1 . . . . 1  =  . . F . . . . A
F G H . . A B C     . 1 . . . . 1 .     . G . . . . B .
H . . A B C D E     1 . . . . 1 . .     H . . . . C . .
. A B C D E F G     . . . . 1 . . .     . . . . D . . .

reversedOnFiles  *  A-file              reversedOn8         reversed
. . . . . . . .     1 . . . . . . .     H G F E D C B A     . . . . . . . .
. . . . . . . .     1 . . . . . . .     H G F E D C B A     . . . . . . . .
. . . . . . . .     1 . . . . . . .     H G F E D C B A     . . . . . . . .
. . . E . . . .     1 . . . . . . .     H G F E D C B A  >> . . . . . . . .
. . F . . . . A  *  1 . . . . . . .  =  H G F . D C B A  56 . . . . . . . .
. G . . . . B .     1 . . . . . . .     H G . . D C B .     . . . . . . . .
H . . . . C . .     1 . . . . . . .     H . . . D C . .     . . . . . . . .
. . . . D . . .     1 . . . . . . .     . . . . D . . .     H G F E D C B A

A 32 bit solution:

rank1mirrored = ( (rank1 * 0x0802 & 0x22110)
                 |(rank1 * 0x8020 & 0x88440) )
                * 0x10101000 >> 24;

Or a simple lookup:

rank1mirrored = reverseByteLookup256[rank1];

See also

Publications

Forum Posts

External Links

Flipping

Mirroring

Rotation

Reflection

Smoke 'n' Mirrors

References

Up one Level