Code: Select all
/*******************************************************************/
/*
The bitboard attacks of Michael Sherwin with union
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_SHERWIN_UNION_BITBOARDS()
/*******************************************************************/
/*
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
*/
/*******************************************************************/
// Make sure this is done right.
#define BIG_ENDIAN() (0)
#define LITTLE_ENDIAN() (1)
#if BIG_ENDIAN() && !LITTLE_ENDIAN()
// Big end first means row 8 is first byte with my square encoding.
struct BBBytes
{
unsigned char row8;
unsigned char row7;
unsigned char row6;
unsigned char row5;
unsigned char row4;
unsigned char row3;
unsigned char row2;
unsigned char row1;
};
#elif LITTLE_ENDIAN() && !BIG_ENDIAN()
// Little end first means row 1 is first byte with my square encoding.
struct BBBytes
{
unsigned char row1;
unsigned char row2;
unsigned char row3;
unsigned char row4;
unsigned char row5;
unsigned char row6;
unsigned char row7;
unsigned char row8;
};
#else
#error big little endian
#endif
union BBUnion
{
Bits64 bb;
BBBytes bbb;
};
/*******************************************************************/
// Bishops
/*
The typical 1-bits of a bishop on d4 are shown below,
with - indicating a don't care bit:
. . . . . . . -
- . . . . . 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:
. . . . . . . -
- . . . . . 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[64];
void initBishopBits()
{
int sq;
for ( sq = 0; sq < 64; ++sq )
{
bishopBits[sq] = 0;
int i;
for ( i = sq - 9; i >= 0 && i % 8 != 7; i -= 9 )
{
bishopBits[sq] |= C64(1) << i;
}
for ( i = sq - 7; i >= 0 && i % 8 != 0; i -= 7 )
{
bishopBits[sq] |= C64(1) << i;
}
for ( i = sq + 9; i < 64 && i % 8 != 0; i += 9 )
{
bishopBits[sq] |= C64(1) << i;
}
for ( i = sq + 7; i < 64 && i % 8 != 7; i += 7 )
{
bishopBits[sq] |= C64(1) << i;
}
bishopBits[sq] &= C64(0x007e7e7e7e7e7e00);
//logf << "bishopBits " << sq << endl;
//logf << bishopBits[sq].txt8lines() << endl;
}
}
// Number of needed bits per square for bishops
const byte squareBitsB[64] =
{
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,
};
/*
The big Table with index-bits for all rows.
The indices are in this order:
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[sq][row2to7][bitsOnRow]
*/
short int bishopRows[64][6][64];
void initBishopRows()
{
int baseIndex = 0;
for ( int bits = 9; bits >= 5; --bits )
{
for ( int sq = 0; sq < 64; ++sq )
{
if ( squareBitsB[sq] != bits )
continue;
Bitboard bb = bishopBits[sq];
bb >>= 9;
int shift = 0;
for ( int row = 0; row < 6; ++row )
{
int p = (bb >> (row * 8)) & 0x3f;
for ( int pattern = 0; pattern < 64; ++pattern )
{
int index = 0;
int s = shift;
for ( int i = 0; i < 6; ++i )
{
if ( p & (1 << i) )
{
index |= ( (pattern & (1 << i)) ? (1 << s) : 0 );
s++;
if ( pattern == 63 )
shift++;
}
}
bishopRows[sq][row][pattern] = baseIndex + index;
//logf << "bishopRows " << sq << " " << row << " " << pattern << " : ";
//logf << bishopRows[sq][row][pattern] << endl;
}
}
baseIndex += (1 << bits);
}
}
}
// From index to attack bits
Bitboard bishopAttackTable[5248];
void initBishopAttacks()
{
int baseIndex = 0;
for ( int bits = 9; bits >= 5; --bits )
{
for ( int sq = 0; sq < 64; ++sq )
{
if ( squareBitsB[sq] != bits )
continue;
Bitboard bb = bishopBits[sq];
for ( int index = 0; index < (1 << bits); ++ index )
{
Bitboard occ = 0;
int i = index;
for ( int rsq = 0; rsq < 64; ++rsq )
{
if ( bb.test_bit( rsq ) )
{
if ( i & 1 )
occ.set_bit( rsq );
i >>= 1;
}
}
Bitboard att = 0;
int j;
for ( j = sq + 9; j < 64 && (j & 7) != 0; j += 9 )
{
att.set_bit( j );
if ( occ.test_bit( j ) )
break;
}
for ( j = sq + 7; j < 64 && (j & 7) != 7; j += 7 )
{
att.set_bit( j );
if ( occ.test_bit( j ) )
break;
}
for ( j = sq - 9; j >= 0 && (j & 7) != 7; j -= 9 )
{
att.set_bit( j );
if ( occ.test_bit( j ) )
break;
}
for ( j = sq - 7; j >= 0 && (j & 7) != 0; j -= 7 )
{
att.set_bit( j );
if ( occ.test_bit( j ) )
break;
}
bishopAttackTable[baseIndex + index] = att;
}
baseIndex += (1 << bits);
}
}
}
/**
The bishop attack bitboard for a square and occupied bitboard
*/
Bitboard bishopAttacks( int sq, Bitboard occ )
{
// The remaining blocking pieces in the X-rays
occ &= bishopBits[sq];
occ >>= 1;
BBUnion occu;
occu.bb = occ;
// 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[sq][0][0];
int index = (bRows + 0)[occu.bbb.row2] // row 2
| (bRows + 64)[occu.bbb.row3] // row 3
| (bRows + 128)[occu.bbb.row4] // row 4
| (bRows + 192)[occu.bbb.row5] // row 5
| (bRows + 256)[occu.bbb.row6] // row 6
| (bRows + 320)[occu.bbb.row7]; // row 7
return bishopAttackTable[index];
}
/*******************************************************************/
// Rooks
/*
The required bit number per square for rooks looks like this:
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[64];
void initRookBits()
{
int sq;
for ( sq = 0; sq < 64; ++sq )
{
rookBits[sq] = 0;
int i;
for ( i = sq - 1; i >= 0 && i % 8 != 7; --i )
{
rookBits[sq] |= C64(1) << i;
}
for ( i = sq - 8; i >= 0; i -= 8 )
{
rookBits[sq] |= C64(1) << i;
}
for ( i = sq + 1; i < 64 && i % 8 != 0; ++i )
{
rookBits[sq] |= C64(1) << i;
}
for ( i = sq + 8; i < 64; i += 8 )
{
rookBits[sq] |= C64(1) << i;
}
if ( (sq & 7) != 7 )
rookBits[sq] &= C64(0x7f7f7f7f7f7f7f7f);
if ( (sq & 7) != 0 )
rookBits[sq] &= C64(0xfefefefefefefefe);
if ( (sq / 8) != 7 )
rookBits[sq] &= C64(0x00ffffffffffffff);
if ( (sq / 8) != 0 )
rookBits[sq] &= C64(0xffffffffffffff00);
//logf << "rookBits " << sq << endl;
//logf << rookBits[sq].txt8lines() << endl;
}
}
// Number of needed bits per square for rooks
const byte squareBitsR[64] =
{
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,
};
/*
The big Table with index-bits for all rows.
The indices are in this order:
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 (0-102400) do not fit in 2 byte short int.
rookRows[sq][row1to8][bitsOnRow]
*/
int rookRows[64][8][256];
void initRookRows()
{
int baseIndex = 0;
for ( int bits = 12; bits >= 10; --bits )
{
for ( int sq = 0; sq < 64; ++sq )
{
if ( squareBitsR[sq] != bits )
continue;
Bitboard bb = rookBits[sq];
int shift = 0;
for ( int row = 0; row < 8; ++row )
{
int p = (bb >> (row * 8)) & 0xff;
for ( int pattern = 0; pattern < 256; ++pattern )
{
int index = 0;
int s = shift;
for ( int i = 0; i < 8; ++i )
{
if ( p & (1 << i) )
{
index |= ( (pattern & (1 << i)) ? (1 << s) : 0 );
s++;
if ( pattern == 255 )
shift++;
}
}
rookRows[sq][row][pattern] = baseIndex + index;
//logf << "rookRows " << sq << " " << row << " " << pattern << " : ";
//logf << rookRows[sq][row][pattern] << endl;
}
}
baseIndex += (1 << bits);
}
}
}
// From index to attack bits
Bitboard rookAttackTable[102400];
void initRookAttacks()
{
int baseIndex = 0;
for ( int bits = 12; bits >= 10; --bits )
{
for ( int sq = 0; sq < 64; ++sq )
{
if ( squareBitsR[sq] != bits )
continue;
Bitboard bb = rookBits[sq];
for ( int index = 0; index < (1 << bits); ++ index )
{
Bitboard occ = 0;
int i = index;
for ( int rsq = 0; rsq < 64; ++rsq )
{
if ( bb.test_bit( rsq ) )
{
if ( i & 1 )
occ.set_bit( rsq );
i >>= 1;
}
}
Bitboard att = 0;
int j;
for ( j = sq + 1; j < 64 && (j & 7) != 0; ++j )
{
att.set_bit( j );
if ( occ.test_bit( j ) )
break;
}
for ( j = sq + 8; j < 64; j += 8 )
{
att.set_bit( j );
if ( occ.test_bit( j ) )
break;
}
for ( j = sq - 1; j >= 0 && (j & 7) != 7; --j )
{
att.set_bit( j );
if ( occ.test_bit( j ) )
break;
}
for ( j = sq - 8; j >= 0; j -= 8 )
{
att.set_bit( j );
if ( occ.test_bit( j ) )
break;
}
rookAttackTable[baseIndex + index] = att;
}
baseIndex += (1 << bits);
}
}
}
/**
The rook attack bitboard for a square and occupied bitboard
*/
Bitboard rookAttacks( int sq, Bitboard occ )
{
// The remaining blocking pieces in the +-rays
occ &= rookBits[sq];
BBUnion occu;
occu.bb = occ;
// 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[sq][0][0];
int index = (rRows + 0)[occu.bbb.row1] // row 1
| (rRows + 256)[occu.bbb.row2] // row 2
| (rRows + 512)[occu.bbb.row3] // row 3
| (rRows + 768)[occu.bbb.row4] // row 4
| (rRows + 1024)[occu.bbb.row5] // row 5
| (rRows + 1280)[occu.bbb.row6] // row 6
| (rRows + 1536)[occu.bbb.row7] // row 7
| (rRows + 1792)[occu.bbb.row8]; // row 8
return rookAttackTable[index];
}
/*******************************************************************/
const Bitboard dirMaskRight[8] =
{
// 0, line_h, line_gh, line_fh, line_eh, line_dh, line_ch, line_bh,
0, C64(0x0101010101010101), C64(0x0303030303030303), C64(0x0707070707070707), C64(0x0f0f0f0f0f0f0f0f),
C64(0x1f1f1f1f1f1f1f1f), C64(0x3f3f3f3f3f3f3f3f), C64(0x7f7f7f7f7f7f7f7f)
};
const Bitboard dirMaskLeft[8] =
{
// line_ag, line_af, line_ae, line_ad, line_ac, line_ab, line_a, 0,
C64(0xfefefefefefefefe), C64(0xfcfcfcfcfcfcfcfc), C64(0xf8f8f8f8f8f8f8f8), C64(0xf0f0f0f0f0f0f0f0),
C64(0xe0e0e0e0e0e0e0e0), C64(0xc0c0c0c0c0c0c0c0), C64(0x8080808080808080), 0
};
const Bitboard dirMaskUp[8] =
{
// row_28, row_38, row_48, row_58, row_68, row_78, row_8, 0,
C64(0xffffffffffffff00), C64(0xffffffffffff0000), C64(0xffffffffff000000), C64(0xffffffff00000000),
C64(0xffffff0000000000), C64(0xffff000000000000), C64(0xff00000000000000), 0
};
const Bitboard dirMaskDown[8] =
{
// 0, row_1, row_12, row_13, row_14, row_15, row_16, row_17,
0, C64(0x00000000000000ff), C64(0x000000000000ffff), C64(0x0000000000ffffff), C64(0x00000000ffffffff),
C64(0x000000ffffffffff), C64(0x0000ffffffffffff), C64(0x00ffffffffffffff)
};
/*******************************************************************/
/*******************************************************************/
/**
Prepare the slider attacks back transformation table.
Put the scattered bits of an sliding attack pattern
back to the original bitboard.
*/
void Board::init_slider_attacks_index()
{
initBishopBits();
initBishopRows();
initBishopAttacks();
initRookBits();
initRookRows();
initRookAttacks();
}
/*******************************************************************/
/**
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::direction_attacks( byte square, byte dir ) const
{
Bitboard result;
Bitboard occ = wpieces_ | bpieces_;
// 4 3 2
// 5 0 1
// 6 7 8
switch ( dir )
{
case 1:
result = rookAttacks( square, occ );
result &= dirMaskRight[square & 7];
break;
case 5:
result = rookAttacks( square, occ );
result &= dirMaskLeft[square & 7];
break;
case 7:
result = rookAttacks( square, occ );
result &= dirMaskDown[square >> 3];
break;
case 3:
result = rookAttacks( square, occ );
result &= dirMaskUp[square >> 3];
break;
case 8:
result = bishopAttacks( square, occ );
result &= dirMaskRight[square & 7];
result &= dirMaskDown[square >> 3];
break;
case 4:
result = bishopAttacks( square, occ );
result &= dirMaskLeft[square & 7];
result &= dirMaskUp[square >> 3];
break;
case 2:
result = bishopAttacks( square, occ );
result &= dirMaskRight[square & 7];
result &= dirMaskUp[square >> 3];
break;
case 6:
result = bishopAttacks( square, occ );
result &= dirMaskLeft[square & 7];
result &= dirMaskDown[square >> 3];
break;
default:
result = 0;
break;
}
return result;
}
/*******************************************************************/
/**
Get a bitboard with all positions set to 1 which can be attacked
from a rook or queen on the square.
*/
Bitboard Board::orthogonal_attacks( byte square ) const
{
Bitboard occ = wpieces_ | bpieces_;
Bitboard result = rookAttacks( square, occ );
return result;
}
/*******************************************************************/
/**
Get a bitboard with all positions set to 1 which can be attacked
from a bishop or queen on the square.
*/
Bitboard Board::diagonal_attacks( byte square ) const
{
Bitboard occ = wpieces_ | bpieces_;
Bitboard result = bishopAttacks( square, occ );
return result;
}
/*******************************************************************/
#endif // #if USE_SHERWIN_UNION_BITBOARDS()
