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 a202144912390bf316e0b9ea0e1e4cab45367e67..2da4d728ee78016bd31dab1c8401ce7c0b646595 100644 (file)
--- 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 1b6af3ead1afedbaba67526b32cd3f6762ffed4f..70835e8eeff144ef08c7b19753933ea18ca7798e 100644 (file)
--- 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 5dbc37ced3975966ca373595c13e92a4b4834d9b..742dbf40413fd977b84516371baa818c37c9cafa 100644 (file)
--- 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<KING>(Us), lsb(pos.checkers())) | pos.checkers();
+            target = between_bb(pos.square<KING>(Us), lsb(pos.checkers()));
             break;
         case NON_EVASIONS:
             target = ~pos.pieces(Us);
@@ -329,7 +329,7 @@ ExtMove* generate<EVASIONS>(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<WHITE, EVASIONS>(pos, moveList)
                      : generate_all<BLACK, EVASIONS>(pos, moveList);
 }

diff --git a/src/position.cpp b/src/position.cpp
index f4739413da44906e4b03c9bd54283f0d8e9251c4..772e45454c63a38d5dbde5754f1f9afde522d895 100644 (file)
--- 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<KING>(us)) | checkers()) & to))
+          // Our move must be a blocking interposition or a capture of the checking piece
+          if (!(between_bb(square<KING>(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;