BitBoard Tests Magic v Non-Rotated 32 Bits v 64 Bits

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Harald
Posts: 265
Joined: Thu Mar 09, 2006 12:07 am

Re: BitBoard Tests (Rotated Lines)

Post by Harald » Sat Aug 25, 2007 6:54 am

bb_rotated_lines.cpp:

Code: Select all

/*******************************************************************/
/*
The rotated bitboard attacks with special line mapping 
as part of the board structure.

(c) 2006 Harald Lüßen
*/
/*******************************************************************/


#include "bb_ifdef.h"
#include "bb_basics.h"
#include "bb_bitboard.h"
#include "bb_board.h"
#include "bb_main.h"


#if USE_ROTATED_BITBOARDS_LINES()

/*******************************************************************/

/*
    directions and shifts
    +-----+-----+-----+
    |<<= 9|<<= 8|<<= 7|
    +-----+-----+-----+
    |<<= 1|     |>>= 1|
    +-----+-----+-----+
    |>>= 7|>>= 8|>>= 9|
    +-----+-----+-----+

    We use this mapping of the normal board squares to bitboard bits
    +-------------------------+
    | 63 62 61 60 59 58 57 56 | 8
    | 55 54 53 52 51 50 49 48 | 7
    | 47 46 45 44 43 42 41 40 | 6
    | 39 38 37 36 35 35 33 32 | 5
    | 31 30 29 28 27 26 25 24 | 4
    | 23 22 21 20 19 18 17 16 | 3
    | 15 14 13 12 11 10  9  8 | 2
    |  7  6  5  4  3  2  1  0 | 1
    +-------------------------+
       a  b  c  d  e  f  g  h
*/

/*******************************************************************/

// pieces at begin of game in rotated bitboards
const Bitboard begin_all_rl90= C64&#40;0xc3c3c3c3c3c3c3c3&#41;;
const Bitboard begin_all_rl45= C64&#40;0x870f1e3c78f0e1c3&#41;;
const Bitboard begin_all_rr45= C64&#40;0xc3e1f0783c1e0f87&#41;;


/*******************************************************************/

// Bit numbers of the normal board in the rotated board
const byte normal_to_rl90&#91;64&#93; =
&#123;
     0,  8, 16, 24, 32, 40, 48, 56,
     1,  9, 17, 25, 33, 41, 49, 57,
     2, 10, 18, 26, 34, 42, 50, 58,
     3, 11, 19, 27, 35, 43, 51, 59,
     4, 12, 20, 28, 36, 44, 52, 60,
     5, 13, 21, 29, 37, 45, 53, 61,
     6, 14, 22, 30, 38, 46, 54, 62,
     7, 15, 23, 31, 39, 47, 55, 63,
&#125;;

// Bit numbers of the normal board in the rotated board
// The squares are in the same line as in the normal board.
const byte normal_to_rl45&#91;64&#93; =
&#123;
     0, 57, 50, 43, 36, 29, 22, 15,
     8,  1, 58, 51, 44, 37, 30, 23,
    16,  9,  2, 59, 52, 45, 38, 31,
    24, 17, 10,  3, 60, 53, 46, 39,
    32, 25, 18, 11,  4, 61, 54, 47,
    40, 33, 26, 19, 12,  5, 62, 55,
    48, 41, 34, 27, 20, 13,  6, 63,
    56, 49, 42, 35, 28, 21, 14,  7,
&#125;;

// Bit numbers of the normal board in the rotated board
// The squares are in the same line as in the normal board.
const byte normal_to_rr45&#91;64&#93; =
&#123;
     0,  9, 18, 27, 36, 45, 54, 63,
     8, 17, 26, 35, 44, 53, 62,  7,
    16, 25, 34, 43, 52, 61,  6, 15,
    24, 33, 42, 51, 60,  5, 14, 23,
    32, 41, 50, 59,  4, 13, 22, 31,
    40, 49, 58,  3, 12, 21, 30, 39,
    48, 57,  2, 11, 20, 29, 38, 47,
    56,  1, 10, 19, 28, 37, 46, 55,
&#125;;

// Shift values of the rotated bitboard for attacks and move generation.
// Shift the rotated bitboard this number of bits to find the row in the low bits.
// The index is the square number on the normal board.
const byte shift_of_rl90&#91;64&#93; =
&#123;
     0,  8, 16, 24, 32, 40, 48, 56,
     0,  8, 16, 24, 32, 40, 48, 56,
     0,  8, 16, 24, 32, 40, 48, 56,
     0,  8, 16, 24, 32, 40, 48, 56,
     0,  8, 16, 24, 32, 40, 48, 56,
     0,  8, 16, 24, 32, 40, 48, 56,
     0,  8, 16, 24, 32, 40, 48, 56,
     0,  8, 16, 24, 32, 40, 48, 56,
&#125;;

// Shift values of the rotated bitboard for attacks and move generation.
// Shift the rotated bitboard this number of bits to find the row in the low bits.
// The index is the square number on the normal board.
const byte shift_of_rl45&#91;64&#93; =
&#123;
     0, 56, 48, 40, 32, 24, 16,  8,
     8,  0, 56, 48, 40, 32, 24, 16,
    16,  8,  0, 56, 48, 40, 32, 24,
    24, 16,  8,  0, 56, 48, 40, 32,
    32, 24, 16,  8,  0, 56, 48, 40,
    40, 32, 24, 16,  8,  0, 56, 48,
    48, 40, 32, 24, 16,  8,  0, 56,
    56, 48, 40, 32, 24, 16,  8,  0,
&#125;;

// Shift values of the rotated bitboard for attacks and move generation.
// Shift the rotated bitboard this number of bits to find the row in the low bits.
// The index is the square number on the normal board.
const byte shift_of_rr45&#91;64&#93; =
&#123;
     0,  8, 16, 24, 32, 40, 48, 56,
     8, 16, 24, 32, 40, 48, 56,  0,
    16, 24, 32, 40, 48, 56,  0,  8,
    24, 32, 40, 48, 56,  0,  8, 16,
    32, 40, 48, 56,  0,  8, 16, 24,
    40, 48, 56,  0,  8, 16, 24, 32,
    48, 56,  0,  8, 16, 24, 32, 40,
    56,  0,  8, 16, 24, 32, 40, 48,
&#125;;

// Mask values of the rotated bitboard for attacks and move generation.
// Mask the low bits of a shifted diagonal/row/line with bits in the correct length.
// The index is the square number on the normal board.
const byte mask_of_rl45&#91;64&#93; =
&#123;
    0xff, 0xfe, 0xfc, 0xf8, 0xf0, 0xe0, 0xc0, 0x80, 
    0x7f, 0xff, 0xfe, 0xfc, 0xf8, 0xf0, 0xe0, 0xc0, 
    0x3f, 0x7f, 0xff, 0xfe, 0xfc, 0xf8, 0xf0, 0xe0, 
    0x1f, 0x3f, 0x7f, 0xff, 0xfe, 0xfc, 0xf8, 0xf0, 
    0x0f, 0x1f, 0x3f, 0x7f, 0xff, 0xfe, 0xfc, 0xf8, 
    0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff, 0xfe, 0xfc, 
    0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff, 0xfe, 
    0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff, 
&#125;;

// Mask values of the rotated bitboard for attacks and move generation.
// Mask the low bits of a shifted diagonal/row/line with bits in the correct length.
// The index is the square number on the normal board.
const byte mask_of_rr45&#91;64&#93; =
&#123;
    0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff, 
    0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff, 0xfe, 
    0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff, 0xfe, 0xfc, 
    0x0f, 0x1f, 0x3f, 0x7f, 0xff, 0xfe, 0xfc, 0xf8, 
    0x1f, 0x3f, 0x7f, 0xff, 0xfe, 0xfc, 0xf8, 0xf0, 
    0x3f, 0x7f, 0xff, 0xfe, 0xfc, 0xf8, 0xf0, 0xe0, 
    0x7f, 0xff, 0xfe, 0xfc, 0xf8, 0xf0, 0xe0, 0xc0, 
    0xff, 0xfe, 0xfc, 0xf8, 0xf0, 0xe0, 0xc0, 0x80, 
&#125;;


/*******************************************************************/

/**
Put the scattered bits of an sliding attack pattern 
back to the original bitboard.
*/
Bitboard slider_rl90_to_bitboard&#91;256&#93;;

/**
Put the scattered bits of an sliding attack pattern 
back to the original bitboard.
*/
Bitboard slider_rl45_to_bitboard&#91;8&#93;&#91;256&#93;;

/**
Put the scattered bits of an sliding attack pattern 
back to the original bitboard.
*/
Bitboard slider_rr45_to_bitboard&#91;8&#93;&#91;256&#93;;


/*******************************************************************/

