X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fbitboard.cpp;h=426a08f3516a1c6415f2a384b8096c0f8d12c24c;hp=ecf51cb1f572dfc9ad44d0d8bfcc2c4a0302be58;hb=025d57855a21822ccb262fed4f5a3f9c14d8e9b2;hpb=e8f885145bd487690a8959928c0573f2edfa5785 diff --git a/src/bitboard.cpp b/src/bitboard.cpp index ecf51cb1..426a08f3 100644 --- a/src/bitboard.cpp +++ b/src/bitboard.cpp @@ -24,6 +24,8 @@ #if defined(IS_64BIT) +static const uint64_t DeBruijnMagic = 0x218A392CD3D5DBFULL; + const uint64_t BMult[64] = { 0x0440049104032280ULL, 0x1021023C82008040ULL, 0x0404040082000048ULL, 0x48C4440084048090ULL, 0x2801104026490000ULL, 0x4100880442040800ULL, @@ -90,6 +92,8 @@ const int RShift[64] = { #else // if !defined(IS_64BIT) +static const uint32_t DeBruijnMagic = 0x783A9B23; + const uint64_t BMult[64] = { 0x54142844C6A22981ULL, 0x710358A6EA25C19EULL, 0x704F746D63A4A8DCULL, 0xBFED1A0B80F838C5ULL, 0x90561D5631E62110ULL, 0x2804260376E60944ULL, @@ -156,51 +160,6 @@ const int RShift[64] = { #endif // defined(IS_64BIT) -static const Bitboard DarkSquaresBB = 0xAA55AA55AA55AA55ULL; - -const Bitboard SquaresByColorBB[2] = { DarkSquaresBB, ~DarkSquaresBB }; - -const Bitboard FileBB[8] = { - FileABB, FileBBB, FileCBB, FileDBB, FileEBB, FileFBB, FileGBB, FileHBB -}; - -const Bitboard NeighboringFilesBB[8] = { - FileBBB, FileABB|FileCBB, FileBBB|FileDBB, FileCBB|FileEBB, - FileDBB|FileFBB, FileEBB|FileGBB, FileFBB|FileHBB, FileGBB -}; - -const Bitboard ThisAndNeighboringFilesBB[8] = { - FileABB|FileBBB, FileABB|FileBBB|FileCBB, - FileBBB|FileCBB|FileDBB, FileCBB|FileDBB|FileEBB, - FileDBB|FileEBB|FileFBB, FileEBB|FileFBB|FileGBB, - FileFBB|FileGBB|FileHBB, FileGBB|FileHBB -}; - -const Bitboard RankBB[8] = { - Rank1BB, Rank2BB, Rank3BB, Rank4BB, Rank5BB, Rank6BB, Rank7BB, Rank8BB -}; - -const Bitboard InFrontBB[2][8] = { - { Rank2BB | Rank3BB | Rank4BB | Rank5BB | Rank6BB | Rank7BB | Rank8BB, - Rank3BB | Rank4BB | Rank5BB | Rank6BB | Rank7BB | Rank8BB, - Rank4BB | Rank5BB | Rank6BB | Rank7BB | Rank8BB, - Rank5BB | Rank6BB | Rank7BB | Rank8BB, - Rank6BB | Rank7BB | Rank8BB, - Rank7BB | Rank8BB, - Rank8BB, - EmptyBoardBB - }, - { EmptyBoardBB, - Rank1BB, - Rank2BB | Rank1BB, - Rank3BB | Rank2BB | Rank1BB, - Rank4BB | Rank3BB | Rank2BB | Rank1BB, - Rank5BB | Rank4BB | Rank3BB | Rank2BB | Rank1BB, - Rank6BB | Rank5BB | Rank4BB | Rank3BB | Rank2BB | Rank1BB, - Rank7BB | Rank6BB | Rank5BB | Rank4BB | Rank3BB | Rank2BB | Rank1BB - } -}; - // Global bitboards definitions with static storage duration are // automatically set to zero before enter main(). Bitboard RMask[64]; @@ -214,9 +173,14 @@ Bitboard BAttacks[0x1480]; Bitboard SetMaskBB[65]; Bitboard ClearMaskBB[65]; -Bitboard NonSlidingAttacksBB[16][64]; +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]; @@ -230,12 +194,14 @@ uint8_t BitCount8Bit[256]; namespace { + CACHE_LINE_ALIGNMENT int BSFTable[64]; + void init_masks(); - void init_non_sliding_attacks(); + 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 block, int dirs, int deltas[][2], + 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]); @@ -265,39 +231,22 @@ void print_bitboard(Bitboard b) { #if defined(IS_64BIT) && !defined(USE_BSFQ) -static CACHE_LINE_ALIGNMENT -const int BitTable[64] = { - 0, 1, 2, 7, 3, 13, 8, 19, 4, 25, 14, 28, 9, 34, 20, 40, 5, 17, 26, - 38, 15, 46, 29, 48, 10, 31, 35, 54, 21, 50, 41, 57, 63, 6, 12, 18, 24, 27, - 33, 39, 16, 37, 45, 47, 30, 53, 49, 56, 62, 11, 23, 32, 36, 44, 52, 55, 61, - 22, 43, 51, 60, 42, 59, 58 -}; - Square first_1(Bitboard b) { - return Square(BitTable[((b & -b) * 0x218a392cd3d5dbfULL) >> 58]); + return Square(BSFTable[((b & -b) * DeBruijnMagic) >> 58]); } Square pop_1st_bit(Bitboard* b) { Bitboard bb = *b; *b &= (*b - 1); - return Square(BitTable[((bb & -bb) * 0x218a392cd3d5dbfULL) >> 58]); + return Square(BSFTable[((bb & -bb) * DeBruijnMagic) >> 58]); } #elif !defined(USE_BSFQ) -static CACHE_LINE_ALIGNMENT -const int BitTable[64] = { - 63, 30, 3, 32, 25, 41, 22, 33, 15, 50, 42, 13, 11, 53, 19, 34, 61, 29, 2, - 51, 21, 43, 45, 10, 18, 47, 1, 54, 9, 57, 0, 35, 62, 31, 40, 4, 49, 5, - 52, 26, 60, 6, 23, 44, 46, 27, 56, 16, 7, 39, 48, 24, 59, 14, 12, 55, 38, - 28, 58, 20, 37, 17, 36, 8 -}; - Square first_1(Bitboard b) { - b ^= (b - 1); - uint32_t fold = int(b) ^ int(b >> 32); - return Square(BitTable[(fold * 0x783a9b23) >> 26]); + uint32_t fold = unsigned(b) ^ unsigned(b >> 32); + return Square(BSFTable[(fold * DeBruijnMagic) >> 26]); } // Use type-punning @@ -324,12 +273,12 @@ Square pop_1st_bit(Bitboard* bb) { if (u.dw.l) { - ret = Square(BitTable[((u.dw.l ^ (u.dw.l - 1)) * 0x783a9b23) >> 26]); + ret = Square(BSFTable[((u.dw.l ^ (u.dw.l - 1)) * DeBruijnMagic) >> 26]); u.dw.l &= (u.dw.l - 1); *bb = u.b; return ret; } - ret = Square(BitTable[((~(u.dw.h ^ (u.dw.h - 1))) * 0x783a9b23) >> 26]); + ret = Square(BSFTable[((~(u.dw.h ^ (u.dw.h - 1))) * DeBruijnMagic) >> 26]); u.dw.h &= (u.dw.h - 1); *bb = u.b; return ret; @@ -347,7 +296,7 @@ void init_bitboards() { int bishopDeltas[4][2] = {{1,1},{-1,1},{1,-1},{-1,-1}}; init_masks(); - init_non_sliding_attacks(); + init_step_attacks(); init_sliding_attacks(RAttacks, RAttackIndex, RMask, RShift, RMult, rookDeltas); init_sliding_attacks(BAttacks, BAttackIndex, BMask, BShift, BMult, bishopDeltas); init_pseudo_attacks(); @@ -363,6 +312,30 @@ namespace { void init_masks() { + SquaresByColorBB[DARK] = 0xAA55AA55AA55AA55ULL; + SquaresByColorBB[LIGHT] = ~SquaresByColorBB[DARK]; + + 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_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]; + } + SetMaskBB[SQ_NONE] = EmptyBoardBB; ClearMaskBB[SQ_NONE] = ~SetMaskBB[SQ_NONE]; @@ -382,9 +355,20 @@ namespace { 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; } - void init_non_sliding_attacks() { + void init_step_attacks() { const int step[][9] = { {0}, @@ -401,35 +385,37 @@ namespace { Square to = s + Square(step[pc][k]); if (square_is_ok(to) && square_distance(s, to) < 3) - set_bit(&NonSlidingAttacksBB[pc][s], to); + set_bit(&StepAttacksBB[pc][s], to); } } - Bitboard sliding_attacks(int sq, Bitboard block, int dirs, int deltas[][2], - int fmin=0, int fmax=7, int rmin=0, int rmax=7) { - Bitboard result = 0; + 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; - for (int i = 0; i < dirs; i++) + for (int i = 0; i < 4; i++) { - int dx = deltas[i][0]; - int dy = deltas[i][1]; - int f = fl + dx; - int r = rk + dy; + dx = deltas[i][0]; + dy = deltas[i][1]; + f = fl + dx; + r = rk + dy; while ( (dx == 0 || (f >= fmin && f <= fmax)) && (dy == 0 || (r >= rmin && r <= rmax))) { - result |= (1ULL << (f + r*8)); - if (block & (1ULL << (f + r*8))) + attacks |= (1ULL << (f + r * 8)); + + if (occupied & (1ULL << (f + r * 8))) break; f += dx; r += dy; } } - return result; + return attacks; } Bitboard index_to_bitboard(int index, Bitboard mask) { @@ -449,28 +435,20 @@ namespace { 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; - for (int i = 0, index = 0; i < 64; i++) + for (i = index = 0; i < 64; i++) { attackIndex[i] = index; - mask[i] = sliding_attacks(i, 0, 4, deltas, 1, 6, 1, 6); - -#if defined(IS_64BIT) - int j = (1 << (64 - shift[i])); -#else - int j = (1 << (32 - shift[i])); -#endif + 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++) { -#if defined(IS_64BIT) - Bitboard b = index_to_bitboard(k, mask[i]); - attacks[index + ((b * mult[i]) >> shift[i])] = sliding_attacks(i, b, 4, deltas); -#else - Bitboard b = index_to_bitboard(k, mask[i]); - unsigned v = int(b) * int(mult[i]) ^ int(b >> 32) * int(mult[i] >> 32); - attacks[index + (v >> shift[i])] = sliding_attacks(i, b, 4, deltas); -#endif + 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; } @@ -488,8 +466,7 @@ namespace { void init_between_bitboards() { - Square s1, s2, s3; - SquareDelta d; + Square s1, s2, s3, d; int f, r; for (s1 = SQ_A1; s1 <= SQ_H8; s1++) @@ -499,7 +476,7 @@ namespace { f = file_distance(s1, s2); r = rank_distance(s1, s2); - d = SquareDelta(s2 - s1) / Max(f, r); + d = (s2 - s1) / Max(f, r); for (s3 = s1 + d; s3 != s2; s3 += d) set_bit(&(BetweenBB[s1][s2]), s3);