X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fbitboard.cpp;h=c6ee517d4aa8e7b5f7f3dfc0464f814f59f54e39;hp=426a08f3516a1c6415f2a384b8096c0f8d12c24c;hb=b1b0c640462aed199a3665e575f9cb208b8e4687;hpb=025d57855a21822ccb262fed4f5a3f9c14d8e9b2 diff --git a/src/bitboard.cpp b/src/bitboard.cpp index 426a08f3..c6ee517d 100644 --- a/src/bitboard.cpp +++ b/src/bitboard.cpp @@ -22,9 +22,46 @@ #include "bitboard.h" #include "bitcount.h" +// Global bitboards definitions with static storage duration are +// automatically set to zero before enter main(). +Magics RMagics[64]; +Magics BMagics[64]; + +Bitboard SetMaskBB[65]; +Bitboard ClearMaskBB[65]; + +Bitboard SquaresByColorBB[2]; +Bitboard FileBB[8]; +Bitboard RankBB[8]; +Bitboard NeighboringFilesBB[8]; +Bitboard ThisAndNeighboringFilesBB[8]; +Bitboard InFrontBB[2][8]; +Bitboard StepAttacksBB[16][64]; +Bitboard BetweenBB[64][64]; +Bitboard SquaresInFrontMask[2][64]; +Bitboard PassedPawnMask[2][64]; +Bitboard AttackSpanMask[2][64]; + +Bitboard BishopPseudoAttacks[64]; +Bitboard RookPseudoAttacks[64]; +Bitboard QueenPseudoAttacks[64]; + +uint8_t BitCount8Bit[256]; + +namespace { + + CACHE_LINE_ALIGNMENT + + int BSFTable[64]; + + Bitboard RAttacks[0x19000]; + Bitboard BAttacks[0x1480]; + + void init_sliding_attacks(Bitboard attacks[], Magics m[], const Bitboard mult[], Square deltas[]); + #if defined(IS_64BIT) -static const uint64_t DeBruijnMagic = 0x218A392CD3D5DBFULL; +const uint64_t DeBruijnMagic = 0x218A392CD3D5DBFULL; const uint64_t BMult[64] = { 0x0440049104032280ULL, 0x1021023C82008040ULL, 0x0404040082000048ULL, @@ -76,23 +113,9 @@ const uint64_t RMult[64] = { 0x410201CE5C030092ULL }; -const int BShift[64] = { - 58, 59, 59, 59, 59, 59, 59, 58, 59, 59, 59, 59, 59, 59, 59, 59, - 59, 59, 57, 57, 57, 57, 59, 59, 59, 59, 57, 55, 55, 57, 59, 59, - 59, 59, 57, 55, 55, 57, 59, 59, 59, 59, 57, 57, 57, 57, 59, 59, - 59, 59, 59, 59, 59, 59, 59, 59, 58, 59, 59, 59, 59, 59, 59, 58 -}; - -const int RShift[64] = { - 52, 53, 53, 53, 53, 53, 53, 52, 53, 54, 54, 54, 54, 54, 54, 53, - 53, 54, 54, 54, 54, 54, 54, 53, 53, 54, 54, 54, 54, 54, 54, 53, - 53, 54, 54, 54, 54, 54, 54, 53, 53, 54, 54, 54, 54, 54, 54, 53, - 53, 54, 54, 54, 54, 54, 54, 53, 52, 53, 53, 53, 53, 53, 53, 52 -}; - #else // if !defined(IS_64BIT) -static const uint32_t DeBruijnMagic = 0x783A9B23; +const uint32_t DeBruijnMagic = 0x783A9B23; const uint64_t BMult[64] = { 0x54142844C6A22981ULL, 0x710358A6EA25C19EULL, 0x704F746D63A4A8DCULL, @@ -144,67 +167,8 @@ const uint64_t RMult[64] = { 0x5AC08A4735370479ULL, }; -const int BShift[64] = { - 26, 27, 27, 27, 27, 27, 27, 26, 27, 27, 27, 27, 27, 27, 27, 27, - 27, 27, 25, 25, 25, 25, 27, 27, 27, 27, 25, 23, 23, 25, 27, 27, - 27, 27, 25, 23, 23, 25, 27, 27, 27, 27, 25, 25, 25, 25, 27, 27, - 27, 27, 27, 27, 27, 27, 27, 27, 26, 27, 27, 27, 27, 27, 27, 26 -}; - -const int RShift[64] = { - 20, 21, 21, 21, 21, 21, 21, 20, 21, 22, 22, 22, 22, 22, 22, 21, - 21, 22, 22, 22, 22, 22, 22, 21, 21, 22, 22, 22, 22, 22, 22, 21, - 21, 22, 22, 22, 22, 22, 22, 21, 21, 22, 22, 22, 22, 22, 22, 21, - 21, 22, 22, 22, 22, 22, 22, 21, 20, 21, 21, 21, 21, 21, 21, 20 -}; - #endif // defined(IS_64BIT) -// Global bitboards definitions with static storage duration are -// automatically set to zero before enter main(). -Bitboard RMask[64]; -int RAttackIndex[64]; -Bitboard RAttacks[0x19000]; - -Bitboard BMask[64]; -int BAttackIndex[64]; -Bitboard BAttacks[0x1480]; - -Bitboard SetMaskBB[65]; -Bitboard ClearMaskBB[65]; - -Bitboard SquaresByColorBB[2]; -Bitboard FileBB[8]; -Bitboard RankBB[8]; -Bitboard NeighboringFilesBB[8]; -Bitboard ThisAndNeighboringFilesBB[8]; -Bitboard InFrontBB[2][8]; -Bitboard StepAttacksBB[16][64]; -Bitboard BetweenBB[64][64]; -Bitboard SquaresInFrontMask[2][64]; -Bitboard PassedPawnMask[2][64]; -Bitboard AttackSpanMask[2][64]; - -Bitboard BishopPseudoAttacks[64]; -Bitboard RookPseudoAttacks[64]; -Bitboard QueenPseudoAttacks[64]; - -uint8_t BitCount8Bit[256]; - - -namespace { - - CACHE_LINE_ALIGNMENT int BSFTable[64]; - - void init_masks(); - void init_step_attacks(); - void init_pseudo_attacks(); - void init_between_bitboards(); - Bitboard index_to_bitboard(int index, Bitboard mask); - Bitboard sliding_attacks(int sq, Bitboard occupied, int deltas[][2], - int fmin, int fmax, int rmin, int rmax); - void init_sliding_attacks(Bitboard attacks[], int attackIndex[], Bitboard mask[], - const int shift[], const Bitboard mult[], int deltas[][2]); } @@ -292,195 +256,167 @@ Square pop_1st_bit(Bitboard* bb) { void init_bitboards() { - int rookDeltas[4][2] = {{0,1},{0,-1},{1,0},{-1,0}}; - int bishopDeltas[4][2] = {{1,1},{-1,1},{1,-1},{-1,-1}}; + SquaresByColorBB[DARK] = 0xAA55AA55AA55AA55ULL; + SquaresByColorBB[LIGHT] = ~SquaresByColorBB[DARK]; - init_masks(); - init_step_attacks(); - init_sliding_attacks(RAttacks, RAttackIndex, RMask, RShift, RMult, rookDeltas); - init_sliding_attacks(BAttacks, BAttackIndex, BMask, BShift, BMult, bishopDeltas); - init_pseudo_attacks(); - init_between_bitboards(); -} - -namespace { - - // All functions below are used to precompute various bitboards during - // program initialization. Some of the functions may be difficult to - // understand, but they all seem to work correctly, and it should never - // be necessary to touch any of them. + for (Square s = SQ_A1; s <= SQ_H8; s++) + { + SetMaskBB[s] = (1ULL << s); + ClearMaskBB[s] = ~SetMaskBB[s]; + } - void init_masks() { + ClearMaskBB[SQ_NONE] = ~EmptyBoardBB; - SquaresByColorBB[DARK] = 0xAA55AA55AA55AA55ULL; - SquaresByColorBB[LIGHT] = ~SquaresByColorBB[DARK]; + FileBB[FILE_A] = FileABB; + RankBB[RANK_1] = Rank1BB; - FileBB[FILE_A] = FileABB; - RankBB[RANK_1] = Rank1BB; + for (int f = FILE_B; f <= FILE_H; f++) + { + FileBB[f] = FileBB[f - 1] << 1; + RankBB[f] = RankBB[f - 1] << 8; + } - for (int f = FILE_B; f <= FILE_H; f++) - { - FileBB[f] = FileBB[f - 1] << 1; - RankBB[f] = RankBB[f - 1] << 8; - } + for (int f = FILE_A; f <= FILE_H; f++) + { + NeighboringFilesBB[f] = (f > FILE_A ? FileBB[f - 1] : 0) | (f < FILE_H ? FileBB[f + 1] : 0); + ThisAndNeighboringFilesBB[f] = FileBB[f] | NeighboringFilesBB[f]; + } - for (int f = FILE_A; f <= FILE_H; f++) - { - NeighboringFilesBB[f] = (f > FILE_A ? FileBB[f - 1] : 0) | (f < FILE_H ? FileBB[f + 1] : 0); - ThisAndNeighboringFilesBB[f] = FileBB[f] | NeighboringFilesBB[f]; - } + for (int rw = RANK_7, rb = RANK_2; rw >= RANK_1; rw--, rb++) + { + InFrontBB[WHITE][rw] = InFrontBB[WHITE][rw + 1] | RankBB[rw + 1]; + InFrontBB[BLACK][rb] = InFrontBB[BLACK][rb - 1] | RankBB[rb - 1]; + } - for (int rw = RANK_7, rb = RANK_2; rw >= RANK_1; rw--, rb++) - { - InFrontBB[WHITE][rw] = InFrontBB[WHITE][rw + 1] | RankBB[rw + 1]; - InFrontBB[BLACK][rb] = InFrontBB[BLACK][rb - 1] | RankBB[rb - 1]; - } + for (Color c = WHITE; c <= BLACK; c++) + for (Square s = SQ_A1; s <= SQ_H8; s++) + { + SquaresInFrontMask[c][s] = in_front_bb(c, s) & file_bb(s); + PassedPawnMask[c][s] = in_front_bb(c, s) & this_and_neighboring_files_bb(s); + AttackSpanMask[c][s] = in_front_bb(c, s) & neighboring_files_bb(s); + } + + for (Bitboard b = 0; b < 256; b++) + BitCount8Bit[b] = (uint8_t)count_1s(b); + + for (int i = 1; i < 64; i++) + if (!CpuIs64Bit) // Matt Taylor's folding trick for 32 bit systems + { + Bitboard b = 1ULL << i; + b ^= b - 1; + b ^= b >> 32; + BSFTable[uint32_t(b * DeBruijnMagic) >> 26] = i; + } + else + BSFTable[((1ULL << i) * DeBruijnMagic) >> 58] = i; + + int steps[][9] = { + {0}, {7,9,0}, {17,15,10,6,-6,-10,-15,-17,0}, {0}, {0}, {0}, {9,7,-7,-9,8,1,-1,-8,0} + }; + + for (Color c = WHITE; c <= BLACK; c++) + for (Square s = SQ_A1; s <= SQ_H8; s++) + for (PieceType pt = PAWN; pt <= KING; pt++) + for (int k = 0; steps[pt][k]; k++) + { + Square to = s + Square(c == WHITE ? steps[pt][k] : -steps[pt][k]); + + if (square_is_ok(to) && square_distance(s, to) < 3) + set_bit(&StepAttacksBB[make_piece(c, pt)][s], to); + } + + Square RDeltas[] = { DELTA_N, DELTA_E, DELTA_S, DELTA_W }; + Square BDeltas[] = { DELTA_NE, DELTA_SE, DELTA_SW, DELTA_NW }; + + init_sliding_attacks(RAttacks, RMagics, RMult, RDeltas); + init_sliding_attacks(BAttacks, BMagics, BMult, BDeltas); + + for (Square s = SQ_A1; s <= SQ_H8; s++) + { + BishopPseudoAttacks[s] = bishop_attacks_bb(s, EmptyBoardBB); + RookPseudoAttacks[s] = rook_attacks_bb(s, EmptyBoardBB); + QueenPseudoAttacks[s] = queen_attacks_bb(s, EmptyBoardBB); + } - SetMaskBB[SQ_NONE] = EmptyBoardBB; - ClearMaskBB[SQ_NONE] = ~SetMaskBB[SQ_NONE]; + for (Square s1 = SQ_A1; s1 <= SQ_H8; s1++) + for (Square s2 = SQ_A1; s2 <= SQ_H8; s2++) + if (bit_is_set(QueenPseudoAttacks[s1], s2)) + { + int f = file_distance(s1, s2); + int r = rank_distance(s1, s2); - for (Square s = SQ_A1; s <= SQ_H8; s++) - { - SetMaskBB[s] = (1ULL << s); - ClearMaskBB[s] = ~SetMaskBB[s]; - } + Square d = (s2 - s1) / Max(f, r); - for (Color c = WHITE; c <= BLACK; c++) - for (Square s = SQ_A1; s <= SQ_H8; s++) - { - SquaresInFrontMask[c][s] = in_front_bb(c, s) & file_bb(s); - PassedPawnMask[c][s] = in_front_bb(c, s) & this_and_neighboring_files_bb(s); - AttackSpanMask[c][s] = in_front_bb(c, s) & neighboring_files_bb(s); - } + for (Square s3 = s1 + d; s3 != s2; s3 += d) + set_bit(&BetweenBB[s1][s2], s3); + } +} - for (Bitboard b = 0; b < 256; b++) - BitCount8Bit[b] = (uint8_t)count_1s(b); - for (int i = 1; i < 64; i++) - if (!CpuIs64Bit) // Matt Taylor's folding trick for 32 bit systems - { - Bitboard b = 1ULL << i; - b ^= b - 1; - b ^= b >> 32; - BSFTable[uint32_t(b * DeBruijnMagic) >> 26] = i; - } - else - BSFTable[((1ULL << i) * DeBruijnMagic) >> 58] = i; - } +namespace { - void init_step_attacks() { + Bitboard submask(Bitboard mask, int key) { - const int step[][9] = { - {0}, - {7,9,0}, {17,15,10,6,-6,-10,-15,-17,0}, {0}, {0}, {0}, - {9,7,-7,-9,8,1,-1,-8,0}, {0}, {0}, - {-7,-9,0}, {17,15,10,6,-6,-10,-15,-17,0}, {0}, {0}, {0}, - {9,7,-7,-9,8,1,-1,-8,0} - }; + Bitboard subMask = 0; + int bitNum = -1; + // Extract an unique submask out of a mask according to the given key for (Square s = SQ_A1; s <= SQ_H8; s++) - for (Piece pc = WP; pc <= BK; pc++) - for (int k = 0; step[pc][k] != 0; k++) - { - Square to = s + Square(step[pc][k]); - - if (square_is_ok(to) && square_distance(s, to) < 3) - set_bit(&StepAttacksBB[pc][s], to); - } + if (bit_is_set(mask, s) && bit_is_set(key, Square(++bitNum))) + set_bit(&subMask, s); + + return subMask; } - Bitboard sliding_attacks(int sq, Bitboard occupied, int deltas[][2], - int fmin, int fmax, int rmin, int rmax) { - int dx, dy, f, r; - int rk = sq / 8; - int fl = sq % 8; - Bitboard attacks = EmptyBoardBB; + Bitboard sliding_attacks(Square sq, Bitboard occupied, Square deltas[], Bitboard excluded) { + + Bitboard attacks = 0; for (int i = 0; i < 4; i++) { - dx = deltas[i][0]; - dy = deltas[i][1]; - f = fl + dx; - r = rk + dy; + Square s = sq + deltas[i]; - while ( (dx == 0 || (f >= fmin && f <= fmax)) - && (dy == 0 || (r >= rmin && r <= rmax))) + while ( square_is_ok(s) + && square_distance(s, s - deltas[i]) == 1 + && !bit_is_set(excluded, s)) { - attacks |= (1ULL << (f + r * 8)); + set_bit(&attacks, s); - if (occupied & (1ULL << (f + r * 8))) + if (bit_is_set(occupied, s)) break; - f += dx; - r += dy; + s += deltas[i]; } } return attacks; } - Bitboard index_to_bitboard(int index, Bitboard mask) { + void init_sliding_attacks(Bitboard attacks[], Magics m[], const Bitboard mult[], Square deltas[]) { - Bitboard result = EmptyBoardBB; - int sq, cnt = 0; + Bitboard occupancy, index, excluded; + int maxKey, offset = 0; - while (mask) + for (Square s = SQ_A1; s <= SQ_H8; s++) { - sq = pop_1st_bit(&mask); + excluded = ((Rank1BB | Rank8BB) & ~rank_bb(s)) | ((FileABB | FileHBB) & ~file_bb(s)); - if (index & (1 << cnt++)) - result |= (1ULL << sq); - } - return result; - } + m[s].attacks = &attacks[offset]; + m[s].mult = mult[s]; + m[s].mask = sliding_attacks(s, EmptyBoardBB, deltas, excluded); + m[s].shift = (CpuIs64Bit ? 64 : 32) - count_1s(m[s].mask); - void init_sliding_attacks(Bitboard attacks[], int attackIndex[], Bitboard mask[], - const int shift[], const Bitboard mult[], int deltas[][2]) { - Bitboard b, v; - int i, j, index; + maxKey = 1 << count_1s(m[s].mask); - for (i = index = 0; i < 64; i++) - { - attackIndex[i] = index; - mask[i] = sliding_attacks(i, 0, deltas, 1, 6, 1, 6); - j = 1 << ((CpuIs64Bit ? 64 : 32) - shift[i]); - - for (int k = 0; k < j; k++) + for (int key = 0; key < maxKey; key++) { - b = index_to_bitboard(k, mask[i]); - v = CpuIs64Bit ? b * mult[i] : unsigned(b * mult[i] ^ (b >> 32) * (mult[i] >> 32)); - attacks[index + (v >> shift[i])] = sliding_attacks(i, b, deltas, 0, 7, 0, 7); - } - index += j; - } - } + occupancy = submask(m[s].mask, key); - void init_pseudo_attacks() { + index = CpuIs64Bit ? occupancy * mult[s] + : unsigned(occupancy * mult[s] ^ (occupancy >> 32) * (mult[s] >> 32)); - for (Square s = SQ_A1; s <= SQ_H8; s++) - { - BishopPseudoAttacks[s] = bishop_attacks_bb(s, EmptyBoardBB); - RookPseudoAttacks[s] = rook_attacks_bb(s, EmptyBoardBB); - QueenPseudoAttacks[s] = queen_attacks_bb(s, EmptyBoardBB); + m[s].attacks[index >> m[s].shift] = sliding_attacks(s, occupancy, deltas, EmptyBoardBB); + } + offset += maxKey; } } - - void init_between_bitboards() { - - Square s1, s2, s3, d; - int f, r; - - for (s1 = SQ_A1; s1 <= SQ_H8; s1++) - for (s2 = SQ_A1; s2 <= SQ_H8; s2++) - if (bit_is_set(QueenPseudoAttacks[s1], s2)) - { - f = file_distance(s1, s2); - r = rank_distance(s1, s2); - - d = (s2 - s1) / Max(f, r); - - for (s3 = s1 + d; s3 != s2; s3 += d) - set_bit(&(BetweenBB[s1][s2]), s3); - } - } - }