X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fbitboard.cpp;h=72e208ffc7c3c2a95e15c84e58489768e1df57ff;hp=ba03d66ef85669cfe4d9f3c8ddf3fa19e272d99c;hb=4dded4e72f9b9582db8adc9a478e9eda5841d8c5;hpb=063e2441b17b8260de443b3d580f49b3d65d03c7 diff --git a/src/bitboard.cpp b/src/bitboard.cpp index ba03d66e..72e208ff 100644 --- a/src/bitboard.cpp +++ b/src/bitboard.cpp @@ -1,7 +1,7 @@ /* Stockfish, a UCI chess playing engine derived from Glaurung 2.1 Copyright (C) 2004-2008 Tord Romstad (Glaurung author) - Copyright (C) 2008-2009 Marco Costalba + Copyright (C) 2008-2010 Marco Costalba, Joona Kiiski, Tord Romstad Stockfish is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by @@ -26,7 +26,6 @@ #include "bitboard.h" #include "bitcount.h" -#include "direction.h" #if defined(IS_64BIT) @@ -161,8 +160,58 @@ const int RShift[64] = { 21, 22, 22, 22, 22, 22, 22, 21, 20, 21, 21, 21, 21, 21, 21, 20 }; -#endif +#endif // defined(IS_64BIT) + +const Bitboard LightSquaresBB = 0x55AA55AA55AA55AAULL; +const Bitboard DarkSquaresBB = 0xAA55AA55AA55AA55ULL; + +const Bitboard SquaresByColorBB[2] = { DarkSquaresBB, LightSquaresBB }; + +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 RelativeRankBB[2][8] = { + { Rank1BB, Rank2BB, Rank3BB, Rank4BB, Rank5BB, Rank6BB, Rank7BB, Rank8BB }, + { Rank8BB, Rank7BB, Rank6BB, Rank5BB, Rank4BB, Rank3BB, Rank2BB, Rank1BB } +}; + +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 + } +}; Bitboard RMask[64]; int RAttackIndex[64]; @@ -176,16 +225,19 @@ Bitboard SetMaskBB[65]; Bitboard ClearMaskBB[65]; Bitboard StepAttackBB[16][64]; -Bitboard RayBB[64][8]; Bitboard BetweenBB[64][64]; +Bitboard SquaresInFrontMask[2][64]; Bitboard PassedPawnMask[2][64]; -Bitboard OutpostMask[2][64]; +Bitboard AttackSpanMask[2][64]; Bitboard BishopPseudoAttacks[64]; Bitboard RookPseudoAttacks[64]; Bitboard QueenPseudoAttacks[64]; +uint8_t BitCount8Bit[256]; +int8_t DirectionTable[64][64]; + //// //// Local definitions @@ -193,18 +245,17 @@ Bitboard QueenPseudoAttacks[64]; namespace { + SquareDelta get_direction(Square orig, Square dest); + void init_direction_table(); void init_masks(); - void init_ray_bitboards(); void init_attacks(); void init_between_bitboards(); + void init_pseudo_attacks(); + Bitboard index_to_bitboard(int index, Bitboard mask); Bitboard sliding_attacks(int sq, Bitboard block, int dirs, int deltas[][2], int fmin, int fmax, int rmin, int rmax); - Bitboard index_to_bitboard(int index, Bitboard mask); - void init_sliding_attacks(Bitboard attacks[], - int attackIndex[], Bitboard mask[], - const int shift[2], const Bitboard mult[], - int deltas[][2]); - void init_pseudo_attacks(); + void init_sliding_attacks(Bitboard attacks[], int attackIndex[], Bitboard mask[], + const int shift[], const Bitboard mult[], int deltas[][2]); } @@ -216,11 +267,14 @@ namespace { /// standard output. This is sometimes useful for debugging. void print_bitboard(Bitboard b) { - for(Rank r = RANK_8; r >= RANK_1; r--) { - std::cout << "+---+---+---+---+---+---+---+---+" << std::endl; - for(File f = FILE_A; f <= FILE_H; f++) - std::cout << "| " << (bit_is_set(b, make_square(f, r))? 'X' : ' ') << ' '; - std::cout << "|" << std::endl; + + for (Rank r = RANK_8; r >= RANK_1; r--) + { + std::cout << "+---+---+---+---+---+---+---+---+" << std::endl; + for (File f = FILE_A; f <= FILE_H; f++) + std::cout << "| " << (bit_is_set(b, make_square(f, r))? 'X' : ' ') << ' '; + + std::cout << "|" << std::endl; } std::cout << "+---+---+---+---+---+---+---+---+" << std::endl; } @@ -230,10 +284,12 @@ void print_bitboard(Bitboard b) { /// program initialization. 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}}; + + init_direction_table(); init_masks(); - init_ray_bitboards(); init_attacks(); init_between_bitboards(); init_sliding_attacks(RAttacks, RAttackIndex, RMask, RShift, RMult, rookDeltas); @@ -242,55 +298,85 @@ void init_bitboards() { } +/// first_1() finds the least significant nonzero bit in a nonzero bitboard. /// pop_1st_bit() finds and clears the least significant nonzero bit in a /// nonzero bitboard. -#if defined(IS_64BIT) +#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 pop_1st_bit(Bitboard *b) { - Bitboard bb = *b ^ (*b - 1); - uint32_t fold = int(bb) ^ int(bb >> 32); +Square first_1(Bitboard b) { + return Square(BitTable[((b & -b) * 0x218a392cd3d5dbfULL) >> 58]); +} + +Square pop_1st_bit(Bitboard* b) { + Bitboard bb = *b; *b &= (*b - 1); - return Square(BitTable[(fold * 0x783a9b23) >> 26]); + return Square(BitTable[((bb & -bb) * 0x218a392cd3d5dbfULL) >> 58]); } -#else +#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]); +} // Use type-punning union b_union { Bitboard b; struct { +#if defined (BIGENDIAN) + uint32_t h; + uint32_t l; +#else uint32_t l; uint32_t h; +#endif } dw; }; -// WARNING: Needs -fno-strict-aliasing compiler option -Square pop_1st_bit(Bitboard *bb) { +Square pop_1st_bit(Bitboard* bb) { - b_union u; - uint32_t b; + b_union u; + Square ret; - u.b = *bb; + u.b = *bb; - if (u.dw.l) - { - b = u.dw.l; - *((uint32_t*)bb) = b & (b - 1); - b ^= (b - 1); - } - else - { - b = u.dw.h; - *((uint32_t*)bb+1) = b & (b - 1); // Little endian only? - b = ~(b ^ (b - 1)); - } - return Square(BitTable[(b * 0x783a9b23) >> 26]); + if (u.dw.l) + { + ret = Square(BitTable[((u.dw.l ^ (u.dw.l - 1)) * 0x783a9b23) >> 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]); + u.dw.h &= (u.dw.h - 1); + *bb = u.b; + return ret; } #endif + namespace { // All functions below are used to precompute various bitboards during @@ -298,37 +384,62 @@ namespace { // understand, but they all seem to work correctly, and it should never // be necessary to touch any of them. + SquareDelta get_direction(Square orig, Square dest) { + + const SquareDelta directions[] = { + DELTA_E, DELTA_N, DELTA_NE, DELTA_NW, DELTA_W, DELTA_S, DELTA_SW, DELTA_SE + }; + + for (int idx = 0; idx < 8; idx++) + { + Square from = orig; + Square to = from + directions[idx]; + + while (to != dest && square_distance(to, from) == 1 && square_is_ok(to)) + { + from = to; + to += directions[idx]; + } + + if (to == dest && square_distance(from, to) == 1) + return directions[idx]; + } + return DELTA_NONE; + } + + void init_direction_table() { + + for (Square s1 = SQ_A1; s1 <= SQ_H8; s1++) + for (Square s2 = SQ_A1; s2 <= SQ_H8; s2++) + DirectionTable[s1][s2] = uint8_t(get_direction(s1, s2)); + } + void init_masks() { + SetMaskBB[SQ_NONE] = 0ULL; ClearMaskBB[SQ_NONE] = ~SetMaskBB[SQ_NONE]; - for(Square s = SQ_A1; s <= SQ_H8; s++) { - SetMaskBB[s] = (1ULL << s); - ClearMaskBB[s] = ~SetMaskBB[s]; + + for (Square s = SQ_A1; s <= SQ_H8; s++) + { + SetMaskBB[s] = (1ULL << s); + ClearMaskBB[s] = ~SetMaskBB[s]; } - for(Color c = WHITE; c <= BLACK; c++) - for(Square s = SQ_A1; s <= SQ_H8; s++) { - PassedPawnMask[c][s] = - in_front_bb(c, s) & this_and_neighboring_files_bb(s); - OutpostMask[c][s] = in_front_bb(c, s) & neighboring_files_bb(s); - } - } + 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); + } - void init_ray_bitboards() { - int d[8] = {1, -1, 16, -16, 17, -17, 15, -15}; - for(int i = 0; i < 128; i = (i + 9) & ~8) { - for(int j = 0; j < 8; j++) { - RayBB[(i&7)|((i>>4)<<3)][j] = EmptyBoardBB; - for(int k = i + d[j]; (k & 0x88) == 0; k += d[j]) - set_bit(&(RayBB[(i&7)|((i>>4)<<3)][j]), Square((k&7)|((k>>4)<<3))); - } - } + for (Bitboard b = 0; b < 256; b++) + BitCount8Bit[b] = (uint8_t)count_1s(b); } - void init_attacks() { - int i, j, k, l; - int step[16][8] = { + + const int step[16][8] = { {0}, {7,9,0}, {17,15,10,6,-6,-10,-15,-17}, {9,7,-7,-9,0}, {8,1,-1,-8,0}, {9,7,-7,-9,8,1,-1,-8}, {9,7,-7,-9,8,1,-1,-8}, {0}, {0}, @@ -336,105 +447,115 @@ namespace { {9,7,-7,-9,8,1,-1,-8}, {9,7,-7,-9,8,1,-1,-8} }; - for(i = 0; i < 64; i++) { - for(j = 0; j <= int(BK); j++) { - StepAttackBB[j][i] = EmptyBoardBB; - for(k = 0; k < 8 && step[j][k] != 0; k++) { - l = i + step[j][k]; - if(l >= 0 && l < 64 && abs((i&7) - (l&7)) < 3) - StepAttackBB[j][i] |= (1ULL << l); + for (int i = 0; i < 64; i++) + for (int j = 0; j <= int(BK); j++) + { + StepAttackBB[j][i] = EmptyBoardBB; + for (int k = 0; k < 8 && step[j][k] != 0; k++) + { + int l = i + step[j][k]; + if (l >= 0 && l < 64 && abs((i & 7) - (l & 7)) < 3) + StepAttackBB[j][i] |= (1ULL << l); + } } - } - } } - 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 = 0ULL; - int rk = sq / 8, fl = sq % 8, r, f, i; - for(i = 0; i < dirs; i++) { - int dx = deltas[i][0], dy = deltas[i][1]; - for(f = fl+dx, r = rk+dy; - (dx==0 || (f>=fmin && f<=fmax)) && (dy==0 || (r>=rmin && r<=rmax)); - f += dx, r += dy) { - result |= (1ULL << (f + r*8)); - if(block & (1ULL << (f + r*8))) break; - } + int rk = sq / 8; + int fl = sq % 8; + + for (int i = 0; i < dirs; i++) + { + int dx = deltas[i][0]; + int dy = deltas[i][1]; + int f = fl + dx; + int 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))) + break; + + f += dx; + r += dy; + } } return result; } - void init_between_bitboards() { - SquareDelta step[8] = { - DELTA_E, DELTA_W, DELTA_N, DELTA_S, DELTA_NE, DELTA_SW, DELTA_NW, DELTA_SE - }; - SignedDirection d; - for(Square s1 = SQ_A1; s1 <= SQ_H8; s1++) - for(Square s2 = SQ_A1; s2 <= SQ_H8; s2++) { - BetweenBB[s1][s2] = EmptyBoardBB; - d = signed_direction_between_squares(s1, s2); - if(d != SIGNED_DIR_NONE) - for(Square s3 = s1 + step[d]; s3 != s2; s3 += step[d]) - set_bit(&(BetweenBB[s1][s2]), s3); + + Square s1, s2, s3; + SquareDelta d; + + for (s1 = SQ_A1; s1 <= SQ_H8; s1++) + for (s2 = SQ_A1; s2 <= SQ_H8; s2++) + { + BetweenBB[s1][s2] = EmptyBoardBB; + d = SquareDelta(DirectionTable[s1][s2]); + + if (d == DELTA_NONE) + continue; + + for (s3 = s1 + d; s3 != s2; s3 += d) + set_bit(&(BetweenBB[s1][s2]), s3); } } - Bitboard index_to_bitboard(int index, Bitboard mask) { - int i, j, bits = count_1s(mask); + Bitboard result = 0ULL; - for(i = 0; i < bits; i++) { - j = pop_1st_bit(&mask); - if(index & (1 << i)) result |= (1ULL << j); + int bits = count_1s(mask); + + for (int i = 0; i < bits; i++) + { + int j = pop_1st_bit(&mask); + if (index & (1 << i)) + result |= (1ULL << j); } return result; } + void init_sliding_attacks(Bitboard attacks[], int attackIndex[], Bitboard mask[], + const int shift[], const Bitboard mult[], int deltas[][2]) { - void init_sliding_attacks(Bitboard attacks[], - int attackIndex[], Bitboard mask[], - const int shift[2], const Bitboard mult[], - int deltas[][2]) { - int i, j, k, index = 0; - Bitboard b; - for(i = 0; i < 64; i++) { - attackIndex[i] = index; - mask[i] = sliding_attacks(i, 0ULL, 4, deltas, 1, 6, 1, 6); + for (int i = 0, index = 0; i < 64; i++) + { + attackIndex[i] = index; + mask[i] = sliding_attacks(i, 0, 4, deltas, 1, 6, 1, 6); #if defined(IS_64BIT) - j = (1 << (64 - shift[i])); + int j = (1 << (64 - shift[i])); #else - j = (1 << (32 - shift[i])); + int j = (1 << (32 - shift[i])); #endif - for(k = 0; k < j; k++) { - + for (int k = 0; k < j; k++) + { #if defined(IS_64BIT) - b = index_to_bitboard(k, mask[i]); - attacks[index + ((b * mult[i]) >> shift[i])] = - sliding_attacks(i, b, 4, deltas); + Bitboard b = index_to_bitboard(k, mask[i]); + attacks[index + ((b * mult[i]) >> shift[i])] = sliding_attacks(i, b, 4, deltas); #else - b = index_to_bitboard(k, mask[i]); - attacks[index + - (unsigned(int(b) * int(mult[i]) ^ - int(b >> 32) * int(mult[i] >> 32)) - >> shift[i])] = - sliding_attacks(i, b, 4, deltas); + 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 - } - index += j; + } + index += j; } } - void init_pseudo_attacks() { - Square s; - for(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); + + 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); } }