From: bmc4 Date: Mon, 15 Mar 2021 19:06:42 +0000 (-0300) Subject: Change definition of between_bb() X-Git-Url: https://git.sesse.net/?p=stockfish;a=commitdiff_plain;h=50890616591443ab06faa0927747bf14c8d450e3 Change definition of between_bb() We remark that in current master, most of our use cases for between_bb() can be optimized if the second parameter of the function is added to the segment. So we change the definition of between_bb(s1, s2) such that it excludes s1 but includes s2. We also use a precomputed array for between_bb() for another small speed gain (see https://tests.stockfishchess.org/tests/view/604d09f72433018de7a389fb). Passed STC: LLR: 2.96 (-2.94,2.94) {-0.25,1.25} Total: 18736 W: 1746 L: 1607 D: 15383 Ptnml(0-2): 61, 1226, 6644, 1387, 50 https://tests.stockfishchess.org/tests/view/60428c84ddcba5f0627bb6e4 Yellow LTC: LTC: LLR: -3.00 (-2.94,2.94) {0.25,1.25} Total: 39144 W: 1431 L: 1413 D: 36300 Ptnml(0-2): 13, 1176, 17184, 1178, 21 https://tests.stockfishchess.org/tests/view/605128702433018de7a38ca1 Closes https://github.com/official-stockfish/Stockfish/pull/3397 --------- Verified for correctness by running perft on the following position: ./stockfish position fen 4rrk1/1p1nq3/p7/2p1P1pp/3P2bp/3Q1Bn1/PPPB4/1K2R1NR w - - 40 21 go perft 6 Nodes searched: 6136386434 -------- No functional change --- diff --git a/src/bitboard.cpp b/src/bitboard.cpp index a2021449..2da4d728 100644 --- a/src/bitboard.cpp +++ b/src/bitboard.cpp @@ -29,6 +29,7 @@ uint8_t SquareDistance[SQUARE_NB][SQUARE_NB]; Bitboard SquareBB[SQUARE_NB]; Bitboard LineBB[SQUARE_NB][SQUARE_NB]; +Bitboard BetweenBB[SQUARE_NB][SQUARE_NB]; Bitboard PseudoAttacks[PIECE_TYPE_NB][SQUARE_NB]; Bitboard PawnAttacks[COLOR_NB][SQUARE_NB]; @@ -107,8 +108,14 @@ void Bitboards::init() { for (PieceType pt : { BISHOP, ROOK }) for (Square s2 = SQ_A1; s2 <= SQ_H8; ++s2) + { if (PseudoAttacks[pt][s1] & s2) - LineBB[s1][s2] = (attacks_bb(pt, s1, 0) & attacks_bb(pt, s2, 0)) | s1 | s2; + { + LineBB[s1][s2] = (attacks_bb(pt, s1, 0) & attacks_bb(pt, s2, 0)) | s1 | s2; + BetweenBB[s1][s2] = (attacks_bb(pt, s1, square_bb(s2)) & attacks_bb(pt, s2, square_bb(s1))); + } + BetweenBB[s1][s2] |= s2; + } } } diff --git a/src/bitboard.h b/src/bitboard.h index 1b6af3ea..70835e8e 100644 --- a/src/bitboard.h +++ b/src/bitboard.h @@ -75,6 +75,7 @@ extern uint8_t PopCnt16[1 << 16]; extern uint8_t SquareDistance[SQUARE_NB][SQUARE_NB]; extern Bitboard SquareBB[SQUARE_NB]; +extern Bitboard BetweenBB[SQUARE_NB][SQUARE_NB]; extern Bitboard LineBB[SQUARE_NB][SQUARE_NB]; extern Bitboard PseudoAttacks[PIECE_TYPE_NB][SQUARE_NB]; extern Bitboard PawnAttacks[COLOR_NB][SQUARE_NB]; @@ -215,19 +216,22 @@ inline Bitboard line_bb(Square s1, Square s2) { } -/// between_bb() returns a bitboard representing squares that are linearly -/// between the two given squares (excluding the given squares). If the given -/// squares are not on a same file/rank/diagonal, we return 0. For instance, -/// between_bb(SQ_C4, SQ_F7) will return a bitboard with squares D5 and E6. +/// between_bb(s1, s2) returns a bitboard representing the squares in the semi-open +/// segment between the squares s1 and s2 (excluding s1 but including s2). If the +/// given squares are not on a same file/rank/diagonal, it returns s2. For instance, +/// between_bb(SQ_C4, SQ_F7) will return a bitboard with squares D5, E6 and F7, but +/// between_bb(SQ_E6, SQ_F8) will return a bitboard with the square F8. This trick +/// allows to generate non-king evasion moves faster: the defending piece must either +/// interpose itself to cover the check or capture the checking piece. inline Bitboard between_bb(Square s1, Square s2) { - Bitboard b = line_bb(s1, s2) & ((AllSquares << s1) ^ (AllSquares << s2)); - return b & (b - 1); //exclude lsb + assert(is_ok(s1) && is_ok(s2)); + return BetweenBB[s1][s2]; } -/// forward_ranks_bb() returns a bitboard representing the squares on the ranks -/// in front of the given one, from the point of view of the given color. For instance, +/// forward_ranks_bb() returns a bitboard representing the squares on the ranks in +/// front of the given one, from the point of view of the given color. For instance, /// forward_ranks_bb(BLACK, SQ_D3) will return the 16 squares on ranks 1 and 2. constexpr Bitboard forward_ranks_bb(Color c, Square s) { diff --git a/src/movegen.cpp b/src/movegen.cpp index 5dbc37ce..742dbf40 100644 --- a/src/movegen.cpp +++ b/src/movegen.cpp @@ -158,7 +158,7 @@ namespace { { assert(rank_of(pos.ep_square()) == relative_rank(Us, RANK_6)); - // An en passant capture cannot resolve a discovered check. + // An en passant capture cannot resolve a discovered check if (Type == EVASIONS && (target & (pos.ep_square() + Up))) return moveList; @@ -218,7 +218,7 @@ namespace { target = ~pos.pieces(); break; case EVASIONS: - target = between_bb(pos.square(Us), lsb(pos.checkers())) | pos.checkers(); + target = between_bb(pos.square(Us), lsb(pos.checkers())); break; case NON_EVASIONS: target = ~pos.pieces(Us); @@ -329,7 +329,7 @@ ExtMove* generate(const Position& pos, ExtMove* moveList) { if (more_than_one(pos.checkers())) return moveList; // Double check, only a king move can save the day - // Generate blocking evasions or captures of the checking piece + // Generate blocking interpositions or captures of the checking piece return us == WHITE ? generate_all(pos, moveList) : generate_all(pos, moveList); } diff --git a/src/position.cpp b/src/position.cpp index f4739413..772e4545 100644 --- a/src/position.cpp +++ b/src/position.cpp @@ -320,7 +320,7 @@ void Position::set_castling_right(Color c, Square rfrom) { Square kto = relative_square(c, cr & KING_SIDE ? SQ_G1 : SQ_C1); Square rto = relative_square(c, cr & KING_SIDE ? SQ_F1 : SQ_D1); - castlingPath[cr] = (between_bb(rfrom, rto) | between_bb(kfrom, kto) | rto | kto) + castlingPath[cr] = (between_bb(rfrom, rto) | between_bb(kfrom, kto)) & ~(kfrom | rfrom); } @@ -613,8 +613,8 @@ bool Position::pseudo_legal(const Move m) const { if (more_than_one(checkers())) return false; - // Our move must be a blocking evasion or a capture of the checking piece - if (!((between_bb(lsb(checkers()), square(us)) | checkers()) & to)) + // Our move must be a blocking interposition or a capture of the checking piece + if (!(between_bb(square(us), lsb(checkers())) & to)) return false; } // In case of king moves under check we have to remove king so as to catch @@ -1218,7 +1218,7 @@ bool Position::has_game_cycle(int ply) const { Square s1 = from_sq(move); Square s2 = to_sq(move); - if (!(between_bb(s1, s2) & pieces())) + if (!((between_bb(s1, s2) ^ s2) & pieces())) { if (ply > i) return true;