/**
Set the rotated bitboards of all pieces
*/
void Board&#58;&#58;set_all_rotated_bitboards&#40;)
&#123;
    Bitboard pieces = wpieces_ | bpieces_;
    all_rl90_ = 0;
    all_rl45_ = 0;
    all_rr45_ = 0;
    int sq;
    for ( sq = 0; sq < 64; ++sq )
    &#123;
        if ( pieces.test_bit&#40; sq ) )
        &#123;
            all_rl90_.set_bit&#40; normal_to_rl90&#91;sq&#93; );
            all_rl45_.set_bit&#40; normal_to_rl45&#91;sq&#93; );
            all_rr45_.set_bit&#40; normal_to_rr45&#91;sq&#93; );
        &#125;
    &#125;
&#125;


/*******************************************************************/

/**
Prepare the slider attacks back transformation table.
Put the scattered bits of an sliding attack pattern 
back to the original bitboard.
*/
void Board&#58;&#58;init_slider_attacks_index&#40;)
&#123;
    // Bitboard slider_rl90_to_bitboard&#91;256&#93;;
    int slider;
    Bitboard result = 0;
    for ( slider = 0; slider < 128; ++slider )
    &#123;
        result = slider;
        result *= C64&#40;0x0002040810204081&#41;; // projection northeast
        result &= C64&#40;0x0101010101010101&#41;; // line_h;
        slider_rl90_to_bitboard&#91;slider&#93; = result;
        slider_rl90_to_bitboard&#91;slider + 128&#93; = result + &#40;C64&#40;1&#41; << 56&#41;;
        //logf << "slider_rl90_to_bitboard " << slider << endl;
        //logf << slider_rl90_to_bitboard&#91;slider&#93;.txt8lines&#40;) << endl;
        //logf << "slider_rl90_to_bitboard " << slider + 128<< endl;
        //logf << slider_rl90_to_bitboard&#91;slider + 128&#93;.txt8lines&#40;) << endl;
    &#125;
    for ( slider = 0; slider < 256; ++slider )
    &#123;
        // Bitboard slider_rl45_to_bitboard&#91;8&#93;&#91;256&#93;;
        result = slider;
        result *= C64&#40;0x0101010101010101&#41;; // projection north
        result &= C64&#40;0x8040201008040201&#41;; // diagonal A8..H1
        for ( int index = 0; index < 8; ++index )
        &#123;
            slider_rl45_to_bitboard&#91;index&#93;&#91;slider&#93; = &#40;result << &#40;8 *      index ))
                                                   | &#40;result >> &#40;8 * &#40;8 - index&#41;));
            //logf << "slider_rl45_to_bitboard " << index << " " << slider << endl;
            //logf << slider_rl45_to_bitboard&#91;index&#93;&#91;slider&#93;.txt8lines&#40;) << endl;
        &#125;
        // Bitboard slider_rr45_to_bitboard&#91;8&#93;&#91;256&#93;;
        result = slider;
        result *= C64&#40;0x0101010101010101&#41;; // projection north
        result &= C64&#40;0x0102040810204080&#41;; // diagonal A1..H8
        for ( int index = 0; index < 8; ++index )
        &#123;
            slider_rr45_to_bitboard&#91;index&#93;&#91;slider&#93; = &#40;result << &#40;8 * &#40;1 + index&#41;))
                                                   | &#40;result >> &#40;8 * &#40;7 - index&#41;));
            //logf << "slider_rr45_to_bitboard " << index << " " << slider << endl;
            //logf << slider_rr45_to_bitboard&#91;index&#93;&#91;slider&#93;.txt8lines&#40;) << endl;
        &#125;
    &#125;
&#125;


/*******************************************************************/

/**
Get a bitboard with all positions set to 1 which can be attacked 
from a bishop, rook or queen on the square moving in the direction.
*/
Bitboard Board&#58;&#58;direction_attacks&#40; byte square, byte dir ) const
&#123;
    Bitboard result;
    Bitboard occ;
    byte shift;
    byte pos;
    byte pattern;
    byte att;

    // 4 3 2
    // 5 0 1
    // 6 7 8
    switch ( dir )
    &#123;
      case 1&#58;
        // normal bitboard
        occ = wpieces_ | bpieces_;
        shift = square & 0x38;
        occ >>= &#40;shift + 1&#41;;
        pattern = occ;
        pos = square & 7;
        att = slider_attacks&#91;pattern & 0x3f&#93;&#91;pos&#93;;
        att &= &#40;1 << pos&#41; - 1;
        result = att;
        result <<= shift;
        break;
      case 5&#58;
        // normal bitboard
        occ = wpieces_ | bpieces_;
        shift = square & 0x38;
        occ >>= &#40;shift + 1&#41;;
        pattern = occ;
        pos = square & 7;
        att = slider_attacks&#91;pattern & 0x3f&#93;&#91;pos&#93;;
        att &= ~(&#40;1 << pos&#41; - 1&#41;;
        result = att;
        result <<= shift;
        break;
      case 7&#58;
        // rotated rl90 bitboard
        occ = all_rl90_;
        shift = shift_of_rl90&#91;square&#93;;
        occ >>= &#40;shift + 1&#41;;
        pattern = occ;
        pos = square >> 3;
        att = slider_attacks&#91;pattern & 0x3f&#93;&#91;pos&#93;;
        att &= &#40;1 << pos&#41; - 1;
        result = slider_rl90_to_bitboard&#91;att&#93;;
        result <<= &#40;square & 7&#41;;
        break;
      case 3&#58;
        // rotated rl90 bitboard
        occ = all_rl90_;
        shift = shift_of_rl90&#91;square&#93;;
        occ >>= &#40;shift + 1&#41;;
        pattern = occ;
        pos = square >> 3;
        att = slider_attacks&#91;pattern & 0x3f&#93;&#91;pos&#93;;
        att &= ~(&#40;1 << pos&#41; - 1&#41;;
        result = slider_rl90_to_bitboard&#91;att&#93;;
        result <<= &#40;square & 7&#41;;
        break;
      case 8&#58;
        // rotated rl45 bitboard
        occ = all_rl45_;
        shift = shift_of_rl45&#91;square&#93;;
        occ >>= &#40;shift + 1&#41;;
        pattern = occ;
        pos = square & 7;
        att = slider_attacks&#91;pattern & 0x3f&#93;&#91;pos&#93;;
        att &= mask_of_rl45&#91;square&#93;;
        att &= &#40;1 << pos&#41; - 1;
        result = slider_rl45_to_bitboard&#91;normal_to_rl45&#91;square&#93; >> 3&#93;&#91;att&#93;;
        break;
      case 4&#58;
        // rotated rl45 bitboard
        occ = all_rl45_;
        shift = shift_of_rl45&#91;square&#93;;
        occ >>= &#40;shift + 1&#41;;
        pattern = occ;
        pos = square & 7;
        att = slider_attacks&#91;pattern & 0x3f&#93;&#91;pos&#93;;
        att &= mask_of_rl45&#91;square&#93;;
        att &= ~(&#40;1 << pos&#41; - 1&#41;;
        result = slider_rl45_to_bitboard&#91;normal_to_rl45&#91;square&#93; >> 3&#93;&#91;att&#93;;
        break;
      case 2&#58;
        // rotated rr45 bitboard
        occ = all_rr45_;
        shift = shift_of_rr45&#91;square&#93;;
        occ >>= &#40;shift + 1&#41;;
        pattern = occ;
        pos = square & 7;
        att = slider_attacks&#91;pattern & 0x3f&#93;&#91;pos&#93;;
        att &= mask_of_rr45&#91;square&#93;;
        att &= &#40;1 << pos&#41; - 1;
        result = slider_rr45_to_bitboard&#91;normal_to_rr45&#91;square&#93; >> 3&#93;&#91;att&#93;;
        break;
      case 6&#58;
        // rotated rr45 bitboard
        occ = all_rr45_;
        shift = shift_of_rr45&#91;square&#93;;
        occ >>= &#40;shift + 1&#41;;
        pattern = occ;
        pos = square & 7;
        att = slider_attacks&#91;pattern & 0x3f&#93;&#91;pos&#93;;
        att &= mask_of_rr45&#91;square&#93;;
        att &= ~(&#40;1 << pos&#41; - 1&#41;;
        result = slider_rr45_to_bitboard&#91;normal_to_rr45&#91;square&#93; >> 3&#93;&#91;att&#93;;
        break;
      default&#58;
        result = 0;
        break;
    &#125;

    return result;
&#125;


/*******************************************************************/

/**
Get a bitboard with all positions set to 1 which can be attacked 
from a rook or queen on the square.
*/
Bitboard Board&#58;&#58;orthogonal_attacks&#40; byte square ) const
&#123;
    Bitboard result;

    // normal bitboard
    Bitboard occ = wpieces_ | bpieces_;
    byte shift = square & 0x38;
    occ >>= &#40;shift + 1&#41;;
    byte pattern = occ;
    byte att = slider_attacks&#91;pattern & 0x3f&#93;&#91;square & 7&#93;;
    result = att;
    result <<= shift;

    // rotated rl90 bitboard
    occ = all_rl90_;
    shift = shift_of_rl90&#91;square&#93;;
    occ >>= &#40;shift + 1&#41;;
    pattern = occ;
    att = slider_attacks&#91;pattern & 0x3f&#93;&#91;square >> 3&#93;;
    occ = slider_rl90_to_bitboard&#91;att&#93;;
    occ <<= square & 7;
    result |= occ;

    return result;
&#125;


/*******************************************************************/

/**
Get a bitboard with all positions set to 1 which can be attacked 
from a bishop or queen on the square.
*/
Bitboard Board&#58;&#58;diagonal_attacks&#40; byte square ) const
&#123;
    Bitboard result;

    // rotated rl45 bitboard
    Bitboard occ = all_rl45_;
    byte shift = shift_of_rl45&#91;square&#93;;
    occ >>= &#40;shift + 1&#41;;
    byte pattern = occ;
    byte att = slider_attacks&#91;pattern & 0x3f&#93;&#91;square & 7&#93;;
    att &= mask_of_rl45&#91;square&#93;;
    result = slider_rl45_to_bitboard&#91;normal_to_rl45&#91;square&#93; >> 3&#93;&#91;att&#93;;

    // rotated rr45 bitboard
    occ = all_rr45_;
    shift = shift_of_rr45&#91;square&#93;;
    occ >>= &#40;shift + 1&#41;;
    pattern = occ;
    att = slider_attacks&#91;pattern & 0x3f&#93;&#91;square & 7&#93;;
    att &= mask_of_rr45&#91;square&#93;;
    occ = slider_rr45_to_bitboard&#91;normal_to_rr45&#91;square&#93; >> 3&#93;&#91;att&#93;;
    result |= occ;

    return result;
&#125;


/*******************************************************************/

#endif // USE_ROTATED_BITBOARDS_LINES&#40;)

Harald
Posts: 265
Joined: Thu Mar 09, 2006 12:07 am

Re: BitBoard Tests (Rotated Switch)

Post by Harald » Sat Aug 25, 2007 6:55 am

bb_rotated_switch.cpp:

Code: Select all

/*******************************************************************/
/*
The rotated bitboard attacks with special line mapping and switches
as part of the board structure.

&#40;c&#41; 2006 Harald Lüßen
*/
/*******************************************************************/


#include "bb_ifdef.h"
#include "bb_basics.h"
#include "bb_bitboard.h"
#include "bb_board.h"
#include "bb_main.h"


#if USE_ROTATED_BITBOARDS_SWITCH&#40;)

/*******************************************************************/

/*
    directions and shifts
    +-----+-----+-----+
    |<<= 9|<<= 8|<<= 7|
    +-----+-----+-----+
    |<<= 1|     |>>= 1|
    +-----+-----+-----+
    |>>= 7|>>= 8|>>= 9|
    +-----+-----+-----+

    We use this mapping of the normal board squares to bitboard bits
    +-------------------------+
    | 63 62 61 60 59 58 57 56 | 8
    | 55 54 53 52 51 50 49 48 | 7
    | 47 46 45 44 43 42 41 40 | 6
    | 39 38 37 36 35 35 33 32 | 5
    | 31 30 29 28 27 26 25 24 | 4
    | 23 22 21 20 19 18 17 16 | 3
    | 15 14 13 12 11 10  9  8 | 2
    |  7  6  5  4  3  2  1  0 | 1
    +-------------------------+
       a  b  c  d  e  f  g  h
*/

/*******************************************************************/

// pieces at begin of game in rotated bitboards
const Bitboard begin_all_rl90= C64&#40;0xc3c3c3c3c3c3c3c3&#41;;
const Bitboard begin_all_rl45= C64&#40;0x870f1e3c78f0e1c3&#41;;
const Bitboard begin_all_rr45= C64&#40;0xc3e1f0783c1e0f87&#41;;


/*******************************************************************/

// Bit numbers of the normal board in the rotated board
const byte normal_to_rl90&#91;64&#93; =
&#123;
     0,  8, 16, 24, 32, 40, 48, 56,
     1,  9, 17, 25, 33, 41, 49, 57,
     2, 10, 18, 26, 34, 42, 50, 58,
     3, 11, 19, 27, 35, 43, 51, 59,
     4, 12, 20, 28, 36, 44, 52, 60,
     5, 13, 21, 29, 37, 45, 53, 61,
     6, 14, 22, 30, 38, 46, 54, 62,
     7, 15, 23, 31, 39, 47, 55, 63,
&#125;;

// Bit numbers of the normal board in the rotated board
// The squares are in the same line as in the normal board.
const byte normal_to_rl45&#91;64&#93; =
&#123;
     0, 57, 50, 43, 36, 29, 22, 15,
     8,  1, 58, 51, 44, 37, 30, 23,
    16,  9,  2, 59, 52, 45, 38, 31,
    24, 17, 10,  3, 60, 53, 46, 39,
    32, 25, 18, 11,  4, 61, 54, 47,
    40, 33, 26, 19, 12,  5, 62, 55,
    48, 41, 34, 27, 20, 13,  6, 63,
    56, 49, 42, 35, 28, 21, 14,  7,
&#125;;

// Bit numbers of the normal board in the rotated board
// The squares are in the same line as in the normal board.
const byte normal_to_rr45&#91;64&#93; =
&#123;
     0,  9, 18, 27, 36, 45, 54, 63,
     8, 17, 26, 35, 44, 53, 62,  7,
    16, 25, 34, 43, 52, 61,  6, 15,
    24, 33, 42, 51, 60,  5, 14, 23,
    32, 41, 50, 59,  4, 13, 22, 31,
    40, 49, 58,  3, 12, 21, 30, 39,
    48, 57,  2, 11, 20, 29, 38, 47,
    56,  1, 10, 19, 28, 37, 46, 55,
&#125;;

// Shift values of the rotated bitboard for attacks and move generation.
// Shift the rotated bitboard this number of bits to find the row in the low bits.
// The index is the square number on the normal board.
const byte shift_of_rl90&#91;64&#93; =
&#123;
     0,  8, 16, 24, 32, 40, 48, 56,
     0,  8, 16, 24, 32, 40, 48, 56,
     0,  8, 16, 24, 32, 40, 48, 56,
     0,  8, 16, 24, 32, 40, 48, 56,
     0,  8, 16, 24, 32, 40, 48, 56,
     0,  8, 16, 24, 32, 40, 48, 56,
     0,  8, 16, 24, 32, 40, 48, 56,
     0,  8, 16, 24, 32, 40, 48, 56,
&#125;;

// Shift values of the rotated bitboard for attacks and move generation.
// Shift the rotated bitboard this number of bits to find the row in the low bits.
// The index is the square number on the normal board.
const byte shift_of_rl45&#91;64&#93; =
&#123;
     0, 56, 48, 40, 32, 24, 16,  8,
     8,  0, 56, 48, 40, 32, 24, 16,
    16,  8,  0, 56, 48, 40, 32, 24,
    24, 16,  8,  0, 56, 48, 40, 32,
    32, 24, 16,  8,  0, 56, 48, 40,
    40, 32, 24, 16,  8,  0, 56, 48,
    48, 40, 32, 24, 16,  8,  0, 56,
    56, 48, 40, 32, 24, 16,  8,  0,
&#125;;

// Shift values of the rotated bitboard for attacks and move generation.
// Shift the rotated bitboard this number of bits to find the row in the low bits.
// The index is the square number on the normal board.
const byte shift_of_rr45&#91;64&#93; =
&#123;
     0,  8, 16, 24, 32, 40, 48, 56,
     8, 16, 24, 32, 40, 48, 56,  0,
    16, 24, 32, 40, 48, 56,  0,  8,
    24, 32, 40, 48, 56,  0,  8, 16,
    32, 40, 48, 56,  0,  8, 16, 24,
    40, 48, 56,  0,  8, 16, 24, 32,
    48, 56,  0,  8, 16, 24, 32, 40,
    56,  0,  8, 16, 24, 32, 40, 48,
&#125;;

#if 0 // Not needed
const byte index_of_rl90&#91;64&#93; =
&#123;
     0,  0,  0,  0,  0,  0,  0,  0,
     0,  0,  0,  0,  0,  0,  0,  0,
     0,  0,  0,  0,  0,  0,  0,  0,
     0,  0,  0,  0,  0,  0,  0,  0,
     0,  0,  0,  0,  0,  0,  0,  0,
     0,  0,  0,  0,  0,  0,  0,  0,
     0,  0,  0,  0,  0,  0,  0,  0,
     0,  0,  0,  0,  0,  0,  0,  0,
&#125;;
#endif

// Index values of the rotated bitboard for attacks and move generation.
// This is the number of the slider part of the bitboard for use in slider_rl45_to_bitboard.
// The index is the square number on the normal board.
const byte index_of_rl45&#91;64&#93; =
&#123;
    7,  8,  9, 10, 11, 12, 13, 14,
    6,  7,  8,  9, 10, 11, 12, 13,
    5,  6,  7,  8,  9, 10, 11, 12,
    4,  5,  6,  7,  8,  9, 10, 11,
    3,  4,  5,  6,  7,  8,  9, 10,
    2,  3,  4,  5,  6,  7,  8,  9,
    1,  2,  3,  4,  5,  6,  7,  8,
    0,  1,  2,  3,  4,  5,  6,  7,
&#125;;

// Index values of the rotated bitboard for attacks and move generation.
// This is the number of the slider part of the bitboard for use in slider_rr45_to_bitboard.
// The index is the square number on the normal board.
const byte index_of_rr45&#91;64&#93; =
&#123;
    0,  1,  2,  3,  4,  5,  6,  7,
    1,  2,  3,  4,  5,  6,  7,  8,
    2,  3,  4,  5,  6,  7,  8,  9,
    3,  4,  5,  6,  7,  8,  9, 10,
    4,  5,  6,  7,  8,  9, 10, 11,
    5,  6,  7,  8,  9, 10, 11, 12,
    6,  7,  8,  9, 10, 11, 12, 13,
    7,  8,  9, 10, 11, 12, 13, 14,
&#125;;


/*******************************************************************/

/**
Put the scattered bits of an sliding attack pattern 
back to the original bitboard.
*/
Bitboard slider_rl90_to_bitboard&#91;256&#93;;

Bitboard rl45_0_bitboard&#91;2&#93;;
Bitboard rl45_1_bitboard&#91;4&#93;;
Bitboard rl45_2_bitboard&#91;8&#93;;
Bitboard rl45_3_bitboard&#91;16&#93;;
Bitboard rl45_4_bitboard&#91;32&#93;;
Bitboard rl45_5_bitboard&#91;64&#93;;
Bitboard rl45_6_bitboard&#91;128&#93;;
Bitboard rl45_7_bitboard&#91;256&#93;;
Bitboard rl45_8_bitboard&#91;128&#93;;
Bitboard rl45_9_bitboard&#91;64&#93;;
Bitboard rl45_10_bitboard&#91;32&#93;;
Bitboard rl45_11_bitboard&#91;16&#93;;
Bitboard rl45_12_bitboard&#91;8&#93;;
Bitboard rl45_13_bitboard&#91;4&#93;;
Bitboard rl45_14_bitboard&#91;2&#93;;

Bitboard rr45_0_bitboard&#91;2&#93;;
Bitboard rr45_1_bitboard&#91;4&#93;;
Bitboard rr45_2_bitboard&#91;8&#93;;
Bitboard rr45_3_bitboard&#91;16&#93;;
Bitboard rr45_4_bitboard&#91;32&#93;;
Bitboard rr45_5_bitboard&#91;64&#93;;
Bitboard rr45_6_bitboard&#91;128&#93;;
Bitboard rr45_7_bitboard&#91;256&#93;;
Bitboard rr45_8_bitboard&#91;128&#93;;
Bitboard rr45_9_bitboard&#91;64&#93;;
Bitboard rr45_10_bitboard&#91;32&#93;;
Bitboard rr45_11_bitboard&#91;16&#93;;
Bitboard rr45_12_bitboard&#91;8&#93;;
Bitboard rr45_13_bitboard&#91;4&#93;;
Bitboard rr45_14_bitboard&#91;2&#93;;


/*******************************************************************/

/**
Set the rotated bitboards of all pieces
*/
void Board&#58;&#58;set_all_rotated_bitboards&#40;)
&#123;
    Bitboard pieces = wpieces_ | bpieces_;
    all_rl90_ = 0;
    all_rl45_ = 0;
    all_rr45_ = 0;
    int sq;
    for ( sq = 0; sq < 64; ++sq )
    &#123;
        if ( pieces.test_bit&#40; sq ) )
        &#123;
            all_rl90_.set_bit&#40; normal_to_rl90&#91;sq&#93; );
            all_rl45_.set_bit&#40; normal_to_rl45&#91;sq&#93; );
            all_rr45_.set_bit&#40; normal_to_rr45&#91;sq&#93; );
        &#125;
    &#125;
&#125;


/*******************************************************************/

/**
Prepare the slider attacks back transformation table.
Put the scattered bits of an sliding attack pattern 
back to the original bitboard.
*/
void Board&#58;&#58;init_slider_attacks_index&#40;)
&#123;
    int slider;
    // Bitboard slider_rl90_to_bitboard&#91;256&#93;;
    Bitboard result = 0;
    for ( slider = 0; slider < 128; ++slider )
    &#123;
        result = slider;
        result *= C64&#40;0x0002040810204081&#41;; // projection northeast
        result &= C64&#40;0x0101010101010101&#41;; // line_h;
        slider_rl90_to_bitboard&#91;slider&#93; = result;
        slider_rl90_to_bitboard&#91;slider + 128&#93; = result + &#40;C64&#40;1&#41; << 56&#41;;
        //logf << "slider_rl90_to_bitboard " << slider << endl;
        //logf << slider_rl90_to_bitboard&#91;slider&#93;.txt8lines&#40;) << endl;
        //logf << "slider_rl90_to_bitboard " << slider + 128<< endl;
        //logf << slider_rl90_to_bitboard&#91;slider + 128&#93;.txt8lines&#40;) << endl;
    &#125;

    for ( slider = 0; slider < 256; ++slider )
    &#123;
        // Bitboard slider_rl45_to_bitboard&#91;8&#93;&#91;256&#93;;
        result = slider;
        result *= C64&#40;0x0101010101010101&#41;; // projection north
        result &= C64&#40;0x8040201008040201&#41;; // diagonal A8..H1
        rl45_0_bitboard&#91;  slider & 0x01      &#93; = result << &#40;7 * 8&#41;;
        rl45_1_bitboard&#91;  slider & 0x03      &#93; = result << &#40;6 * 8&#41;;
        rl45_2_bitboard&#91;  slider & 0x07      &#93; = result << &#40;5 * 8&#41;;
        rl45_3_bitboard&#91;  slider & 0x0f      &#93; = result << &#40;4 * 8&#41;;
        rl45_4_bitboard&#91;  slider & 0x1f      &#93; = result << &#40;3 * 8&#41;;
        rl45_5_bitboard&#91;  slider & 0x3f      &#93; = result << &#40;2 * 8&#41;;
        rl45_6_bitboard&#91;  slider & 0x7f      &#93; = result << &#40;1 * 8&#41;;
        rl45_7_bitboard&#91;  slider & 0xff      &#93; = result;
        rl45_8_bitboard&#91; &#40;slider & 0xfe&#41; >> 1&#93; = result >> &#40;1 * 8&#41;;
        rl45_9_bitboard&#91; &#40;slider & 0xfc&#41; >> 2&#93; = result >> &#40;2 * 8&#41;;
        rl45_10_bitboard&#91;&#40;slider & 0xf8&#41; >> 3&#93; = result >> &#40;3 * 8&#41;;
        rl45_11_bitboard&#91;&#40;slider & 0xf0&#41; >> 4&#93; = result >> &#40;4 * 8&#41;;
        rl45_12_bitboard&#91;&#40;slider & 0xe0&#41; >> 5&#93; = result >> &#40;5 * 8&#41;;
        rl45_13_bitboard&#91;&#40;slider & 0xc0&#41; >> 6&#93; = result >> &#40;6 * 8&#41;;
        rl45_14_bitboard&#91;&#40;slider & 0x80&#41; >> 7&#93; = result >> &#40;7 * 8&#41;;

        // Bitboard slider_rr45_to_bitboard&#91;8&#93;&#91;256&#93;;
        result = slider;
        result *= C64&#40;0x0101010101010101&#41;; // projection north
        result &= C64&#40;0x0102040810204080&#41;; // diagonal A1..H8
        rr45_0_bitboard&#91;  slider & 0x01      &#93; = result >> &#40;7 * 8&#41;;
        rr45_1_bitboard&#91;  slider & 0x03      &#93; = result >> &#40;6 * 8&#41;;
        rr45_2_bitboard&#91;  slider & 0x07      &#93; = result >> &#40;5 * 8&#41;;
        rr45_3_bitboard&#91;  slider & 0x0f      &#93; = result >> &#40;4 * 8&#41;;
        rr45_4_bitboard&#91;  slider & 0x1f      &#93; = result >> &#40;3 * 8&#41;;
        rr45_5_bitboard&#91;  slider & 0x3f      &#93; = result >> &#40;2 * 8&#41;;
        rr45_6_bitboard&#91;  slider & 0x7f      &#93; = result >> &#40;1 * 8&#41;;
        rr45_7_bitboard&#91;  slider & 0xff      &#93; = result;
        rr45_8_bitboard&#91; &#40;slider & 0xfe&#41; >> 1&#93; = result << &#40;1 * 8&#41;;
        rr45_9_bitboard&#91; &#40;slider & 0xfc&#41; >> 2&#93; = result << &#40;2 * 8&#41;;
        rr45_10_bitboard&#91;&#40;slider & 0xf8&#41; >> 3&#93; = result << &#40;3 * 8&#41;;
        rr45_11_bitboard&#91;&#40;slider & 0xf0&#41; >> 4&#93; = result << &#40;4 * 8&#41;;
        rr45_12_bitboard&#91;&#40;slider & 0xe0&#41; >> 5&#93; = result << &#40;5 * 8&#41;;
        rr45_13_bitboard&#91;&#40;slider & 0xc0&#41; >> 6&#93; = result << &#40;6 * 8&#41;;
        rr45_14_bitboard&#91;&#40;slider & 0x80&#41; >> 7&#93; = result << &#40;7 * 8&#41;;
    &#125;
&#125;


/*******************************************************************/

/**
Get a bitboard with all positions set to 1 which can be attacked 
from a bishop, rook or queen on the square moving in the direction.
*/
Bitboard Board&#58;&#58;direction_attacks&#40; byte square, byte dir ) const
&#123;
    Bitboard result;
    Bitboard occ;
    byte shift;
    byte pos;
    byte pattern;
    byte att;

    // 4 3 2
    // 5 0 1
    // 6 7 8
    switch ( dir )
    &#123;
      case 1&#58;
        // normal bitboard
        occ = wpieces_ | bpieces_;
        shift = square & 0x38;
        occ >>= &#40;shift + 1&#41;;
        pattern = occ;
        pos = square & 7;
        att = slider_attacks&#91;pattern & 0x3f&#93;&#91;pos&#93;;
        att &= &#40;1 << pos&#41; - 1;
        result = att;
        result <<= shift;
        break;
      case 5&#58;
        // normal bitboard
        occ = wpieces_ | bpieces_;
        shift = square & 0x38;
        occ >>= &#40;shift + 1&#41;;
        pattern = occ;
        pos = square & 7;
        att = slider_attacks&#91;pattern & 0x3f&#93;&#91;pos&#93;;
        att &= ~(&#40;1 << pos&#41; - 1&#41;;
        result = att;
        result <<= shift;
        break;
      case 7&#58;
        // rotated rl90 bitboard
        occ = all_rl90_;
        shift = shift_of_rl90&#91;square&#93;;
        occ >>= &#40;shift + 1&#41;;
        pattern = occ;
        pos = square >> 3;
        att = slider_attacks&#91;pattern & 0x3f&#93;&#91;pos&#93;;
        att &= &#40;1 << pos&#41; - 1;
        result = slider_rl90_to_bitboard&#91;att&#93;;
        result <<= square & 7;
        break;
      case 3&#58;
        // rotated rl90 bitboard
        occ = all_rl90_;
        shift = shift_of_rl90&#91;square&#93;;
        occ >>= &#40;shift + 1&#41;;
        pattern = occ;
        pos = square >> 3;
        att = slider_attacks&#91;pattern & 0x3f&#93;&#91;pos&#93;;
        att &= ~(&#40;1 << pos&#41; - 1&#41;;
        result = slider_rl90_to_bitboard&#91;att&#93;;
        result <<= square & 7;
        break;
      case 8&#58;
        // rotated rl45 bitboard
        occ = all_rl45_;
        shift = shift_of_rl45&#91;square&#93;;
        occ >>= &#40;shift + 1&#41;;
        pattern = occ;
        pos = square & 7;
        att = slider_attacks&#91;pattern & 0x3f&#93;&#91;pos&#93;;
        att &= &#40;1 << pos&#41; - 1;
        switch&#40; index_of_rl45&#91;square&#93; )
        &#123;
          case 0&#58;
            result = rl45_0_bitboard&#91;att & 0x01&#93;;
            break;
          case 1&#58;
            result = rl45_1_bitboard&#91;att & 0x03&#93;;
            break;
          case 2&#58;
            result = rl45_2_bitboard&#91;att & 0x07&#93;;
            break;
          case 3&#58;
            result = rl45_3_bitboard&#91;att & 0x0f&#93;;
            break;
          case 4&#58;
            result = rl45_4_bitboard&#91;att & 0x1f&#93;;
            break;
          case 5&#58;
            result = rl45_5_bitboard&#91;att & 0x3f&#93;;
            break;
          case 6&#58;
            result = rl45_6_bitboard&#91;att & 0x7f&#93;;
            break;
          case 7&#58;
            result = rl45_7_bitboard&#91;att&#93;;
            break;
          case 8&#58;
            result = rl45_8_bitboard&#91;&#40;att >> 1&#41; & 0x7f&#93;;
            break;
          case 9&#58;
            result = rl45_9_bitboard&#91;&#40;att >> 2&#41; & 0x3f&#93;;
            break;
          case 10&#58;
            result = rl45_10_bitboard&#91;&#40;att >>3&#41; & 0x1f&#93;;
            break;
          case 11&#58;
            result = rl45_11_bitboard&#91;&#40;att >> 4&#41; & 0x0f&#93;;
            break;
          case 12&#58;
            result = rl45_12_bitboard&#91;&#40;att >> 5&#41; & 0x07&#93;;
            break;
          case 13&#58;
            result = rl45_13_bitboard&#91;&#40;att >> 6&#41; & 0x03&#93;;
            break;
          case 14&#58;
            result = rl45_14_bitboard&#91;&#40;att >> 7&#41; & 0x01&#93;;
            break;
        &#125;
        break;
      case 4&#58;
        // rotated rl45 bitboard
        occ = all_rl45_;
        shift = shift_of_rl45&#91;square&#93;;
        occ >>= &#40;shift + 1&#41;;
        pattern = occ;
        pos = square & 7;
        att = slider_attacks&#91;pattern & 0x3f&#93;&#91;pos&#93;;
        att &= ~(&#40;1 << pos&#41; - 1&#41;;
        switch&#40; index_of_rl45&#91;square&#93; )
        &#123;
          case 0&#58;
            result = rl45_0_bitboard&#91;att & 0x01&#93;;
            break;
          case 1&#58;
            result = rl45_1_bitboard&#91;att & 0x03&#93;;
            break;
          case 2&#58;
            result = rl45_2_bitboard&#91;att & 0x07&#93;;
            break;
          case 3&#58;
            result = rl45_3_bitboard&#91;att & 0x0f&#93;;
            break;
          case 4&#58;
            result = rl45_4_bitboard&#91;att & 0x1f&#93;;
            break;
          case 5&#58;
            result = rl45_5_bitboard&#91;att & 0x3f&#93;;
            break;
          case 6&#58;
            result = rl45_6_bitboard&#91;att & 0x7f&#93;;
            break;
          case 7&#58;
            result = rl45_7_bitboard&#91;att&#93;;
            break;
          case 8&#58;
            result = rl45_8_bitboard&#91;&#40;att >> 1&#41; & 0x7f&#93;;
            break;
          case 9&#58;
            result = rl45_9_bitboard&#91;&#40;att >> 2&#41; & 0x3f&#93;;
            break;
          case 10&#58;
            result = rl45_10_bitboard&#91;&#40;att >> 3&#41; & 0x1f&#93;;
            break;
          case 11&#58;
            result = rl45_11_bitboard&#91;&#40;att >> 4&#41; & 0x0f&#93;;
            break;
          case 12&#58;
            result = rl45_12_bitboard&#91;&#40;att >> 5&#41; & 0x07&#93;;
            break;
          case 13&#58;
            result = rl45_13_bitboard&#91;&#40;att >> 6&#41; & 0x03&#93;;
            break;
          case 14&#58;
            result = rl45_14_bitboard&#91;&#40;att >> 7&#41; & 0x01&#93;;
            break;
        &#125;
        break;
      case 2&#58;
        // rotated rr45 bitboard
        occ = all_rr45_;
        shift = shift_of_rr45&#91;square&#93;;
        occ >>= &#40;shift + 1&#41;;
        pattern = occ;
        pos = square & 7;
        att = slider_attacks&#91;pattern & 0x3f&#93;&#91;pos&#93;;
        att &= &#40;1 << pos&#41; - 1;
        switch&#40; index_of_rr45&#91;square&#93; )
        &#123;
          case 0&#58;
            result = rr45_0_bitboard&#91;att & 0x01&#93;;
            break;
          case 1&#58;
            result = rr45_1_bitboard&#91;att & 0x03&#93;;
            break;
          case 2&#58;
            result = rr45_2_bitboard&#91;att & 0x07&#93;;
            break;
          case 3&#58;
            result = rr45_3_bitboard&#91;att & 0x0f&#93;;
            break;
          case 4&#58;
            result = rr45_4_bitboard&#91;att & 0x1f&#93;;
            break;
          case 5&#58;
            result = rr45_5_bitboard&#91;att & 0x3f&#93;;
            break;
          case 6&#58;
            result = rr45_6_bitboard&#91;att & 0x7f&#93;;
            break;
          case 7&#58;
            result = rr45_7_bitboard&#91;att&#93;;
            break;
          case 8&#58;
            result = rr45_8_bitboard&#91;&#40;att >> 1&#41; & 0x7f&#93;;
            break;
          case 9&#58;
            result = rr45_9_bitboard&#91;&#40;att >> 2&#41; & 0x3f&#93;;
            break;
          case 10&#58;
            result = rr45_10_bitboard&#91;&#40;att >> 3&#41; & 0x1f&#93;;
            break;
          case 11&#58;
            result = rr45_11_bitboard&#91;&#40;att >> 4&#41; & 0x0f&#93;;
            break;
          case 12&#58;
            result = rr45_12_bitboard&#91;&#40;att >> 5&#41; & 0x07&#93;;
            break;
          case 13&#58;
            result = rr45_13_bitboard&#91;&#40;att >> 6&#41; & 0x03&#93;;
            break;
          case 14&#58;
            result = rr45_14_bitboard&#91;&#40;att >> 7&#41; & 0x01&#93;;
            break;
        &#125;
        break;
      case 6&#58;
        // rotated rr45 bitboard
        occ = all_rr45_;
        shift = shift_of_rr45&#91;square&#93;;
        occ >>= &#40;shift + 1&#41;;
        pattern = occ;
        pos = square & 7;
        att = slider_attacks&#91;pattern & 0x3f&#93;&#91;pos&#93;;
        att &= ~(&#40;1 << pos&#41; - 1&#41;;
        switch&#40; index_of_rr45&#91;square&#93; )
        &#123;
          case 0&#58;
            result = rr45_0_bitboard&#91;att & 0x01&#93;;
            break;
          case 1&#58;
            result = rr45_1_bitboard&#91;att & 0x03&#93;;
            break;
          case 2&#58;
            result = rr45_2_bitboard&#91;att & 0x07&#93;;
            break;
          case 3&#58;
            result = rr45_3_bitboard&#91;att & 0x0f&#93;;
            break;
          case 4&#58;
            result = rr45_4_bitboard&#91;att & 0x1f&#93;;
            break;
          case 5&#58;
            result = rr45_5_bitboard&#91;att & 0x3f&#93;;
            break;
          case 6&#58;
            result = rr45_6_bitboard&#91;att & 0x7f&#93;;
            break;
          case 7&#58;
            result = rr45_7_bitboard&#91;att&#93;;
            break;
          case 8&#58;
            result = rr45_8_bitboard&#91;&#40;att >> 1&#41; & 0x7f&#93;;
            break;
          case 9&#58;
            result = rr45_9_bitboard&#91;&#40;att >> 2&#41; & 0x3f&#93;;
            break;
          case 10&#58;
            result = rr45_10_bitboard&#91;&#40;att >> 3&#41; & 0x1f&#93;;
            break;
          case 11&#58;
            result = rr45_11_bitboard&#91;&#40;att >> 4&#41; & 0x0f&#93;;
            break;
          case 12&#58;
            result = rr45_12_bitboard&#91;&#40;att >> 5&#41; & 0x07&#93;;
            break;
          case 13&#58;
            result = rr45_13_bitboard&#91;&#40;att >> 6&#41; & 0x03&#93;;
            break;
          case 14&#58;
            result = rr45_14_bitboard&#91;&#40;att >> 7&#41; & 0x01&#93;;
            break;
        &#125;
        break;
      default&#58;
        result = 0;
        break;
    &#125;

    return result;
&#125;


/*******************************************************************/

/**
Get a bitboard with all positions set to 1 which can be attacked 
from a rook or queen on the square.
*/
Bitboard Board&#58;&#58;orthogonal_attacks&#40; byte square ) const
&#123;
    Bitboard result;

    // normal bitboard
    Bitboard occ = wpieces_ | bpieces_;
    byte shift = square & 0x38;
    occ >>= &#40;shift + 1&#41;;
    byte pattern = occ;
    byte att = slider_attacks&#91;pattern & 0x3f&#93;&#91;square & 7&#93;;
    result = att;
    result <<= shift;

    // rotated rl90 bitboard
    occ = all_rl90_;
    shift = shift_of_rl90&#91;square&#93;;
    occ >>= &#40;shift + 1&#41;;
    pattern = occ;
    att = slider_attacks&#91;pattern & 0x3f&#93;&#91;square >> 3&#93;;
    occ = slider_rl90_to_bitboard&#91;att&#93;;
    occ <<= square & 7;
    result |= occ;

    return result;
&#125;


/*******************************************************************/

/**
Get a bitboard with all positions set to 1 which can be attacked 
from a bishop or queen on the square.
*/
Bitboard Board&#58;&#58;diagonal_attacks&#40; byte square ) const
&#123;
    Bitboard result;

    // rotated rl45 bitboard
    Bitboard occ = all_rl45_;
    byte shift = shift_of_rl45&#91;square&#93;;
    occ >>= &#40;shift + 1&#41;;
    byte pattern = occ;
    byte att = slider_attacks&#91;pattern & 0x3f&#93;&#91;square & 7&#93;;
    switch&#40; index_of_rl45&#91;square&#93; )
    &#123;
      case 0&#58;
        result = rl45_0_bitboard&#91;att & 0x01&#93;;
        break;
      case 1&#58;
        result = rl45_1_bitboard&#91;att & 0x03&#93;;
        break;
      case 2&#58;
        result = rl45_2_bitboard&#91;att & 0x07&#93;;
        break;
      case 3&#58;
        result = rl45_3_bitboard&#91;att & 0x0f&#93;;
        break;
      case 4&#58;
        result = rl45_4_bitboard&#91;att & 0x1f&#93;;
        break;
      case 5&#58;
        result = rl45_5_bitboard&#91;att & 0x3f&#93;;
        break;
      case 6&#58;
        result = rl45_6_bitboard&#91;att & 0x7f&#93;;
        break;
      case 7&#58;
        result = rl45_7_bitboard&#91;att&#93;;
        break;
      case 8&#58;
        result = rl45_8_bitboard&#91;&#40;att >> 1&#41; & 0x7f&#93;;
        break;
      case 9&#58;
        result = rl45_9_bitboard&#91;&#40;att >> 2&#41; & 0x3f&#93;;
        break;
      case 10&#58;
        result = rl45_10_bitboard&#91;&#40;att >> 3&#41; & 0x1f&#93;;
        break;
      case 11&#58;
        result = rl45_11_bitboard&#91;&#40;att >> 4&#41; & 0x0f&#93;;
        break;
      case 12&#58;
        result = rl45_12_bitboard&#91;&#40;att >> 5&#41; & 0x07&#93;;
        break;
      case 13&#58;
        result = rl45_13_bitboard&#91;&#40;att >> 6&#41; & 0x03&#93;;
        break;
      case 14&#58;
        result = rl45_14_bitboard&#91;&#40;att >> 7&#41; & 0x01&#93;;
        break;
    &#125;

    // rotated rr45 bitboard
    occ = all_rr45_;
    shift = shift_of_rr45&#91;square&#93;;
    occ >>= &#40;shift + 1&#41;;
    pattern = occ;
    att = slider_attacks&#91;pattern & 0x3f&#93;&#91;square & 7&#93;;
    switch&#40; index_of_rr45&#91;square&#93; )
    &#123;
      case 0&#58;
        result |= rr45_0_bitboard&#91;att & 0x01&#93;;
        break;
      case 1&#58;
        result |= rr45_1_bitboard&#91;att & 0x03&#93;;
        break;
      case 2&#58;
        result |= rr45_2_bitboard&#91;att & 0x07&#93;;
        break;
      case 3&#58;
        result |= rr45_3_bitboard&#91;att & 0x0f&#93;;
        break;
      case 4&#58;
        result |= rr45_4_bitboard&#91;att & 0x1f&#93;;
        break;
      case 5&#58;
        result |= rr45_5_bitboard&#91;att & 0x3f&#93;;
        break;
      case 6&#58;
        result |= rr45_6_bitboard&#91;att & 0x7f&#93;;
        break;
      case 7&#58;
        result |= rr45_7_bitboard&#91;att&#93;;
        break;
      case 8&#58;
        result |= rr45_8_bitboard&#91;&#40;att >> 1&#41; & 0x7f&#93;;
        break;
      case 9&#58;
        result |= rr45_9_bitboard&#91;&#40;att >> 2&#41; & 0x3f&#93;;
        break;
      case 10&#58;
        result |= rr45_10_bitboard&#91;&#40;att >> 3&#41; & 0x1f&#93;;
        break;
      case 11&#58;
        result |= rr45_11_bitboard&#91;&#40;att >> 4&#41; & 0x0f&#93;;
        break;
      case 12&#58;
        result |= rr45_12_bitboard&#91;&#40;att >> 5&#41; & 0x07&#93;;
        break;
      case 13&#58;
        result |= rr45_13_bitboard&#91;&#40;att >> 6&#41; & 0x03&#93;;
        break;
      case 14&#58;
        result |= rr45_14_bitboard&#91;&#40;att >> 7&#41; & 0x01&#93;;
        break;
    &#125;

    return result;
&#125;


/*******************************************************************/

#endif // USE_ROTATED_BITBOARDS_SWITCH&#40;)

Harald
Posts: 265
Joined: Thu Mar 09, 2006 12:07 am

Re: BitBoard Tests (Rotated Indices)

Post by Harald » Sat Aug 25, 2007 6:56 am

bb_rotated_indices.cpp:

Code: Select all

/*******************************************************************/ 
/* Rotated Indices by Alessandro Damiani &#40;engine Fortress&#41;         */
/* This test has been written in 2006                              */
/* Implemented in Elephant by Harald Lüßen                         */
/*******************************************************************/ 

#include "bb_ifdef.h" 
#include "bb_basics.h" 
#include "bb_bitboard.h" 
#include "bb_board.h" 
#include "bb_move.h" 
#include "bb_main.h" 

#if USE_ROTATED_INDICES&#40;) 

/*******************************************************************/ 
// Global data required by Rotated Indices

Bitboard attackFromHorizontal&#91;64&#93;&#91;64&#93;;
Bitboard attackFromVertical&#91;64&#93;&#91;64&#93;;
Bitboard attackFromRightUp&#91;64&#93;&#91;64&#93;;
Bitboard attackFromRightDown&#91;64&#93;&#91;64&#93;;

Bitboard allPieces;


/*******************************************************************/ 
// Global data required by Board&#58;&#58;direction_attacks&#40;)

const Bitboard dirMaskRight&#91;8&#93; = 
&#123; 
    // 0, line_h, line_gh, line_fh, line_eh, line_dh, line_ch, line_bh, 
    0, C64&#40;0x0101010101010101&#41;, C64&#40;0x0303030303030303&#41;, C64&#40;0x0707070707070707&#41;, C64&#40;0x0f0f0f0f0f0f0f0f&#41;, 
    C64&#40;0x1f1f1f1f1f1f1f1f&#41;, C64&#40;0x3f3f3f3f3f3f3f3f&#41;, C64&#40;0x7f7f7f7f7f7f7f7f&#41; 
&#125;; 

const Bitboard dirMaskLeft&#91;8&#93; = 
&#123; 
    // line_ag, line_af, line_ae, line_ad, line_ac, line_ab, line_a, 0, 
    C64&#40;0xfefefefefefefefe&#41;, C64&#40;0xfcfcfcfcfcfcfcfc&#41;, C64&#40;0xf8f8f8f8f8f8f8f8&#41;, C64&#40;0xf0f0f0f0f0f0f0f0&#41;, 
    C64&#40;0xe0e0e0e0e0e0e0e0&#41;, C64&#40;0xc0c0c0c0c0c0c0c0&#41;, C64&#40;0x8080808080808080&#41;, 0 
&#125;; 

const Bitboard dirMaskUp&#91;8&#93; = 
&#123; 
    // row_28, row_38, row_48, row_58, row_68, row_78, row_8, 0, 
    C64&#40;0xffffffffffffff00&#41;, C64&#40;0xffffffffffff0000&#41;, C64&#40;0xffffffffff000000&#41;, C64&#40;0xffffffff00000000&#41;, 
    C64&#40;0xffffff0000000000&#41;, C64&#40;0xffff000000000000&#41;, C64&#40;0xff00000000000000&#41;, 0 
&#125;; 

const Bitboard dirMaskDown&#91;8&#93; = 
&#123; 
    // 0, row_1, row_12, row_13, row_14, row_15, row_16, row_17, 
    0, C64&#40;0x00000000000000ff&#41;, C64&#40;0x000000000000ffff&#41;, C64&#40;0x0000000000ffffff&#41;, C64&#40;0x00000000ffffffff&#41;, 
    C64&#40;0x000000ffffffffff&#41;, C64&#40;0x0000ffffffffffff&#41;, C64&#40;0x00ffffffffffffff&#41; 
&#125;; 


/*******************************************************************/ 
// Macros

#define slideSquareMask&#40;x&#41;        ((&#40;1 << &#40;x&#41;) >> 1&#41; & 63&#41;
#define attackRank&#40;from&#41;          &#40;attackFromHorizontal&#91;from&#93;&#91;&#40;int&#41;(&#40;allPieces >> ((&#40;from&#41; & 0x38&#41; + 1&#41;) & 63&#41;&#93;)
#define attackFile&#40;from&#41;          &#40;attackFromVertical&#91;from&#93;&#91;slideIndexV&#91;&#40;from&#41; & 7&#93;&#93;)
#define attackDiagRightUp&#40;from&#41;   &#40;attackFromRightUp&#91;from&#93;&#91;slideIndexRU&#91;(&#40;from&#41; >> 3&#41; + (&#40;from&#41; & 7&#41;&#93;&#93;)
#define attackDiagRightDown&#40;from&#41; &#40;attackFromRightDown&#91;from&#93;&#91;slideIndexRD&#91;7 - (&#40;from&#41; >> 3&#41; + (&#40;from&#41; & 7&#41;&#93;&#93;)
#define attackFromBishop&#40;from&#41;    &#40;attackDiagRightUp&#40;from&#41; | attackDiagRightDown&#40;from&#41;)
#define attackFromRook&#40;from&#41;      &#40;attackRank&#40;from&#41;        | attackFile&#40;from&#41;)
#define attackFromQueen&#40;from&#41;     &#40;attackFromBishop&#40;from&#41;  | attackFromRook&#40;from&#41;)


/*******************************************************************/ 

// Initialisation of Rotated Indices
// Either done on engine start-up or by loading the precalculated attack tables from disk.
Bitboard indexToAttackFromHorizontal&#40;int s, unsigned int i&#41;
&#123;
    Bitboard a = 0;

    // to the right&#58;
    Bitboard x = Bitboard&#58;&#58;set_one_bit&#40; s );
    x.shift_r&#40;);
    unsigned int t = &#40;s & 7&#41; <= 1 ? 0 &#58; &#40;unsigned int&#41; 1 << (&#40;s & 7&#41; - 2&#41;;    
    while ( x & &#40;Bitboard&#41;C64&#40;0x7f7f7f7f7f7f7f7f&#41; )
    &#123;
        a |= x;
        if ( t == 0 || &#40;t & i&#41; )
        &#123;
            break;
        &#125;
        else
        &#123;
            x.shift_r&#40;);
            t >>= 1;
        &#125;
    &#125;

    // to the left&#58;
    x = Bitboard&#58;&#58;set_one_bit&#40; s );
    x.shift_l&#40;);
    t = &#40;s & 7&#41; >= 6 ? 0 &#58; &#40;unsigned int&#41; 1 << &#40;s & 7&#41;;
    while ( x & &#40;Bitboard&#41;C64&#40;0xfefefefefefefefe&#41; )
    &#123;
        a |= x;
        if ( t == 0 || t > 63 || &#40;t & i&#41; )
        &#123;
            break;
        &#125;
        else
        &#123;
            x.shift_l&#40;);
            t <<= 1;
        &#125;
    &#125;

    return a;
&#125;


/*******************************************************************/ 

Bitboard indexToAttackFromVertical &#40;int s, unsigned int i&#41;
&#123;
    Bitboard a = 0;

    // downwards&#58;
    Bitboard x = Bitboard&#58;&#58;set_one_bit&#40; s );
    x.shift_d&#40;);
    unsigned int t = &#40;s >> 3&#41; <= 1 ? 0 &#58; &#40;unsigned int&#41; 1 << (&#40;s >> 3&#41; - 2&#41;;
    while &#40;x&#41;
    &#123;
        a |= x;
        if ( t == 0 || &#40;t & i&#41; )
        &#123;
            break;
        &#125;
        else
        &#123;
            x.shift_d&#40;);
            t >>= 1;
        &#125;
    &#125;

    // upwards&#58;
    x = Bitboard&#58;&#58;set_one_bit&#40; s );
    x.shift_u&#40;);
    t = &#40;s >> 3&#41; >= 6 ? 0 &#58; &#40;unsigned int&#41; 1 << &#40;s >> 3&#41;;
    while &#40;x&#41;
    &#123;
        a |= x;
        if ( t == 0 || t > 63 || &#40;t & i&#41; )
        &#123;
            break;
        &#125;
        else
        &#123;
            x.shift_u&#40;);
            t <<= 1;
        &#125;
    &#125;

    return a;
&#125;


/*******************************************************************/ 

Bitboard indexToAttackFromRightUp &#40;int s, unsigned int i&#41;
&#123;
    Bitboard a = 0;

    // right up&#58;
    Bitboard x = Bitboard&#58;&#58;set_one_bit&#40; s );
    x.shift_ur&#40;);
    unsigned int t = &#40;s & 7&#41; <= 1 ? 0 &#58; &#40;unsigned int&#41; 1 << (&#40;s & 7&#41; - 2&#41;;    
    while ( x & &#40;Bitboard&#41;C64&#40;0x7f7f7f7f7f7f7f7f&#41; )
    &#123;
        a |= x;
        if ( t == 0 || &#40;t & i&#41; )
        &#123;
            break;
        &#125;
        else
        &#123;
            x.shift_ur&#40;);
            t >>= 1;
        &#125;
    &#125;

    // left down&#58;
    x = Bitboard&#58;&#58;set_one_bit&#40; s );
    x.shift_dl&#40;);
    t = &#40;s & 7&#41; >= 6 ? 0 &#58; &#40;unsigned int&#41; 1 << &#40;s & 7&#41;;
    while ( x & &#40;Bitboard&#41;C64&#40;0xfefefefefefefefe&#41; )
    &#123;
        a |= x;
        if ( t == 0 || t > 63 || &#40;t & i&#41; )
        &#123;
            break;
        &#125;
        else
        &#123;
            x.shift_dl&#40;);
            t <<= 1;
        &#125;
    &#125;

    return a;
&#125;


/*******************************************************************/ 

Bitboard indexToAttackFromRightDown &#40;int s, unsigned int i&#41;
&#123;
    Bitboard a = 0;

    // right down&#58;
    Bitboard x = Bitboard&#58;&#58;set_one_bit&#40; s );
    x.shift_dr&#40;);
    unsigned int t = &#40;s >> 3&#41; <= 1 ? 0 &#58; &#40;unsigned int&#41; 1 << (&#40;s >> 3&#41; - 2&#41;;
    while ( x & &#40;Bitboard&#41;C64&#40;0x7f7f7f7f7f7f7f7f&#41; )
    &#123;
        a |= x;
        if ( t == 0 || &#40;t & i&#41; )
        &#123;
            break;
        &#125;
        else
        &#123;
            x.shift_dr&#40;);
            t >>= 1;
        &#125;
    &#125;

    // left up&#58;
    x = Bitboard&#58;&#58;set_one_bit&#40; s );
    x.shift_ul&#40;);
    t = &#40;s >> 3&#41; >= 6 ? 0 &#58; &#40;unsigned int&#41; 1 << &#40;s >> 3&#41;;
    while ( x & &#40;Bitboard&#41;C64&#40;0xfefefefefefefefe&#41; )
    &#123;
        a |= x;
        if ( t == 0 || t > 63 || &#40;t & i&#41; )
        &#123;
            break;
        &#125;
        else
        &#123;
            x.shift_ul&#40;);
            t <<= 1;
        &#125;
    &#125;

    return a;
&#125;


/*******************************************************************/ 

/** 
Initialises Rotated Indices. Must be called once before using them.
*/ 
void initRotatedIndices&#40;) 
&#123; 
    for &#40;int s = 0; s < 64; s++)
    &#123;
        for &#40;int i = 0; i < 64; i++)
        &#123;
            attackFromHorizontal&#91;s&#93;&#91;i&#93;= indexToAttackFromHorizontal&#40; s, i ); 
            attackFromVertical&#91;s&#93;&#91;i&#93;  = indexToAttackFromVertical&#40; s, i ); 
            attackFromRightUp&#91;s&#93;&#91;i&#93;   = indexToAttackFromRightUp&#40; s, i ); 
            attackFromRightDown&#91;s&#93;&#91;i&#93; = indexToAttackFromRightDown&#40; s, i ); 
        &#125;
    &#125;
&#125; 


/*******************************************************************/ 

/** 
Called in Move.make&#40;) and in Move.unmake&#40;) to update Rotated Indices.
Precondition&#58; move m has been made/unmade on the board
*/ 
void updateRotatedIndices&#40; Board &board, const Move &m )
&#123; 
    if ( !m.exist&#40;) )
        return;

    //allPieces = board.wpieces_ | board.bpieces_;
    
    int fromRank = m.from&#40;) >> 3;
    int fromFile = m.from&#40;) & 7;
    int toRank = m.to&#40;) >> 3;
    int toFile = m.to&#40;) & 7;
    int mask;
    
    // update slide indices at from-square&#58;
    board.slideIndexV&#91;                fromFile&#93; ^= mask = slideSquareMask&#40;fromRank&#41;;
    board.slideIndexRU&#91;    fromRank + fromFile&#93; ^=        slideSquareMask&#40;fromFile&#41;;
    board.slideIndexRD&#91;7 - fromRank + fromFile&#93; ^= mask;
    
    // update slide indices at to-square&#58;
    //if (!m.isCapture&#40;) /* note&#58; an en passant capture has isCapture&#40;) == false */)
    if ( m.type&#40;) != Move&#58;&#58;Capture || m.type&#40;) == Move&#58;&#58;En_Passant )
    &#123;
        board.slideIndexV&#91;              toFile&#93; ^= mask = slideSquareMask&#40;toRank&#41;;
        board.slideIndexRU&#91;    toRank + toFile&#93; ^=        slideSquareMask&#40;toFile&#41;;
        board.slideIndexRD&#91;7 - toRank + toFile&#93; ^= mask;
    &#125;
    
    // special moves&#58;
    //if &#40;m.getType&#40;) != 0&#41;
    if ( m.type&#40;) != Move&#58;&#58;Undefined )
    &#123;
        //if &#40;m.getType&#40;) == MOVE_TYPE_ENPASSANT_CAPTURE&#41; &#123;
        if ( m.type&#40;) == Move&#58;&#58;En_Passant )
        &#123;
            // go one square back&#58;
            //Square to = m.getPlayer&#40;).isWhite&#40;) ? m.to + 8 &#58; m.to - 8;
            byte to = m.to&#40;) > m.from&#40;) ? m.to&#40;) - 8 &#58; m.to&#40;) + 8;
            // update slide indices for captured piece&#58;
            toRank = to >> 3;
            toFile = to & 7;
            board.slideIndexV&#91;              toFile&#93; ^= mask = slideSquareMask&#40;toRank&#41;;
            board.slideIndexRU&#91;    toRank + toFile&#93; ^=        slideSquareMask&#40;toFile&#41;;
            board.slideIndexRD&#91;7 - toRank + toFile&#93; ^= mask;
        &#125;
        //else if &#40;m.getType&#40;) == MOVE_TYPE_CASTLING_SHORT || m.getType&#40;) == MOVE_TYPE_CASTLING_LONG&#41;
        else if ( m.type&#40;) == Move&#58;&#58;Castling )
        &#123;
            //Square rookFrom;
            //Square rookTo;
            //if &#40;m.getType&#40;) == MOVE_TYPE_CASTLING_SHORT&#41; &#123;
            //...
            byte rookFrom = m.rook_from&#40;);
            byte rookTo = m.rook_to&#40;);
            
            // update slide indices at rook's from-square&#58;
            fromRank = rookFrom >> 3;
            fromFile = rookFrom & 7;
            board.slideIndexV&#91;                fromFile&#93; ^= mask = slideSquareMask&#40;fromRank&#41;;
            board.slideIndexRU&#91;    fromRank + fromFile&#93; ^=        slideSquareMask&#40;fromFile&#41;;
            board.slideIndexRD&#91;7 - fromRank + fromFile&#93; ^= mask;
            
            // update slide indices at rook's to-square&#58;
            toRank = rookTo >> 3;
            toFile = rookTo & 7;
            board.slideIndexV&#91;              toFile&#93; ^= mask = slideSquareMask&#40;toRank&#41;;
            board.slideIndexRU&#91;    toRank + toFile&#93; ^=        slideSquareMask&#40;toFile&#41;;
            board.slideIndexRD&#91;7 - toRank + toFile&#93; ^= mask;        
        &#125;
    &#125;
&#125; 


/*******************************************************************/ 

void Board&#58;&#58;init_slider_attacks_index&#40;)
&#123;
    initRotatedIndices&#40;);
&#125;


/*******************************************************************/ 

void Board&#58;&#58;set_all_rotated_bitboards&#40;)
&#123;
    allPieces = wpieces_ | bpieces_;
    int i;
    for ( i = 0; i < 8; ++i )
    &#123;
        slideIndexV&#91;i&#93; = 0;
    &#125;
    for ( i = 0; i < 15; ++i )
    &#123;
        slideIndexRU&#91;i&#93; = 0;
        slideIndexRD&#91;i&#93; = 0;
    &#125;
    for ( int sq = 0; sq < 64; ++sq )
    &#123;
        int f = sq & 7;
        int r = sq >> 3;
        if ( r > 0 && r < 7 )
        &#123;
            slideIndexV&#91;f&#93; |= ( allPieces.test_bit&#40;sq&#41; ? slideSquareMask&#40;r&#41; &#58; 0 );
        &#125;
        if ( f > 0 && f < 7 && r > 0 && r < 7 )
        &#123;
            slideIndexRU&#91;    r + f&#93; |= ( allPieces.test_bit&#40;sq&#41; ? slideSquareMask&#40;f&#41; &#58; 0 );
            slideIndexRD&#91;7 - r + f&#93; |= ( allPieces.test_bit&#40;sq&#41; ? slideSquareMask&#40;r&#41; &#58; 0 );
        &#125;
    &#125;
&#125;


/*******************************************************************/ 

/** 
Get a bitboard with all positions set to 1 which can be attacked 
from a bishop, rook or queen on the square moving in the direction. 
*/ 
Bitboard Board&#58;&#58;direction_attacks&#40; byte square, byte dir ) const 
&#123; 
    allPieces = wpieces_ | bpieces_;
    Bitboard result; 
    
    // 4 3 2 
    // 5 0 1 
    // 6 7 8 
    switch ( dir ) 
    &#123; 
      case 1&#58;
        result = attackRank&#40;square&#41; & dirMaskRight&#91;square & 7&#93;;
        break;
        
      case 2&#58; 
        result = attackDiagRightUp&#40;square&#41; & dirMaskRight&#91;square & 7&#93;;
        break;
        
      case 3&#58; 
        result = attackFile&#40;square&#41; & dirMaskUp&#91;square >> 3&#93;;
        break;
        
      case 4&#58; 
        result = attackDiagRightDown&#40;square&#41; & dirMaskLeft&#91;square & 7&#93;;
        break;
        
      case 5&#58; 
        result = attackRank&#40;square&#41; & dirMaskLeft&#91;square & 7&#93;;
        break;
        
      case 6&#58; 
        result = attackDiagRightUp&#40;square&#41; & dirMaskLeft&#91;square & 7&#93;;
        break;
        
      case 7&#58; 
        result = attackFile&#40;square&#41; & dirMaskDown&#91;square >> 3&#93;;
        break;
        
      case 8&#58; 
        result = attackDiagRightDown&#40;square&#41; & dirMaskRight&#91;square & 7&#93;;
        break;
       
      default&#58; 
        result = 0; 
        break; 
    &#125;

    return result; 
&#125; 


/*******************************************************************/ 

/** 
Get a bitboard with all positions set to 1 which can be attacked 
from a rook and queen on the square. 
*/ 
Bitboard Board&#58;&#58;orthogonal_attacks&#40; byte square ) const 
&#123; 
    allPieces = wpieces_ | bpieces_;
    return attackFromRook&#40;square&#41;;
&#125; 


/*******************************************************************/ 

/** 
Get a bitboard with all positions set to 1 which can be attacked 
from a bishop and queen on the square. 
*/ 
Bitboard Board&#58;&#58;diagonal_attacks&#40; byte square ) const 
&#123; 
    allPieces = wpieces_ | bpieces_;
    return attackFromBishop&#40;square&#41;; 
&#125; 


/*******************************************************************/ 

#endif // USE_ROTATED_INDICES&#40;)

Harald
Posts: 265
Joined: Thu Mar 09, 2006 12:07 am

Re: BitBoard Tests (Michael Sherwin)

Post by Harald » Sat Aug 25, 2007 6:58 am

bb_attacks_sherwin.cpp:

Code: Select all

/*******************************************************************/
/*
The bitboard attacks of Michael Sherwin 
as part of the board structure.

&#40;c&#41; 2006 Harald Lüßen
*/
/*******************************************************************/


#include "bb_ifdef.h"
#include "bb_basics.h"
#include "bb_bitboard.h"
#include "bb_board.h"
#include "bb_main.h"


#if USE_SHERWIN_BITBOARDS&#40;)

/*******************************************************************/

/*
    directions and shifts
    +-----+-----+-----+
    |<<= 9|<<= 8|<<= 7|
    +-----+-----+-----+
    |<<= 1|     |>>= 1|
    +-----+-----+-----+
    |>>= 7|>>= 8|>>= 9|
    +-----+-----+-----+

    We use this mapping of the normal board squares to bitboard bits
    +-------------------------+
    | 63 62 61 60 59 58 57 56 | 8
    | 55 54 53 52 51 50 49 48 | 7
    | 47 46 45 44 43 42 41 40 | 6
    | 39 38 37 36 35 35 33 32 | 5
    | 31 30 29 28 27 26 25 24 | 4
    | 23 22 21 20 19 18 17 16 | 3
    | 15 14 13 12 11 10  9  8 | 2
    |  7  6  5  4  3  2  1  0 | 1
    +-------------------------+
       a  b  c  d  e  f  g  h
*/

/*******************************************************************/

// Bishops

/*
The typical 1-bits of a bishop on d4 are shown below, 
with - indicating a don't care bit&#58;
 . . . . . . . -
 - . . . . . 1 .  giving 1 bit  or 2 different values from row 7
 . 1 . . . 1 . .  giving 2 bits or 4 different values from row 6
 . . 1 . 1 . . .  giving 2 bits or 4 different values from row 5
 . . . B . . . .  giving 0 bits or 0 different values from row 4
 . . 1 . 1 . . .  giving 2 bits or 4 different values from row 3
 . 1 . . . 1 . .  giving 2 bits or 4 different values from row 2
 - . . . . . - .

The values are just a mapping of the relevant bits to a compact value. 
For bits named a to i the value for Bd4 will be&#58;
 . . . . . . . -
 - . . . . . i .  giving 1 bit  or 2 different values from row 7
 . g . . . h . .  giving 2 bits or 4 different values from row 6
 . . e . f . . .  giving 2 bits or 4 different values from row 5
 . . . B . . . .  giving 0 bits or 0 different values from row 4
 . . c . d . . .  giving 2 bits or 4 different values from row 3
 . a . . . b . .  giving 2 bits or 4 different values from row 2
 - . . . . . - .

-> 0x0000000ihgfedcba as index. With 2^9 = 512 index values. 

There are 4 squares with 9 bits like Bd4. Other squares need another amount of bits.

 6 5 5 5 5 5 5 6
 5 5 5 5 5 5 5 5
 5 5 7 7 7 7 5 5
 5 5 7 9 9 7 5 5
 5 5 7 9 9 7 5 5
 5 5 7 7 7 7 5 5
 5 5 5 5 5 5 5 5
 6 5 5 5 5 5 5 6

 4 squares with 9 bits for 512 indices are 2048 indices.
12 squares with 7 bits for 128 indices are 1536 indices.
44 squares with 5 bits for  32 indices are 1408 indices.
 4 squares with 6 bits for  64 indices are  256 indices.
                                     Total 5248 indices.
*/

// The big X mask for all moves from sq, but only inner 6x6 area
Bitboard bishopBits&#91;64&#93;;

void initBishopBits&#40;)
&#123;
    int sq;
    for ( sq = 0; sq < 64; ++sq )
    &#123;
        bishopBits&#91;sq&#93; = 0;
        int i;
        for ( i = sq - 9; i >= 0 && i % 8 != 7; i -= 9 )
        &#123;
            bishopBits&#91;sq&#93; |= C64&#40;1&#41; << i;
        &#125;
        for ( i = sq - 7; i >= 0 && i % 8 != 0; i -= 7 )
        &#123;
            bishopBits&#91;sq&#93; |= C64&#40;1&#41; << i;
        &#125;
        for ( i = sq + 9; i < 64 && i % 8 != 0; i += 9 )
        &#123;
            bishopBits&#91;sq&#93; |= C64&#40;1&#41; << i;
        &#125;
        for ( i = sq + 7; i < 64 && i % 8 != 7; i += 7 )
        &#123;
            bishopBits&#91;sq&#93; |= C64&#40;1&#41; << i;
        &#125;
        bishopBits&#91;sq&#93; &= C64&#40;0x007e7e7e7e7e7e00&#41;;
        //logf << "bishopBits " << sq << endl;
        //logf << bishopBits&#91;sq&#93;.txt8lines&#40;) << endl;
    &#125;
&#125;


// Number of needed bits per square for bishops
const byte squareBitsB&#91;64&#93; = 
&#123;
  6, 5, 5, 5, 5, 5, 5, 6,
  5, 5, 5, 5, 5, 5, 5, 5,
  5, 5, 7, 7, 7, 7, 5, 5,
  5, 5, 7, 9, 9, 7, 5, 5,
  5, 5, 7, 9, 9, 7, 5, 5,
  5, 5, 7, 7, 7, 7, 5, 5,
  5, 5, 5, 5, 5, 5, 5, 5,
  6, 5, 5, 5, 5, 5, 5, 6,
&#125;;


/*
The big Table with index-bits for all rows.
The indices are in this order&#58;
0000999999999 4 times 9 bit
0001999999999
0010999999999
0011999999999
0100007777777 12 times 7 bit
01....7777777
0110117777777
0111000666666 4 times 6 bit
0111001666666
0111010666666
0111011666666
0111100055555 44 times 5 bit
........55555
1010001155555
bishopRows&#91;sq&#93;&#91;row2to7&#93;&#91;bitsOnRow&#93;
*/
short int bishopRows&#91;64&#93;&#91;6&#93;&#91;64&#93;;

void initBishopRows&#40;)
&#123;
    int baseIndex = 0;
    for ( int bits = 9; bits >= 5; --bits )
    &#123;
        for ( int sq = 0; sq < 64; ++sq )
        &#123;
            if ( squareBitsB&#91;sq&#93; != bits )
                continue;
            Bitboard bb = bishopBits&#91;sq&#93;;
            bb >>= 9;
            int shift = 0;
            for ( int row = 0; row < 6; ++row )
            &#123;
                int p = &#40;bb >> &#40;row * 8&#41;) & 0x3f;
                for ( int pattern = 0; pattern < 64; ++pattern )
                &#123;
                    int index = 0;
                    int s = shift;
                    for ( int i = 0; i < 6; ++i )
                    &#123;
                        if ( p & &#40;1 << i&#41; )
                        &#123;
                            index |= ( &#40;pattern & &#40;1 << i&#41;) ? &#40;1 << s&#41; &#58; 0 );
                            s++;
                            if ( pattern == 63 )
                                shift++;
                        &#125;
                    &#125;
                    bishopRows&#91;sq&#93;&#91;row&#93;&#91;pattern&#93; = baseIndex + index;
                    //logf << "bishopRows " << sq << " " << row << " " << pattern << " &#58; ";
                    //logf << bishopRows&#91;sq&#93;&#91;row&#93;&#91;pattern&#93; << endl;
                &#125;
            &#125;
            baseIndex += &#40;1 << bits&#41;;
        &#125;
    &#125;
&#125;


// From index to attack bits
Bitboard bishopAttackTable&#91;5248&#93;;

void initBishopAttacks&#40;)
&#123;
    int baseIndex = 0;
    for ( int bits = 9; bits >= 5; --bits )
    &#123;
        for ( int sq = 0; sq < 64; ++sq )
        &#123;
            if ( squareBitsB&#91;sq&#93; != bits )
                continue;
            Bitboard bb = bishopBits&#91;sq&#93;;
            for ( int index = 0; index < &#40;1 << bits&#41;; ++ index )
            &#123;
                Bitboard occ = 0;
                int i = index;
                for ( int rsq = 0; rsq < 64; ++rsq )
                &#123;
                    if ( bb.test_bit&#40; rsq ) )
                    &#123;
                        if ( i & 1 )
                            occ.set_bit&#40; rsq );
                        i >>= 1;
                    &#125;
                &#125;
                Bitboard att = 0;
                int j;
                for ( j = sq + 9; j < 64 && &#40;j & 7&#41; != 0; j += 9 )
                &#123;
                    att.set_bit&#40; j );
                    if ( occ.test_bit&#40; j ) )
                        break;
                &#125;
                for ( j = sq + 7; j < 64 && &#40;j & 7&#41; != 7; j += 7 )
                &#123;
                    att.set_bit&#40; j );
                    if ( occ.test_bit&#40; j ) )
                        break;
                &#125;
                for ( j = sq - 9; j >= 0 && &#40;j & 7&#41; != 7; j -= 9 )
                &#123;
                    att.set_bit&#40; j );
                    if ( occ.test_bit&#40; j ) )
                        break;
                &#125;
                for ( j = sq - 7; j >= 0 && &#40;j & 7&#41; != 0; j -= 7 )
                &#123;
                    att.set_bit&#40; j );
                    if ( occ.test_bit&#40; j ) )
                        break;
                &#125;
                bishopAttackTable&#91;baseIndex + index&#93; = att;
            &#125;
            baseIndex += &#40;1 << bits&#41;;
        &#125;
    &#125;
&#125;


/**
The bishop attack bitboard for a square and occupied bitboard
*/
Bitboard bishopAttacks&#40; int sq, Bitboard occ )
&#123;
    // The remaining blocking pieces in the X-rays
    occ  &= bishopBits&#91;sq&#93;; 
    occ >>= 9;

    // Since every square has its set of row values the six row lookups 
    // simply map any blockers to specific bits that when ored together 
    // gives an offset in the bishop attack table.
    short int *bRows = &bishopRows&#91;sq&#93;&#91;0&#93;&#91;0&#93;;
    int index = &#40;bRows +   0&#41;&#91;&#40;occ >>  0&#41; & 0x3f&#93;  // row 2
              | &#40;bRows +  64&#41;&#91;&#40;occ >>  8&#41; & 0x3f&#93;  // row 3
              | &#40;bRows + 128&#41;&#91;&#40;occ >> 16&#41; & 0x3f&#93;  // row 4
              | &#40;bRows + 192&#41;&#91;&#40;occ >> 24&#41; & 0x3f&#93;  // row 5
              | &#40;bRows + 256&#41;&#91;&#40;occ >> 32&#41; & 0x3f&#93;  // row 6
              | &#40;bRows + 320&#41;&#91;&#40;occ >> 40&#41; & 0x3f&#93;; // row 7
    return bishopAttackTable&#91;index&#93;;
&#125;


/*******************************************************************/

// Rooks

/*
The required bit number per square for rooks looks like this&#58;

12 11 11 11 11 11 11 12    4 x 12 bit =  4 x 4096 entries = 16384
11 10 10 10 10 10 10 11   24 x 11 bit = 24 x 2048 entries = 49152
11 10 10 10 10 10 10 11   36 x 10 bit = 36 x 1024 entries = 36864
11 10 10 10 10 10 10 11                            total = 102400
11 10 10 10 10 10 10 11
11 10 10 10 10 10 10 11
11 10 10 10 10 10 10 11
12 11 11 11 11 11 11 12
*/

// The big + mask for all moves from sq
Bitboard rookBits&#91;64&#93;;

void initRookBits&#40;)
&#123;
    int sq;
    for ( sq = 0; sq < 64; ++sq )
    &#123;
        rookBits&#91;sq&#93; = 0;
        int i;
        for ( i = sq - 1; i >= 0 && i % 8 != 7; --i )
        &#123;
            rookBits&#91;sq&#93; |= C64&#40;1&#41; << i;
        &#125;
        for ( i = sq - 8; i >= 0; i -= 8 )
        &#123;
            rookBits&#91;sq&#93; |= C64&#40;1&#41; << i;
        &#125;
        for ( i = sq + 1; i < 64 && i % 8 != 0; ++i )
        &#123;
            rookBits&#91;sq&#93; |= C64&#40;1&#41; << i;
        &#125;
        for ( i = sq + 8; i < 64; i += 8 )
        &#123;
            rookBits&#91;sq&#93; |= C64&#40;1&#41; << i;
        &#125;
        if ( &#40;sq & 7&#41; != 7 )
            rookBits&#91;sq&#93; &= C64&#40;0x7f7f7f7f7f7f7f7f&#41;;
        if ( &#40;sq & 7&#41; != 0 )
            rookBits&#91;sq&#93; &= C64&#40;0xfefefefefefefefe&#41;;
        if ( &#40;sq / 8&#41; != 7 )
            rookBits&#91;sq&#93; &= C64&#40;0x00ffffffffffffff&#41;;
        if ( &#40;sq / 8&#41; != 0 )
            rookBits&#91;sq&#93; &= C64&#40;0xffffffffffffff00&#41;;
        //logf << "rookBits " << sq << endl;
        //logf << rookBits&#91;sq&#93;.txt8lines&#40;) << endl;
    &#125;
&#125;


// Number of needed bits per square for rooks
const byte squareBitsR&#91;64&#93; = 
&#123;
  12, 11, 11, 11, 11, 11, 11, 12,
  11, 10, 10, 10, 10, 10, 10, 11,
  11, 10, 10, 10, 10, 10, 10, 11,
  11, 10, 10, 10, 10, 10, 10, 11,
  11, 10, 10, 10, 10, 10, 10, 11,
  11, 10, 10, 10, 10, 10, 10, 11,
  11, 10, 10, 10, 10, 10, 10, 11,
  12, 11, 11, 11, 11, 11, 11, 12,
&#125;;


/*
The big Table with index-bits for all rows.
The indices are in this order&#58;
00000cccccccccccc 4 times 12 bit
00001cccccccccccc
00010cccccccccccc
00011cccccccccccc
001000bbbbbbbbbbb 24 times 11 bit
0.....bbbbbbbbbbb
100111bbbbbbbbbbb
1010000aaaaaaaaaa 36 times 10 bit
.......aaaaaaaaaa
1110011aaaaaaaaaa
This index is very big because its values &#40;0-102400&#41; do not fit in 2 byte short int.
rookRows&#91;sq&#93;&#91;row1to8&#93;&#91;bitsOnRow&#93;
*/
int rookRows&#91;64&#93;&#91;8&#93;&#91;256&#93;;

void initRookRows&#40;)
&#123;
    int baseIndex = 0;
    for ( int bits = 12; bits >= 10; --bits )
    &#123;
        for ( int sq = 0; sq < 64; ++sq )
        &#123;
            if ( squareBitsR&#91;sq&#93; != bits )
                continue;
            Bitboard bb = rookBits&#91;sq&#93;;
            int shift = 0;
            for ( int row = 0; row < 8; ++row )
            &#123;
                int p = &#40;bb >> &#40;row * 8&#41;) & 0xff;
                for ( int pattern = 0; pattern < 256; ++pattern )
                &#123;
                    int index = 0;
                    int s = shift;
                    for ( int i = 0; i < 8; ++i )
                    &#123;
                        if ( p & &#40;1 << i&#41; )
                        &#123;
                            index |= ( &#40;pattern & &#40;1 << i&#41;) ? &#40;1 << s&#41; &#58; 0 );
                            s++;
                            if ( pattern == 255 )
                                shift++;
                        &#125;
                    &#125;
                    rookRows&#91;sq&#93;&#91;row&#93;&#91;pattern&#93; = baseIndex + index;
                    //logf << "rookRows " << sq << " " << row << " " << pattern << " &#58; ";
                    //logf << rookRows&#91;sq&#93;&#91;row&#93;&#91;pattern&#93; << endl;
                &#125;
            &#125;
            baseIndex += &#40;1 << bits&#41;;
        &#125;
    &#125;
&#125;


// From index to attack bits
Bitboard rookAttackTable&#91;102400&#93;;

void initRookAttacks&#40;)
&#123;
    int baseIndex = 0;
    for ( int bits = 12; bits >= 10; --bits )
    &#123;
        for ( int sq = 0; sq < 64; ++sq )
        &#123;
            if ( squareBitsR&#91;sq&#93; != bits )
                continue;
            Bitboard bb = rookBits&#91;sq&#93;;
            for ( int index = 0; index < &#40;1 << bits&#41;; ++ index )
            &#123;
                Bitboard occ = 0;
                int i = index;
                for ( int rsq = 0; rsq < 64; ++rsq )
                &#123;
                    if ( bb.test_bit&#40; rsq ) )
                    &#123;
                        if ( i & 1 )
                            occ.set_bit&#40; rsq );
                        i >>= 1;
                    &#125;
                &#125;
                Bitboard att = 0;
                int j;
                for ( j = sq + 1; j < 64 && &#40;j & 7&#41; != 0; ++j )
                &#123;
                    att.set_bit&#40; j );
                    if ( occ.test_bit&#40; j ) )
                        break;
                &#125;
                for ( j = sq + 8; j < 64; j += 8 )
                &#123;
                    att.set_bit&#40; j );
                    if ( occ.test_bit&#40; j ) )
                        break;
                &#125;
                for ( j = sq - 1; j >= 0 && &#40;j & 7&#41; != 7; --j )
                &#123;
                    att.set_bit&#40; j );
                    if ( occ.test_bit&#40; j ) )
                        break;
                &#125;
                for ( j = sq - 8; j >= 0; j -= 8 )
                &#123;
                    att.set_bit&#40; j );
                    if ( occ.test_bit&#40; j ) )
                        break;
                &#125;
                rookAttackTable&#91;baseIndex + index&#93; = att;
            &#125;
            baseIndex += &#40;1 << bits&#41;;
        &#125;
    &#125;
&#125;


/**
The rook attack bitboard for a square and occupied bitboard
*/
Bitboard rookAttacks&#40; int sq, Bitboard occ )
&#123;
    // The remaining blocking pieces in the +-rays
    occ &= rookBits&#91;sq&#93;; 

    // Since every square has its set of row values the six row lookups 
    // simply map any blockers to specific bits that when ored together 
    // gives an offset in the bishop attack table.
    int *rRows = &rookRows&#91;sq&#93;&#91;0&#93;&#91;0&#93;;
    int index = &#40;rRows +    0&#41;&#91;&#40;occ >>  0&#41; & 0xff&#93;  // row 1
              | &#40;rRows +  256&#41;&#91;&#40;occ >>  8&#41; & 0xff&#93;  // row 2
              | &#40;rRows +  512&#41;&#91;&#40;occ >> 16&#41; & 0xff&#93;  // row 3
              | &#40;rRows +  768&#41;&#91;&#40;occ >> 24&#41; & 0xff&#93;  // row 4
              | &#40;rRows + 1024&#41;&#91;&#40;occ >> 32&#41; & 0xff&#93;  // row 5
              | &#40;rRows + 1280&#41;&#91;&#40;occ >> 40&#41; & 0xff&#93;  // row 6
              | &#40;rRows + 1536&#41;&#91;&#40;occ >> 48&#41; & 0xff&#93;  // row 7
              | &#40;rRows + 1792&#41;&#91;&#40;occ >> 56&#41; & 0xff&#93;; // row 8
    return rookAttackTable&#91;index&#93;;
&#125;


/*******************************************************************/

const Bitboard dirMaskRight&#91;8&#93; =
&#123;
    // 0, line_h, line_gh, line_fh, line_eh, line_dh, line_ch, line_bh, 
    0, C64&#40;0x0101010101010101&#41;, C64&#40;0x0303030303030303&#41;, C64&#40;0x0707070707070707&#41;, C64&#40;0x0f0f0f0f0f0f0f0f&#41;, 
    C64&#40;0x1f1f1f1f1f1f1f1f&#41;, C64&#40;0x3f3f3f3f3f3f3f3f&#41;, C64&#40;0x7f7f7f7f7f7f7f7f&#41;
&#125;;

const Bitboard dirMaskLeft&#91;8&#93; =
&#123;
    // line_ag, line_af, line_ae, line_ad, line_ac, line_ab, line_a, 0, 
    C64&#40;0xfefefefefefefefe&#41;, C64&#40;0xfcfcfcfcfcfcfcfc&#41;, C64&#40;0xf8f8f8f8f8f8f8f8&#41;, C64&#40;0xf0f0f0f0f0f0f0f0&#41;, 
    C64&#40;0xe0e0e0e0e0e0e0e0&#41;, C64&#40;0xc0c0c0c0c0c0c0c0&#41;, C64&#40;0x8080808080808080&#41;, 0
&#125;;

const Bitboard dirMaskUp&#91;8&#93; =
&#123;
    // row_28, row_38, row_48, row_58, row_68, row_78, row_8, 0, 
    C64&#40;0xffffffffffffff00&#41;, C64&#40;0xffffffffffff0000&#41;, C64&#40;0xffffffffff000000&#41;, C64&#40;0xffffffff00000000&#41;, 
    C64&#40;0xffffff0000000000&#41;, C64&#40;0xffff000000000000&#41;, C64&#40;0xff00000000000000&#41;, 0
&#125;;

const Bitboard dirMaskDown&#91;8&#93; =
&#123;
    // 0, row_1, row_12, row_13, row_14, row_15, row_16, row_17,
    0, C64&#40;0x00000000000000ff&#41;, C64&#40;0x000000000000ffff&#41;, C64&#40;0x0000000000ffffff&#41;, C64&#40;0x00000000ffffffff&#41;, 
    C64&#40;0x000000ffffffffff&#41;, C64&#40;0x0000ffffffffffff&#41;, C64&#40;0x00ffffffffffffff&#41;
&#125;;


/*******************************************************************/
/*******************************************************************/

/**
Prepare the slider attacks back transformation table.
Put the scattered bits of an sliding attack pattern 
back to the original bitboard.
*/
void Board&#58;&#58;init_slider_attacks_index&#40;)
&#123;
    initBishopBits&#40;);
    initBishopRows&#40;);
    initBishopAttacks&#40;);
    initRookBits&#40;);
    initRookRows&#40;);
    initRookAttacks&#40;);
&#125;


/*******************************************************************/

/**
Get a bitboard with all positions set to 1 which can be attacked 
from a bishop, rook or queen on the square moving in the direction.
*/
Bitboard Board&#58;&#58;direction_attacks&#40; byte square, byte dir ) const
&#123;
    Bitboard result;
    Bitboard occ = wpieces_ | bpieces_;

    // 4 3 2
    // 5 0 1
    // 6 7 8
    switch ( dir )
    &#123;
      case 1&#58;
        result = rookAttacks&#40; square, occ );
        result &= dirMaskRight&#91;square & 7&#93;;
        break;
      case 5&#58;
        result = rookAttacks&#40; square, occ );
        result &= dirMaskLeft&#91;square & 7&#93;;
        break;
      case 7&#58;
        result = rookAttacks&#40; square, occ );
        result &= dirMaskDown&#91;square >> 3&#93;;
        break;
      case 3&#58;
        result = rookAttacks&#40; square, occ );
        result &= dirMaskUp&#91;square >> 3&#93;;
        break;
      case 8&#58;
        result = bishopAttacks&#40; square, occ );
        result &= dirMaskRight&#91;square & 7&#93;;
        result &= dirMaskDown&#91;square >> 3&#93;;
        break;
      case 4&#58;
        result = bishopAttacks&#40; square, occ );
        result &= dirMaskLeft&#91;square & 7&#93;;
        result &= dirMaskUp&#91;square >> 3&#93;;
        break;
      case 2&#58;
        result = bishopAttacks&#40; square, occ );
        result &= dirMaskRight&#91;square & 7&#93;;
        result &= dirMaskUp&#91;square >> 3&#93;;
        break;
      case 6&#58;
        result = bishopAttacks&#40; square, occ );
        result &= dirMaskLeft&#91;square & 7&#93;;
        result &= dirMaskDown&#91;square >> 3&#93;;
        break;
      default&#58;
        result = 0;
        break;
    &#125;

    return result;
&#125;


/*******************************************************************/

/**
Get a bitboard with all positions set to 1 which can be attacked 
from a rook or queen on the square.
*/
Bitboard Board&#58;&#58;orthogonal_attacks&#40; byte square ) const
&#123;
    Bitboard occ = wpieces_ | bpieces_;
    Bitboard result = rookAttacks&#40; square, occ );
    return result;
&#125;


/*******************************************************************/

/**
Get a bitboard with all positions set to 1 which can be attacked 
from a bishop or queen on the square.
*/
Bitboard Board&#58;&#58;diagonal_attacks&#40; byte square ) const
&#123;
    Bitboard occ = wpieces_ | bpieces_;
    Bitboard result = bishopAttacks&#40; square, occ );
    return result;
&#125;


/*******************************************************************/

#endif // #if USE_SHERWIN_BITBOARDS&#40;)

Harald
Posts: 265
Joined: Thu Mar 09, 2006 12:07 am

Re: BitBoard Tests (Kogge Stone)

Post by Harald » Sat Aug 25, 2007 6:59 am

bb_attacks_kogge_stone.cpp:

Code: Select all

/*******************************************************************/
/*
The Kogge-Stone bitboard attacks 
as part of the board structure. 
The original code comes from Steffan Westcott. 
With a Kogge-Stone method the move generation should be changed from 
'for each slider do all directions' to 'for each direction do all sliders'.
I have not done this.

&#40;c&#41; 2006 Harald Lüßen
*/
/*******************************************************************/


#include "bb_ifdef.h"
#include "bb_basics.h"
#include "bb_bitboard.h"
#include "bb_board.h"
#include "bb_main.h"


#if USE_KOGGE_STONE_BITBOARDS&#40;)

/*******************************************************************/

/*
    directions and shifts
    +-----+-----+-----+
    |<<= 9|<<= 8|<<= 7|
    +-----+-----+-----+
    |<<= 1|     |>>= 1|
    +-----+-----+-----+
    |>>= 7|>>= 8|>>= 9|
    +-----+-----+-----+

    We use this mapping of the normal board squares to bitboard bits
    +-------------------------+
    | 63 62 61 60 59 58 57 56 | 8
    | 55 54 53 52 51 50 49 48 | 7
    | 47 46 45 44 43 42 41 40 | 6
    | 39 38 37 36 35 35 33 32 | 5
    | 31 30 29 28 27 26 25 24 | 4
    | 23 22 21 20 19 18 17 16 | 3
    | 15 14 13 12 11 10  9  8 | 2
    |  7  6  5  4  3  2  1  0 | 1
    +-------------------------+
       a  b  c  d  e  f  g  h
*/

/*******************************************************************/

typedef unsigned __int64 BitBoard;

///////////////////////////////////////////////////////////////////////////

BitBoard ShiftUp       &#40;BitBoard b&#41; &#123; return  b<<8; &#125;
BitBoard ShiftDown     &#40;BitBoard b&#41; &#123; return  b>>8; &#125;
BitBoard ShiftLeft     &#40;BitBoard b&#41; &#123; return &#40;b<<1&#41; & C64&#40;0xfefefefefefefefe&#41;; &#125;
BitBoard ShiftRight    &#40;BitBoard b&#41; &#123; return &#40;b>>1&#41; & C64&#40;0x7f7f7f7f7f7f7f7f&#41;; &#125;
BitBoard ShiftUpLeft   &#40;BitBoard b&#41; &#123; return &#40;b<<9&#41; & C64&#40;0xfefefefefefefefe&#41;; &#125;
BitBoard ShiftUpRight  &#40;BitBoard b&#41; &#123; return &#40;b<<7&#41; & C64&#40;0x7f7f7f7f7f7f7f7f&#41;; &#125;
BitBoard ShiftDownLeft &#40;BitBoard b&#41; &#123; return &#40;b>>7&#41; & C64&#40;0xfefefefefefefefe&#41;; &#125;
BitBoard ShiftDownRight&#40;BitBoard b&#41; &#123; return &#40;b>>9&#41; & C64&#40;0x7f7f7f7f7f7f7f7f&#41;; &#125;

///////////////////////////////////////////////////////////////////////////

/**
The routine FillUpOccluded&#40;) smears the set bits of bitboard g upwards, but only
along set bits of p; a reset bit in p is enough to halt a smear. RookAttacksUp&#40;)
uses this routine to find all squares rooks may occupy by either staying still
or moving up along empty squares &#40;no captures allowed&#41;. Shifting this last
result up by 1 square gives the squares all rooks can attack by moving upwards
&#40;which _does_ include captures&#41;.
*/
BitBoard FillUpOccluded&#40;BitBoard g, BitBoard p&#41;
&#123;
           g |= p & &#40;g <<  8&#41;;
           p &=     &#40;p <<  8&#41;;
           g |= p & &#40;g << 16&#41;;
           p &=     &#40;p << 16&#41;;
    return g |= p & &#40;g << 32&#41;;
&#125;

BitBoard FillDownOccluded&#40;BitBoard g, BitBoard p&#41;
&#123;
           g |= p & &#40;g >>  8&#41;;
           p &=     &#40;p >>  8&#41;;
           g |= p & &#40;g >> 16&#41;;
           p &=     &#40;p >> 16&#41;;
    return g |= p & &#40;g >> 32&#41;;
&#125;

BitBoard FillLeftOccluded&#40;BitBoard g, BitBoard p&#41;
&#123;
           p &= C64&#40;0xfefefefefefefefe&#41;;
           g |= p & &#40;g << 1&#41;;
           p &=     &#40;p << 1&#41;;
           g |= p & &#40;g << 2&#41;;
           p &=     &#40;p << 2&#41;;
    return g |= p & &#40;g << 4&#41;;
&#125;

BitBoard FillRightOccluded&#40;BitBoard g, BitBoard p&#41;
&#123;
           p &= C64&#40;0x7f7f7f7f7f7f7f7f&#41;;
           g |= p & &#40;g >> 1&#41;;
           p &=     &#40;p >> 1&#41;;
           g |= p & &#40;g >> 2&#41;;
           p &=     &#40;p >> 2&#41;;
    return g |= p & &#40;g >> 4&#41;;
&#125;

BitBoard FillUpLeftOccluded&#40;BitBoard g, BitBoard p&#41;
&#123;
           p &= C64&#40;0xfefefefefefefefe&#41;;
           g |= p & &#40;g <<  9&#41;;
           p &=     &#40;p <<  9&#41;;
           g |= p & &#40;g << 18&#41;;
           p &=     &#40;p << 18&#41;;
    return g |= p & &#40;g << 36&#41;;
&#125;

BitBoard FillUpRightOccluded&#40;BitBoard g, BitBoard p&#41;
&#123;
           p &= C64&#40;0x7f7f7f7f7f7f7f7f&#41;;
           g |= p & &#40;g <<  7&#41;;
           p &=     &#40;p <<  7&#41;;
           g |= p & &#40;g << 14&#41;;
           p &=     &#40;p << 14&#41;;
    return g |= p & &#40;g << 28&#41;;
&#125;

BitBoard FillDownLeftOccluded&#40;BitBoard g, BitBoard p&#41;
&#123;
           p &= C64&#40;0xfefefefefefefefe&#41;;
           g |= p & &#40;g >>  7&#41;;
           p &=     &#40;p >>  7&#41;;
           g |= p & &#40;g >> 14&#41;;
           p &=     &#40;p >> 14&#41;;
    return g |= p & &#40;g >> 28&#41;;
&#125;

BitBoard FillDownRightOccluded&#40;BitBoard g, BitBoard p&#41;
&#123;
           p &= C64&#40;0x7f7f7f7f7f7f7f7f&#41;;
           g |= p & &#40;g >>  9&#41;;
           p &=     &#40;p >>  9&#41;;
           g |= p & &#40;g >> 18&#41;;
           p &=     &#40;p >> 18&#41;;
    return g |= p & &#40;g >> 36&#41;;
&#125;


/*******************************************************************/

/**
Get a bitboard with all positions set to 1 which can be attacked 
from a bishop, rook or queen on the square moving in the direction.
*/
Bitboard Board&#58;&#58;direction_attacks&#40; byte square, byte dir ) const
&#123;
    Bitboard seed = Bitboard&#58;&#58;set_one_bit&#40; square );
    Bitboard free = ~&#40;wpieces_ | bpieces_);

    // 4 3 2
    // 5 0 1
    // 6 7 8
    switch ( dir )
    &#123;
      case 1&#58;
        return ShiftRight&#40; FillRightOccluded&#40; seed, free ) );
      case 5&#58;
        return ShiftLeft&#40; FillLeftOccluded&#40; seed, free ) );
      case 7&#58;
        return ShiftDown&#40; FillDownOccluded&#40; seed, free ) );
      case 3&#58;
        return ShiftUp&#40; FillUpOccluded&#40; seed, free ) );
      case 8&#58;
        return ShiftDownRight&#40; FillDownRightOccluded&#40; seed, free ) );
      case 4&#58;
        return ShiftUpLeft&#40; FillUpLeftOccluded&#40; seed, free ) );
      case 2&#58;
        return ShiftUpRight&#40; FillUpRightOccluded&#40; seed, free ) );
      case 6&#58;
        return ShiftDownLeft&#40; FillDownLeftOccluded&#40; seed, free ) );
      default&#58;
        return 0;
    &#125;
&#125;


/*******************************************************************/

/**
Get a bitboard with all positions set to 1 which can be attacked 
from a rook or queen on the square.
*/
Bitboard Board&#58;&#58;orthogonal_attacks&#40; byte square ) const
&#123;
    Bitboard seed = Bitboard&#58;&#58;set_one_bit&#40; square );
    Bitboard free = ~&#40;wpieces_ | bpieces_);
    return ShiftRight&#40; FillRightOccluded&#40; seed, free ) )
         | ShiftLeft&#40; FillLeftOccluded&#40; seed, free ) )
         | ShiftUp&#40; FillUpOccluded&#40; seed, free ) )
         | ShiftDown&#40; FillDownOccluded&#40; seed, free ) );
&#125;


/*******************************************************************/

/**
Get a bitboard with all positions set to 1 which can be attacked 
from a bishop or queen on the square.
*/
Bitboard Board&#58;&#58;diagonal_attacks&#40; byte square ) const
&#123;
    Bitboard seed = Bitboard&#58;&#58;set_one_bit&#40; square );
    Bitboard free = ~&#40;wpieces_ | bpieces_);
    return ShiftUpRight&#40; FillUpRightOccluded&#40; seed, free ) )
         | ShiftUpLeft&#40; FillUpLeftOccluded&#40; seed, free ) )
         | ShiftDownLeft&#40; FillDownLeftOccluded&#40; seed, free ) )
         | ShiftDownRight&#40; FillDownRightOccluded&#40; seed, free ) );
&#125;


/*******************************************************************/
/*
The original from Steffan Westcott &#40;with a1=0, b1, h8=63-mapping&#41;
http&#58;//www.stmintz.com/ccc/index.php?id=261956&#58;

Peter,

Let me provide a summary &#58;

The general discussion here is about generation of attack/move bitboards for
sliding pieces by direct calculation. Each routine considers moves/attacks in
one direction only. Each routine considers all pieces on the board ie. generates
data for all moving pieces simultaneously. The routines do their work by direct
manipulation of the basic bitboards. No lookup tables or rotated bitboards are
used. All of these properties may make this approach attractive for some
architectures, with careful engine design. Mention has been made of the imminent
64-bit Hammer core CPU by AMD, which may benefit bitboard algorithms.

Two methods have been examined. The conceptually easier method has been dubbed
here as a 'flood fill' &#40;a term borrowed from computer graphics&#41;, where the fill
proceeds in one direction only. A simple example, showing an upward flood fill &#58;


BitBoard ShiftUp&#40;BitBoard b&#41;
&#123;
    return b << 8;
&#125;


BitBoard FillUpOccluded_flood&#40;BitBoard g, BitBoard p&#41;
&#123;
    for&#40;int n = 0; n < 7; n++)
        g |= ShiftUp&#40;g&#41; & p;
    return g;
&#125;


BitBoard RookAttacksUp&#40;BitBoard rooks, BitBoard empty_squares&#41;
&#123;
    return ShiftUp&#40;FillUpOccluded_flood&#40;rooks, empty_squares&#41;);
&#125;


BitBoard RookMovesUp&#40;BitBoard friendly_rooks, BitBoard friendly_pieces,
                     BitBoard empty_squares&#41;
&#123;
    return RookAttacksUp&#40;friendly_rooks, empty_squares&#41; & ~friendly_pieces;
&#125;


The other method is inspired by parallel prefix circuits, a hardware design for
fast carry propagation in adders. The Kogge-Stone method lends itself to
convenient implementation in software, here used to propagate sliding chess
pieces rather than carry bits.

On closer inspection of Russell's code, I spotted some errors, alas. So, here is
the correct version, in full &#58;

// Uses this ordering for bits <-> squares
//
// 56 57 58 59 60 61 62 63
// 48 49 50 51 52 53 54 55
// 40 41 42 43 44 45 46 47
// 32 33 34 35 36 37 38 39
// 24 25 26 27 28 29 30 31
// 16 17 18 19 20 21 22 23
//  8  9 10 11 12 13 14 15
//  0  1  2  3  4  5  6  7

typedef unsigned __int64 BitBoard;

///////////////////////////////////////////////////////////////////////////

BitBoard ShiftRight    &#40;BitBoard b&#41; &#123; return &#40;b<<1&#41; & 0xfefefefefefefefe; &#125;
BitBoard ShiftLeft     &#40;BitBoard b&#41; &#123; return &#40;b>>1&#41; & 0x7f7f7f7f7f7f7f7f; &#125;
BitBoard ShiftUp       &#40;BitBoard b&#41; &#123; return  b<<8; &#125;
BitBoard ShiftDown     &#40;BitBoard b&#41; &#123; return  b>>8; &#125;
BitBoard ShiftUpRight  &#40;BitBoard b&#41; &#123; return &#40;b<<9&#41; & 0xfefefefefefefefe; &#125;
BitBoard ShiftUpLeft   &#40;BitBoard b&#41; &#123; return &#40;b<<7&#41; & 0x7f7f7f7f7f7f7f7f; &#125;
BitBoard ShiftDownRight&#40;BitBoard b&#41; &#123; return &#40;b>>7&#41; & 0xfefefefefefefefe; &#125;
BitBoard ShiftDownLeft &#40;BitBoard b&#41; &#123; return &#40;b>>9&#41; & 0x7f7f7f7f7f7f7f7f; &#125;

///////////////////////////////////////////////////////////////////////////

BitBoard FillRightOccluded&#40;BitBoard g, BitBoard p&#41;
&#123;
           p &= 0xfefefefefefefefe;
           g |= p & &#40;g << 1&#41;;
           p &=     &#40;p << 1&#41;;
           g |= p & &#40;g << 2&#41;;
           p &=     &#40;p << 2&#41;;
    return g |= p & &#40;g << 4&#41;;
&#125;

BitBoard FillLeftOccluded&#40;BitBoard g, BitBoard p&#41;
&#123;
           p &= 0x7f7f7f7f7f7f7f7f;
           g |= p & &#40;g >> 1&#41;;
           p &=     &#40;p >> 1&#41;;
           g |= p & &#40;g >> 2&#41;;
           p &=     &#40;p >> 2&#41;;
    return g |= p & &#40;g >> 4&#41;;
&#125;

BitBoard FillUpOccluded&#40;BitBoard g, BitBoard p&#41;
&#123;
           g |= p & &#40;g <<  8&#41;;
           p &=     &#40;p <<  8&#41;;
           g |= p & &#40;g << 16&#41;;
           p &=     &#40;p << 16&#41;;
    return g |= p & &#40;g << 32&#41;;
&#125;

BitBoard FillDownOccluded&#40;BitBoard g, BitBoard p&#41;
&#123;
           g |= p & &#40;g >>  8&#41;;
           p &=     &#40;p >>  8&#41;;
           g |= p & &#40;g >> 16&#41;;
           p &=     &#40;p >> 16&#41;;
    return g |= p & &#40;g >> 32&#41;;
&#125;

BitBoard FillUpRightOccluded&#40;BitBoard g, BitBoard p&#41;
&#123;
           p &= 0xfefefefefefefefe;
           g |= p & &#40;g <<  9&#41;;
           p &=     &#40;p <<  9&#41;;
           g |= p & &#40;g << 18&#41;;
           p &=     &#40;p << 18&#41;;
    return g |= p & &#40;g << 36&#41;;
&#125;

BitBoard FillUpLeftOccluded&#40;BitBoard g, BitBoard p&#41;
&#123;
           p &= 0x7f7f7f7f7f7f7f7f;
           g |= p & &#40;g <<  7&#41;;
           p &=     &#40;p <<  7&#41;;
           g |= p & &#40;g << 14&#41;;
           p &=     &#40;p << 14&#41;;
    return g |= p & &#40;g << 28&#41;;
&#125;

BitBoard FillDownRightOccluded&#40;BitBoard g, BitBoard p&#41;
&#123;
           p &= 0xfefefefefefefefe;
           g |= p & &#40;g >>  7&#41;;
           p &=     &#40;p >>  7&#41;;
           g |= p & &#40;g >> 14&#41;;
           p &=     &#40;p >> 14&#41;;
    return g |= p & &#40;g >> 28&#41;;
&#125;

BitBoard FillDownLeftOccluded&#40;BitBoard g, BitBoard p&#41;
&#123;
           p &= 0x7f7f7f7f7f7f7f7f;
           g |= p & &#40;g >>  9&#41;;
           p &=     &#40;p >>  9&#41;;
           g |= p & &#40;g >> 18&#41;;
           p &=     &#40;p >> 18&#41;;
    return g |= p & &#40;g >> 36&#41;;
&#125;


In the above, g = moving piece&#40;s&#41;;  p = empty squares

I posted here a long article on the definition of parallel prefix problems, and
how they could be applied to chess programming. Also, in other threads I've
illustrated algorithms featuring direct calculation with bitboard terms, such as
all shortest path finding. If you want them, I have those posts on file, but
none of the thread context they appeared in.

Feel free to use this material.

Cheers,
Steffan


--------------------------------------------------------------------
And another one with some mathematical background
http&#58;//www.stmintz.com/ccc/index.php?id=252289&#58;

Gerd,

A faster routine to find all possible target squares for upward rook
moves/attacks might look like this &#58;


---- CUT HERE ----

BitBoard FillUpOccluded&#40;BitBoard g, BitBoard p&#41;
&#123;
           g |= p & &#40;g <<  8&#41;;
           p &=     &#40;p <<  8&#41;;
           g |= p & &#40;g << 16&#41;;
           p &=     &#40;p << 16&#41;;
    return g |= p & &#40;g << 32&#41;;
&#125;


BitBoard RookAttacksUp&#40;BitBoard rooks, BitBoard empty_squares&#41;
&#123;
    return ShiftUp&#40;FillUpOccluded&#40;rooks, empty_squares&#41;);
&#125;

---- CUT HERE ----


RookAttacksUp&#40;) is doing the same work as the part of your routine
getRookAttacks&#40;) which deals with upward rook attacks, but with less operations.

The routine FillUpOccluded&#40;) smears the set bits of bitboard g upwards, but only
along set bits of p; a reset bit in p is enough to halt a smear. RookAttacksUp&#40;)
uses this routine to find all squares rooks may occupy by either staying still
or moving up along empty squares &#40;no captures allowed&#41;. Shifting this last
result up by 1 square gives the squares all rooks can attack by moving upwards
&#40;which _does_ include captures&#41;.

A parallel prefix problem is of the sort &#58;

   Given the terms x1, x2, x3, ... , xN and an associative operator #
   find the values q1 = x1
                   q2 = x1 # x2
                   q3 = x1 # x2 # x3
                   .
                   .
                   .
                   qN = x1 # x2 # x3 # ... # xN

Associative expressions can be bracketed any way you like, the result is the
same. To see why this is interesting for chess programming, let's define x1, x2,
... and # to be

    xI = < gI, pI >     &#40;a two element tuple&#41;
         where gI = square aI has a rook on it
         and   pI = square aI is empty
         for all I = 1, 2, 3, ... , 8

and xI # xJ = < gI, pI >  #  < gJ, pJ >
            = < (&#40;gI && pJ&#41; || gJ&#41;,  &#40;pI && pJ&#41; >

All this algebra looks very scary at first, so here's an example &#58;

  q2 = x1 # x2 = < rook_on_a1, a1_is_empty > # < rook_on_a2, a2_is_empty >
               = < (&#40;rook_on_a1 && a2_is_empty&#41; || rook_on_a2&#41;,
                   &#40;a1_is_empty && a2_is_empty&#41; >

The first tuple of q2 tells us if a rook is on a2 or can move up to a2 along
empty squares.

The second tuple of q2 tells us if a rook could move up freely through a1-a2 ie.
a1-a2 are empty.

In general,

  xI # x&#40;I+1&#41; # ... # xJ =
    < a_rook_somewhere_on_aI_to_aJ_is_either_on_aJ_or_can_move_up_to_aJ,
      all_squares_aI_to_aJ_are_empty >

and so

  qJ = < a_rook_somewhere_in_file_a_is_either_on_aJ_or_can_move_up_to_aJ,
         all_squares_a1_to_aJ_are_empty >

The tuples g and p are known as the "generator" and "propagator" terms in the
literature of fast carry propagation circuits. But we are not dealing with carry
bits in a carry propagate adder! Here, we are generating and propagating upward
rook attacks along a file of a chessboard.

Why all this theory? Well, prefix computation is a heavily researched area,
researched by many folk smarter than me &#58;) Its of interest because it has many
applications, such as VLSI design, pattern matching, and others. There are many
different ways of going about it, with different implementation characteristics.

The method chosen in FillUpOccluded&#40;) is based on a Kogge-Stone parallel prefix
network, because it can be implemented very easily in software. The diagram
below &#40;trust me, it really _is_ supposed to look like that&#41; is an illustration
of how it works. The corresponding lines of program code are shown on the right.
The inputs are fed into the network at the top, pass along the connecting lines,
are combined by the # operator at various points, and the outputs appear at the
bottom.


x1 x2 x3 x4 x5 x6 x7 x8         Input &#58; g, p
|  |  |  |  |  |  |  |
V  V  V  V  V  V  V  V
|  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |
|\ |\ |\ |\ |\ |\ |\ |
| \| \| \| \| \| \| \|
|  #  #  #  #  #  #  #          g |= p & &#40;g <<  8&#41;;
|  |  |  |  |  |  |  |          p &=     &#40;p <<  8&#41;;
|\ |\ |\ |\ |\ |\ |  |
| \&#58; \&#58; \&#58; \&#58; \&#58; \&#58;  |
|  \  \  \  \  \  \  |
|  &#58;\ &#58;\ &#58;\ &#58;\ &#58;\ &#58;\ |
|  | \| \| \| \| \| \|
|  |  #  #  #  #  #  #          g |= p & &#40;g << 16&#41;;
|  |  |  |  |  |  |  |          p &=     &#40;p << 16&#41;;
|\ |\ |\ |\ |  |  |  |
| \&#58; \&#58; \&#58; \&#58;  |  |  |
|  \  \  \  \  |  |  |
|  &#58;\ &#58;\ &#58;\ &#58;\ |  |  |
|  | \&#58; \&#58; \&#58; \&#58;  |  |
|  |  \  \  \  \  |  |
|  |  &#58;\ &#58;\ &#58;\ &#58;\ |  |
|  |  | \&#58; \&#58; \&#58; \&#58;  |
|  |  |  \  \  \  \  |
|  |  |  ;\ ;\ &#58;\ &#58;\ |
|  |  |  | \| \| \| \|
|  |  |  |  #  #  #  #          g |= p & &#40;g << 32&#41;;
|  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |
V  V  V  V  V  V  V  V
q1 q2 q3 q4 q5 q6 q7 q8         Output &#58; g


To convince yourself this works, select any output qI and trace upwards from the
bottom of the diagram. You'll see it leads back to x1, x2, ... , xI, so qI is
formed by some computation of x1 # x2 # ... # xI.

&#91;Implementor's note &#58; The 2 program lines that assign to variable p are not
strictly correct. By the end of the routine, p1 and p2 have been trashed
&#40;reset&#41;. However, they are trashed after they can affect the correctness of the
routine result.&#93;


Cheers,
Steffan
*/
/*******************************************************************/

#endif // #if USE_KOGGE_STONE_BITBOARDS&#40;)

Harald
Posts: 265
Joined: Thu Mar 09, 2006 12:07 am

Re: BitBoard Tests (Naive Shift)

Post by Harald » Sat Aug 25, 2007 7:00 am

bb_attacks_naive_shift.cpp:

Code: Select all

/*******************************************************************/
/*
The naive shift bitboard attacks 
as part of the board structure. 
This is a simple method of shifting a bit through the bitboard.
This method uses a do while loop for generating the results. 

&#40;c&#41; 2006 Harald Lüßen
*/
/*******************************************************************/


#include "bb_ifdef.h"
#include "bb_basics.h"
#include "bb_bitboard.h"
#include "bb_board.h"
#include "bb_main.h"


#if USE_NAIVE_SHIFT_BITBOARDS&#40;)

/*******************************************************************/

/*
    directions and shifts
    +-----+-----+-----+
    |<<= 9|<<= 8|<<= 7|
    +-----+-----+-----+
    |<<= 1|     |>>= 1|
    +-----+-----+-----+
    |>>= 7|>>= 8|>>= 9|
    +-----+-----+-----+

    We use this mapping of the normal board squares to bitboard bits
    +-------------------------+
    | 63 62 61 60 59 58 57 56 | 8
    | 55 54 53 52 51 50 49 48 | 7
    | 47 46 45 44 43 42 41 40 | 6
    | 39 38 37 36 35 35 33 32 | 5
    | 31 30 29 28 27 26 25 24 | 4
    | 23 22 21 20 19 18 17 16 | 3
    | 15 14 13 12 11 10  9  8 | 2
    |  7  6  5  4  3  2  1  0 | 1
    +-------------------------+
       a  b  c  d  e  f  g  h
*/

/*******************************************************************/

/**
Get a bitboard with all positions set to 1 which can be attacked 
from a bishop, rook or queen on the square moving in the direction.
*/
Bitboard Board&#58;&#58;direction_attacks&#40; byte square, byte dir ) const
&#123;
    Bitboard seed = Bitboard&#58;&#58;set_one_bit&#40; square );
    Bitboard free = ~&#40;wpieces_ | bpieces_);
    Bitboard result;

    // 4 3 2
    // 5 0 1
    // 6 7 8
    switch ( dir )
    &#123;
      case 1&#58;
        free &= C64&#40;0x7f7f7f7f7f7f7f7f&#41;;
        do
        &#123;
            seed >>= 1;
            result |= seed;
        &#125; while ( seed & free );
        result &= C64&#40;0x7f7f7f7f7f7f7f7f&#41;;
        break;
      case 5&#58;
        free &= C64&#40;0xfefefefefefefefe&#41;;
        do
        &#123;
            seed <<= 1;
            result |= seed;
        &#125; while ( seed & free );
        result &= C64&#40;0xfefefefefefefefe&#41;;
        break;
      case 7&#58;
        do
        &#123;
            seed >>= 8;
            result |= seed;
        &#125; while ( seed & free );
        break;
      case 3&#58;
        do
        &#123;
            seed <<= 8;
            result |= seed;
        &#125; while ( seed & free );
        break;
      case 8&#58;
        free &= C64&#40;0x7f7f7f7f7f7f7f7f&#41;;
        do
        &#123;
            seed >>= 9;
            result |= seed;
        &#125; while ( seed & free );
        result &= C64&#40;0x7f7f7f7f7f7f7f7f&#41;;
        break;
      case 4&#58;
        free &= C64&#40;0xfefefefefefefefe&#41;;
        do
        &#123;
            seed <<= 9;
            result |= seed;
        &#125; while ( seed & free );
        result &= C64&#40;0xfefefefefefefefe&#41;;
        break;
      case 2&#58;
        free &= C64&#40;0x7f7f7f7f7f7f7f7f&#41;;
        do
        &#123;
            seed <<= 7;
            result |= seed;
        &#125; while ( seed & free );
        result &= C64&#40;0x7f7f7f7f7f7f7f7f&#41;;
        break;
      case 6&#58;
        free &= C64&#40;0xfefefefefefefefe&#41;;
        do
        &#123;
            seed >>= 7;
            result |= seed;
        &#125; while ( seed & free );
        result &= C64&#40;0xfefefefefefefefe&#41;;
        break;
      default&#58;
        result = 0;
        break;
    &#125;
    return result;
&#125;


/*******************************************************************/

/**
Get a bitboard with all positions set to 1 which can be attacked 
from a rook or queen on the square.
*/
Bitboard Board&#58;&#58;orthogonal_attacks&#40; byte square ) const
&#123;
    return direction_attacks&#40; square, 1 )
         | direction_attacks&#40; square, 3 )
         | direction_attacks&#40; square, 5 )
         | direction_attacks&#40; square, 7 );
&#125;


/*******************************************************************/

/**
Get a bitboard with all positions set to 1 which can be attacked 
from a bishop or queen on the square.
*/
Bitboard Board&#58;&#58;diagonal_attacks&#40; byte square ) const
&#123;
    return direction_attacks&#40; square, 2 )
         | direction_attacks&#40; square, 4 )
         | direction_attacks&#40; square, 6 )
         | direction_attacks&#40; square, 8 );
&#125;


/*******************************************************************/

#endif // #if USE_NAIVE_SHIFT_BITBOARDS&#40;)

Harald
Posts: 265
Joined: Thu Mar 09, 2006 12:07 am

Re: BitBoard Tests (Simple Shift)

Post by Harald » Sat Aug 25, 2007 7:01 am

bb_attacks_simple_shift.cpp:

Code: Select all

/*******************************************************************/
/*
The simple shift bitboard attacks 
as part of the board structure. 
This is a simple method of shifting a bit through the bitboard.
I used the Kogge-Stone infrastructure. No loops, if, while.

&#40;c&#41; 2006 Harald Lüßen
*/
/*******************************************************************/


#include "bb_ifdef.h"
#include "bb_basics.h"
#include "bb_bitboard.h"
#include "bb_board.h"
#include "bb_main.h"


#if USE_SIMPLE_SHIFT_BITBOARDS&#40;)

/*******************************************************************/

/*
    directions and shifts
    +-----+-----+-----+
    |<<= 9|<<= 8|<<= 7|
    +-----+-----+-----+
    |<<= 1|     |>>= 1|
    +-----+-----+-----+
    |>>= 7|>>= 8|>>= 9|
    +-----+-----+-----+

    We use this mapping of the normal board squares to bitboard bits
    +-------------------------+
    | 63 62 61 60 59 58 57 56 | 8
    | 55 54 53 52 51 50 49 48 | 7
    | 47 46 45 44 43 42 41 40 | 6
    | 39 38 37 36 35 35 33 32 | 5
    | 31 30 29 28 27 26 25 24 | 4
    | 23 22 21 20 19 18 17 16 | 3
    | 15 14 13 12 11 10  9  8 | 2
    |  7  6  5  4  3  2  1  0 | 1
    +-------------------------+
       a  b  c  d  e  f  g  h
*/

/*******************************************************************/

typedef unsigned __int64 BitBoard;

///////////////////////////////////////////////////////////////////////////

BitBoard ShiftUp       &#40;BitBoard b&#41; &#123; return  b<<8; &#125;
BitBoard ShiftDown     &#40;BitBoard b&#41; &#123; return  b>>8; &#125;
BitBoard ShiftLeft     &#40;BitBoard b&#41; &#123; return &#40;b<<1&#41; & C64&#40;0xfefefefefefefefe&#41;; &#125;
BitBoard ShiftRight    &#40;BitBoard b&#41; &#123; return &#40;b>>1&#41; & C64&#40;0x7f7f7f7f7f7f7f7f&#41;; &#125;
BitBoard ShiftUpLeft   &#40;BitBoard b&#41; &#123; return &#40;b<<9&#41; & C64&#40;0xfefefefefefefefe&#41;; &#125;
BitBoard ShiftUpRight  &#40;BitBoard b&#41; &#123; return &#40;b<<7&#41; & C64&#40;0x7f7f7f7f7f7f7f7f&#41;; &#125;
BitBoard ShiftDownLeft &#40;BitBoard b&#41; &#123; return &#40;b>>7&#41; & C64&#40;0xfefefefefefefefe&#41;; &#125;
BitBoard ShiftDownRight&#40;BitBoard b&#41; &#123; return &#40;b>>9&#41; & C64&#40;0x7f7f7f7f7f7f7f7f&#41;; &#125;

///////////////////////////////////////////////////////////////////////////

/**
The routine FillUpOccluded&#40;) smears the set bits of bitboard g upwards, but only
along set bits of p; a reset bit in p is enough to halt a smear. RookAttacksUp&#40;)
uses this routine to find all squares rooks may occupy by either staying still
or moving up along empty squares &#40;no captures allowed&#41;. Shifting this last
result up by 1 square gives the squares all rooks can attack by moving upwards
&#40;which _does_ include captures&#41;.
*/
BitBoard FillUpOccluded&#40;BitBoard g, BitBoard p&#41;
&#123;
           g |= p & &#40;g <<  8&#41;;
           g |= p & &#40;g <<  8&#41;;
           g |= p & &#40;g <<  8&#41;;
           g |= p & &#40;g <<  8&#41;;
           g |= p & &#40;g <<  8&#41;;
           g |= p & &#40;g <<  8&#41;;
    return g |= p & &#40;g <<  8&#41;;
&#125;

BitBoard FillDownOccluded&#40;BitBoard g, BitBoard p&#41;
&#123;
           g |= p & &#40;g >>  8&#41;;
           g |= p & &#40;g >>  8&#41;;
           g |= p & &#40;g >>  8&#41;;
           g |= p & &#40;g >>  8&#41;;
           g |= p & &#40;g >>  8&#41;;
           g |= p & &#40;g >>  8&#41;;
    return g |= p & &#40;g >>  8&#41;;
&#125;

BitBoard FillLeftOccluded&#40;BitBoard g, BitBoard p&#41;
&#123;
           p &= C64&#40;0xfefefefefefefefe&#41;;
           g |= p & &#40;g << 1&#41;;
           g |= p & &#40;g << 1&#41;;
           g |= p & &#40;g << 1&#41;;
           g |= p & &#40;g << 1&#41;;
           g |= p & &#40;g << 1&#41;;
           g |= p & &#40;g << 1&#41;;
    return g |= p & &#40;g << 1&#41;;
&#125;

BitBoard FillRightOccluded&#40;BitBoard g, BitBoard p&#41;
&#123;
           p &= C64&#40;0x7f7f7f7f7f7f7f7f&#41;;
           g |= p & &#40;g >> 1&#41;;
           g |= p & &#40;g >> 1&#41;;
           g |= p & &#40;g >> 1&#41;;
           g |= p & &#40;g >> 1&#41;;
           g |= p & &#40;g >> 1&#41;;
           g |= p & &#40;g >> 1&#41;;
    return g |= p & &#40;g >> 1&#41;;
&#125;

BitBoard FillUpLeftOccluded&#40;BitBoard g, BitBoard p&#41;
&#123;
           p &= C64&#40;0xfefefefefefefefe&#41;;
           g |= p & &#40;g << 9&#41;;
           g |= p & &#40;g << 9&#41;;
           g |= p & &#40;g << 9&#41;;
           g |= p & &#40;g << 9&#41;;
           g |= p & &#40;g << 9&#41;;
           g |= p & &#40;g << 9&#41;;
    return g |= p & &#40;g << 9&#41;;
&#125;

BitBoard FillUpRightOccluded&#40;BitBoard g, BitBoard p&#41;
&#123;
           p &= C64&#40;0x7f7f7f7f7f7f7f7f&#41;;
           g |= p & &#40;g << 7&#41;;
           g |= p & &#40;g << 7&#41;;
           g |= p & &#40;g << 7&#41;;
           g |= p & &#40;g << 7&#41;;
           g |= p & &#40;g << 7&#41;;
           g |= p & &#40;g << 7&#41;;
    return g |= p & &#40;g << 7&#41;;
&#125;

BitBoard FillDownLeftOccluded&#40;BitBoard g, BitBoard p&#41;
&#123;
           p &= C64&#40;0xfefefefefefefefe&#41;;
           g |= p & &#40;g >> 7&#41;;
           g |= p & &#40;g >> 7&#41;;
           g |= p & &#40;g >> 7&#41;;
           g |= p & &#40;g >> 7&#41;;
           g |= p & &#40;g >> 7&#41;;
           g |= p & &#40;g >> 7&#41;;
    return g |= p & &#40;g >> 7&#41;;
&#125;

BitBoard FillDownRightOccluded&#40;BitBoard g, BitBoard p&#41;
&#123;
           p &= C64&#40;0x7f7f7f7f7f7f7f7f&#41;;
           g |= p & &#40;g >> 9&#41;;
           g |= p & &#40;g >> 9&#41;;
           g |= p & &#40;g >> 9&#41;;
           g |= p & &#40;g >> 9&#41;;
           g |= p & &#40;g >> 9&#41;;
           g |= p & &#40;g >> 9&#41;;
    return g |= p & &#40;g >> 9&#41;;
&#125;


/*******************************************************************/

/**
Get a bitboard with all positions set to 1 which can be attacked 
from a bishop, rook or queen on the square moving in the direction.
*/
Bitboard Board&#58;&#58;direction_attacks&#40; byte square, byte dir ) const
&#123;
    Bitboard seed = Bitboard&#58;&#58;set_one_bit&#40; square );
    Bitboard free = ~&#40;wpieces_ | bpieces_);

    // 4 3 2
    // 5 0 1
    // 6 7 8
    switch ( dir )
    &#123;
      case 1&#58;
        return ShiftRight&#40; FillRightOccluded&#40; seed, free ) );
      case 5&#58;
        return ShiftLeft&#40; FillLeftOccluded&#40; seed, free ) );
      case 7&#58;
        return ShiftDown&#40; FillDownOccluded&#40; seed, free ) );
      case 3&#58;
        return ShiftUp&#40; FillUpOccluded&#40; seed, free ) );
      case 8&#58;
        return ShiftDownRight&#40; FillDownRightOccluded&#40; seed, free ) );
      case 4&#58;
        return ShiftUpLeft&#40; FillUpLeftOccluded&#40; seed, free ) );
      case 2&#58;
        return ShiftUpRight&#40; FillUpRightOccluded&#40; seed, free ) );
      case 6&#58;
        return ShiftDownLeft&#40; FillDownLeftOccluded&#40; seed, free ) );
      default&#58;
        return 0;
    &#125;
&#125;


/*******************************************************************/

/**
Get a bitboard with all positions set to 1 which can be attacked 
from a rook or queen on the square.
*/
Bitboard Board&#58;&#58;orthogonal_attacks&#40; byte square ) const
&#123;
    Bitboard seed = Bitboard&#58;&#58;set_one_bit&#40; square );
    Bitboard free = ~&#40;wpieces_ | bpieces_);
    return ShiftRight&#40; FillRightOccluded&#40; seed, free ) )
         | ShiftLeft&#40; FillLeftOccluded&#40; seed, free ) )
         | ShiftUp&#40; FillUpOccluded&#40; seed, free ) )
         | ShiftDown&#40; FillDownOccluded&#40; seed, free ) );
&#125;


/*******************************************************************/

/**
Get a bitboard with all positions set to 1 which can be attacked 
from a bishop or queen on the square.
*/
Bitboard Board&#58;&#58;diagonal_attacks&#40; byte square ) const
&#123;
    Bitboard seed = Bitboard&#58;&#58;set_one_bit&#40; square );
    Bitboard free = ~&#40;wpieces_ | bpieces_);
    return ShiftUpRight&#40; FillUpRightOccluded&#40; seed, free ) )
         | ShiftUpLeft&#40; FillUpLeftOccluded&#40; seed, free ) )
         | ShiftDownLeft&#40; FillDownLeftOccluded&#40; seed, free ) )
         | ShiftDownRight&#40; FillDownRightOccluded&#40; seed, free ) );
&#125;


/*******************************************************************/

#endif // #if USE_SIMPLE_SHIFT_BITBOARDS&#40;)

Gerd Isenberg
Posts: 2127
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: BitBoard Tests (Kogge Stone)

Post by Gerd Isenberg » Sat Aug 25, 2007 9:58 am

As Bob mentioned, the issue is not only the pure calculation speed but the convenience of temporarily changing the occupancy. On fill-approaches 'for each slider do all directions' to 'for each direction do all sliders' is a good point.

There is not only the immanent parallelism to process multiple sliders in one run - which becomes less efficient the less sliders are available - but also the ability to improve ipc to the max by processing two or up to four directions in parallel, if enough registers are available. With mmx and dump7fill/Kogge-Stone the time to process four directions was only slightly slower than doing one direction only. Same will happen with K10 (and future x64 processors in general) and 128-bit xmm registers.

For instance I do sse2-Kogge-Stone-fills. Quad-bitboard-generator (two registers) for sliders and queen-like king of both sides and dual-bitboard propagator (one register), the empty-set. Together with fill-like attacks of pawns, knights and king I get:

1.) direction wise move-target sets.
2.) taboo set for the king to move.
3.) squares attacked at least once or twice (for a "cheap" setwise pre-see selection)
4.) xray informations, indirect attacks and defences through
own/opposite sliders, able to move on same direction.
5.) pinned pieces of both sides.
6.) discovered checkers.
7.) a set of checking target squares for rook/bishops.
8.) in case of distant check the inbetween set as possible
legal move targets.

Michael Sherwin
Posts: 3041
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: BitBoard Tests (Michael Sherwin)

Post by Michael Sherwin » Sat Aug 25, 2007 5:01 pm

Harald wrote:This test is not perfect. There is a lot that can be discussed.
What Harald did in the very short time that he did it was truely amazing. It is simply beyond my abilities. I know, because, I tried! However, his statement above is very true and strongly applies to his test of my method. All I ask is for it to be honestly "discussed".

Code: Select all

Bitboard rookAttacks&#40; int sq, Bitboard occ ) 
&#123; 
    // The remaining blocking pieces in the +-rays 
    occ &= rookBits&#91;sq&#93;; 

    // Since every square has its set of row values the six row lookups 
    // simply map any blockers to specific bits that when ored together 
    // gives an offset in the bishop attack table. 
    int *rRows = &rookRows&#91;sq&#93;&#91;0&#93;&#91;0&#93;; 
    int index = &#40;rRows +    0&#41;&#91;&#40;occ >>  0&#41; & 0xff&#93;  // row 1 
              | &#40;rRows +  256&#41;&#91;&#40;occ >>  8&#41; & 0xff&#93;  // row 2 
              | &#40;rRows +  512&#41;&#91;&#40;occ >> 16&#41; & 0xff&#93;  // row 3 
              | &#40;rRows +  768&#41;&#91;&#40;occ >> 24&#41; & 0xff&#93;  // row 4 
              | &#40;rRows + 1024&#41;&#91;&#40;occ >> 32&#41; & 0xff&#93;  // row 5 
              | &#40;rRows + 1280&#41;&#91;&#40;occ >> 40&#41; & 0xff&#93;  // row 6 
              | &#40;rRows + 1536&#41;&#91;&#40;occ >> 48&#41; & 0xff&#93;  // row 7 
              | &#40;rRows + 1792&#41;&#91;&#40;occ >> 56&#41; & 0xff&#93;; // row 8 
    return rookAttackTable&#91;index&#93;; 
&#125;
This is 64 bit register friendly code that was tested on a 32 bit machine. Just by changing the indici generation to 32 bit code for each row it looks like to me that ~17 32 bit instructions would be saved per look-up. That has got to be huge! And it is not clear that the register friendly approach was best. Making occ into a union in which each byte is accessible (my original spec.) would make the number of instructions even less.

Code: Select all

    int index = &#40;rRows +    0&#41;&#91;&#40;occ.row1&#93;  // row 1 
              | &#40;rRows +  256&#41;&#91;occ.row2&#93;  
              | &#40;rRows +  512&#41;&#91;occ.row3&#93;   
              | &#40;rRows +  768&#41;&#91;occ.row4&#93;  
              | &#40;rRows + 1024&#41;&#91;occ.row5&#93;   
              | &#40;rRows + 1280&#41;&#91;occ.row6&#93;  
              | &#40;rRows + 1536&#41;&#91;occ.row7&#93;  
              | &#40;rRows + 1792&#41;&#91;occ.row8&#93;;  
Memory look-ups are not as efficient as register operations, however, in this case the memory look-ups would be hard to beat as they can be done in parrallel. So now the savings is at about 25 assembly instructions per look-up and the rest are done in parallel!

Now look at the timings.

Code: Select all

+----------------------------+-----------------------+--------------+-----------+ 
| Name                       | Inventor or Supporter | Table Size   | Test-Time | 
+----------------------------+-----------------------+--------------+-----------+ 
| Rotated Bitboards &#40;naive&#41;  | Robert Hyatt          |   77.2 KByte |  87.78 s  | 
| Rotated Bitboards &#40;aligned&#41;| ?                     |   35.0 KByte |  86.65 s  | 
| Rotated Bitboards &#40;switch&#41; | &#40;Harald Lüßen?)       |   14.9 KByte |  88.91 s  | 
| Rotated Indices            | Alessandro Damiani    |  128.3 KByte |  78.93 s  | 
| Exploding Bitboards        | Harald Lüßen          |    3.5 KByte | 101.79 s  | 
| Magic Mult. &#40;Kinderg.)     | Gerd Isenberg         |    9.7 KByte |  91.87 s  | 
| Magic M. &#40;Kinderg.) 32 bit | Gerd Isenberg         |    9.7 KByte |  81.37 s  | 
| Sherwin Index              | Michael Sherwin       | 1402.4 KByte |  90.03 s  | 
| Pradu Minimize Magic       | Pradyumna Kannan      |  844.0 KByte |  81.42 s  | 
| Pradu Perfect Magic Hash   |  and                  |  627.4 KByte |  82.09 s  | 
| Pradu Big                  | Lasse Hansen          | 2306.0 KByte |  82.33 s  | 
| Kogge-Stone                | Steffan Westcott      |    0.0 KByte |  99.32 s  | 
| Simple Shift               | --                    |    0.0 KByte | 110.25 s  | 
| Naive Shift                | --                    |    0.0 KByte | 111.69 s  | 
+----------------------------+-----------------------+--------------+-----------+ 
Not to pick on Gerd and his fantastic method, however, my 64 bit (32 bit unfriendly) version was faster than Gerd's 64 bit (32 bit unfriendly) version. I believe for the reasons given above that my 32 bit friendly version would gain a lot more!

So all I ask is that, if someone continues these test, is to give the Sherwin index a fair shake!

Thanks to Harald for naming it after me! :D
I hate if statements. Pawns demand if statements. Therefore I hate pawns.

Carey
Posts: 313
Joined: Wed Mar 08, 2006 7:18 pm
Contact:

Re: BitBoard Tests Magic v Non-Rotated 32 Bits v 64 Bits

Post by Carey » Sat Aug 25, 2007 6:30 pm

Something I've been curious about for a while. Since I don't have a 64 bit system to test it on, I figured I'd ask...

What about the "Classic" method. (Called here the "Pitty method".)

You know, the old school kind from before rotated bitboards were developed.

(Somewhat like how Chess 4.x did it, except they were more concerned about updating their database, which was very slow.)

Do the 8 rays, do the FindFirstBit() & FindLastBit() stuff, etc.

The memory is only 8 rays * 64 squares * sizeof(BitBoard) = 4k.

Code: Select all

/*
**  white bishops
*/
pieces = p.WhiteBishops;
while &#40;pieces&#41;
   &#123;
    m.from = firstBit&#40;pieces&#41;;
    pieces &= &#40;pieces - 1&#41;;

    diag_attacks=plus7&#91;m.from&#93;;
    if &#40;blockers=diag_attacks & p.AllPieces&#41;
/* if's not needed if BSF & BSR could return a 'no-bits set' code */
      &#123;
       blocking_square=firstBit&#40;blockers&#41;;
       diag_attacks^=plus7&#91;blocking_square&#93;;
      &#125;
    attacks=diag_attacks;

    diag_attacks=plus9&#91;m.from&#93;;
    if &#40;blockers=diag_attacks & p.AllPieces&#41;
      &#123;
       blocking_square=firstBit&#40;blockers&#41;;
       diag_attacks^=plus9&#91;blocking_square&#93;;
      &#125;
    attacks|=diag_attacks;

    diag_attacks=minus7&#91;m.from&#93;;
    if &#40;blockers=diag_attacks & p.AllPieces&#41;
      &#123;
       blocking_square=lastBit&#40;blockers&#41;;
       diag_attacks^=minus7&#91;blocking_square&#93;;
      &#125;
    attacks|=diag_attacks;

    diag_attacks=minus9&#91;m.from&#93;;
    if &#40;blockers=diag_attacks & p.AllPieces&#41;
      &#123;
       blocking_square=lastBit&#40;blockers&#41;;
       diag_attacks^=minus9&#91;blocking_square&#93;;
      &#125;
    attacks|=diag_attacks;
   &#125;

I figured that with 64 bit systems having fast BSF & BSR instructions, something like this might be practical.

But I don't have a 64 bit system to test it on.

(Note: This code snippet came from a friend. So if you talk about it, please call it the 'Pitty method". Any newbie who's ever tried to figure out how to do rotated bitboards for his first chess program might be able to figure out why it's called the "Pitty method".... And yes, there are two T's in this spelling.)

edit: Minor code typo due to cleanup for posting.

Post Reply