Reformat SEE to better document the function

This is one of the most difficult to understand but also
most important and speed critical functions of SF.

This patch rewrites some part of it to hopefully
make it clearer and drop some redundant variables
in the process.

Same speed than master (or even a bit more).

Thanks to Chris Cain for useful feedback.

No functional change.

diff --git a/src/bitboard.h b/src/bitboard.h
index 5cafcfcc1a7987e62852e3778d780e2015887e38..cf948afc7c9398f4b63aa56d79409d34acc7f89c 100644 (file)
--- a/src/bitboard.h
+++ b/src/bitboard.h
@@ -160,15 +160,17 @@ constexpr Bitboard shift(Bitboard b) {
         : 0;
 }
 
         : 0;
 }
 

+

 /// pawn_attacks_bb() returns the pawn attacks for the given color from the
 /// squares in the given bitboard.
 
 /// pawn_attacks_bb() returns the pawn attacks for the given color from the
 /// squares in the given bitboard.
 

-template<Color c>
+template<Color C>

 constexpr Bitboard pawn_attacks_bb(Bitboard b) {
 constexpr Bitboard pawn_attacks_bb(Bitboard b) {

-  return c == WHITE ? shift<NORTH_WEST>(b) | shift<NORTH_EAST>(b)
+  return C == WHITE ? shift<NORTH_WEST>(b) | shift<NORTH_EAST>(b)

                     : shift<SOUTH_WEST>(b) | shift<SOUTH_EAST>(b);
 }
 
                     : shift<SOUTH_WEST>(b) | shift<SOUTH_EAST>(b);
 }
 

+

 /// adjacent_files_bb() returns a bitboard representing all the squares on the
 /// adjacent files of the given one.
 
 /// adjacent_files_bb() returns a bitboard representing all the squares on the
 /// adjacent files of the given one.
 


@@ -187,9 +189,9 @@ inline Bitboard between_bb(Square s1, Square s2) {
 }
 
 
 }
 
 

-/// forward_ranks_bb() returns a bitboard representing all the squares on all 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.
+/// forward_ranks_bb() returns a bitboard representing the squares on all 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.

 
 inline Bitboard forward_ranks_bb(Color c, Square s) {
   return ForwardRanksBB[c][rank_of(s)];
 
 inline Bitboard forward_ranks_bb(Color c, Square s) {
   return ForwardRanksBB[c][rank_of(s)];

diff --git a/src/evaluate.cpp b/src/evaluate.cpp
index 0022ae4c26d28fcae3d329032d730a627b1ed9e9..884b1d854722939f90412be2805a98d4d378461d 100644 (file)
--- a/src/evaluate.cpp
+++ b/src/evaluate.cpp
@@ -510,9 +510,9 @@ namespace {
   template<Tracing T> template<Color Us>
   Score Evaluation<T>::threats() const {
 
   template<Tracing T> template<Color Us>
   Score Evaluation<T>::threats() const {
 

-    const Color     Them     = (Us == WHITE ? BLACK      : WHITE);
-    const Direction Up       = (Us == WHITE ? NORTH      : SOUTH);
-    const Bitboard  TRank3BB = (Us == WHITE ? Rank3BB    : Rank6BB);
+    const Color     Them     = (Us == WHITE ? BLACK   : WHITE);
+    const Direction Up       = (Us == WHITE ? NORTH   : SOUTH);
+    const Bitboard  TRank3BB = (Us == WHITE ? Rank3BB : Rank6BB);

 
     Bitboard b, weak, defended, nonPawnEnemies, stronglyProtected, safeThreats;
     Score score = SCORE_ZERO;
 
     Bitboard b, weak, defended, nonPawnEnemies, stronglyProtected, safeThreats;
     Score score = SCORE_ZERO;

diff --git a/src/pawns.cpp b/src/pawns.cpp
index 01e9632c2639fce3af989847f91123105165f42f..a1b533258b30f6e4b1b0264c24f896facdbc65ec 100644 (file)
--- a/src/pawns.cpp
+++ b/src/pawns.cpp
@@ -88,8 +88,8 @@ namespace {
   template<Color Us>
   Score evaluate(const Position& pos, Pawns::Entry* e) {
 
   template<Color Us>
   Score evaluate(const Position& pos, Pawns::Entry* e) {
 

-    const Color     Them = (Us == WHITE ? BLACK      : WHITE);
-    const Direction Up   = (Us == WHITE ? NORTH      : SOUTH);
+    const Color     Them = (Us == WHITE ? BLACK : WHITE);
+    const Direction Up   = (Us == WHITE ? NORTH : SOUTH);

 
     Bitboard b, neighbours, stoppers, doubled, supported, phalanx;
     Bitboard lever, leverPush;
 
     Bitboard b, neighbours, stoppers, doubled, supported, phalanx;
     Bitboard lever, leverPush;

diff --git a/src/position.cpp b/src/position.cpp
index 7e12fdcc433f10f53643bccfad7d08d9fa0b3617..fdae0ae0bf211999f9c2ee69472c4f151af0f8a0 100644 (file)
--- a/src/position.cpp
+++ b/src/position.cpp
@@ -60,22 +60,27 @@ const Piece Pieces[] = { W_PAWN, W_KNIGHT, W_BISHOP, W_ROOK, W_QUEEN, W_KING,
 // from the bitboards and scan for new X-ray attacks behind it.
 
 template<int Pt>
 // from the bitboards and scan for new X-ray attacks behind it.
 
 template<int Pt>

-PieceType min_attacker(const Bitboard* bb, Square to, Bitboard stmAttackers,
+PieceType min_attacker(const Bitboard* byTypeBB, Square to, Bitboard stmAttackers,

                        Bitboard& occupied, Bitboard& attackers) {
 
                        Bitboard& occupied, Bitboard& attackers) {
 

-  Bitboard b = stmAttackers & bb[Pt];
+  Bitboard b = stmAttackers & byTypeBB[Pt];

   if (!b)
   if (!b)

-      return min_attacker<Pt + 1>(bb, to, stmAttackers, occupied, attackers);
+      return min_attacker<Pt + 1>(byTypeBB, to, stmAttackers, occupied, attackers);

 
 

-  occupied ^= b & ~(b - 1);
+  occupied ^= lsb(b); // Remove the attacker from occupied

 
 

+  // Add any X-ray attack behind the just removed piece. For instance with
+  // rooks in a8 and a7 attacking a1, after removing a7 we add rook in a8.
+  // Note that new added attackers can be of any color.

   if (Pt == PAWN || Pt == BISHOP || Pt == QUEEN)
   if (Pt == PAWN || Pt == BISHOP || Pt == QUEEN)

-      attackers |= attacks_bb<BISHOP>(to, occupied) & (bb[BISHOP] | bb[QUEEN]);
+      attackers |= attacks_bb<BISHOP>(to, occupied) & (byTypeBB[BISHOP] | byTypeBB[QUEEN]);

 
   if (Pt == ROOK || Pt == QUEEN)
 
   if (Pt == ROOK || Pt == QUEEN)

-      attackers |= attacks_bb<ROOK>(to, occupied) & (bb[ROOK] | bb[QUEEN]);
+      attackers |= attacks_bb<ROOK>(to, occupied) & (byTypeBB[ROOK] | byTypeBB[QUEEN]);

 
 

-  attackers &= occupied; // After X-ray that may add already processed pieces
+  // X-ray may add already processed pieces because byTypeBB[] is constant: in
+  // the rook example, now attackers contains _again_ rook in a7, so remove it.
+  attackers &= occupied;

   return (PieceType)Pt;
 }
 
   return (PieceType)Pt;
 }
 


@@ -997,11 +1002,12 @@ bool Position::see_ge(Move m, Value threshold) const {
   if (type_of(m) != NORMAL)
       return VALUE_ZERO >= threshold;
 
   if (type_of(m) != NORMAL)
       return VALUE_ZERO >= threshold;
 

+  Bitboard stmAttackers;

   Square from = from_sq(m), to = to_sq(m);
   PieceType nextVictim = type_of(piece_on(from));
   Square from = from_sq(m), to = to_sq(m);
   PieceType nextVictim = type_of(piece_on(from));

-  Color stm = ~color_of(piece_on(from)); // First consider opponent's move
-  Value balance; // Values of the pieces taken by us minus opponent's ones
-  Bitboard occupied, stmAttackers;
+  Color us = color_of(piece_on(from));
+  Color stm = ~us; // First consider opponent's move
+  Value balance;   // Values of the pieces taken by us minus opponent's ones

 
   // The opponent may be able to recapture so this is the best result
   // we can hope for.
 
   // The opponent may be able to recapture so this is the best result
   // we can hope for.


@@ -1014,65 +1020,57 @@ bool Position::see_ge(Move m, Value threshold) const {
   // capture our piece for free.
   balance -= PieceValue[MG][nextVictim];
 
   // capture our piece for free.
   balance -= PieceValue[MG][nextVictim];
 

-  if (balance >= VALUE_ZERO) // Always true if nextVictim == KING
+  // If it is enough (like in PxQ) then return immediately. Note that
+  // in case nextVictim == KING we always return here, this is ok
+  // if the given move is legal.
+  if (balance >= VALUE_ZERO)

       return true;
 
       return true;
 

-  bool opponentToMove = true;
-  occupied = pieces() ^ from ^ to;
-
-  // Find all attackers to the destination square, with the moving piece removed,
-  // but possibly an X-ray attacker added behind it.
+  // Find all attackers to the destination square, with the moving piece
+  // removed, but possibly an X-ray attacker added behind it.
+  Bitboard occupied = pieces() ^ from ^ to;

   Bitboard attackers = attackers_to(to, occupied) & occupied;
 
   while (true)
   {
   Bitboard attackers = attackers_to(to, occupied) & occupied;
 
   while (true)
   {

-      // The balance is negative only because we assumed we could win
-      // the last piece for free. We are truly winning only if we can
-      // win the last piece _cheaply enough_. Test if we can actually
-      // do this otherwise "give up".
-      assert(balance < VALUE_ZERO);
-

       stmAttackers = attackers & pieces(stm);
 
       stmAttackers = attackers & pieces(stm);
 

-      // Don't allow pinned pieces to attack pieces except the king as long all
-      // pinners are on their original square.
+      // Don't allow pinned pieces to attack (except the king) as long as
+      // all pinners are on their original square.

       if (!(st->pinnersForKing[stm] & ~occupied))
           stmAttackers &= ~st->blockersForKing[stm];
 
       if (!(st->pinnersForKing[stm] & ~occupied))
           stmAttackers &= ~st->blockersForKing[stm];
 

-      // If we have no more attackers we must give up
+      // If stm has no more attackers then give up: stm loses

       if (!stmAttackers)
           break;
 
       if (!stmAttackers)
           break;
 

-      // Locate and remove the next least valuable attacker
+      // Locate and remove the next least valuable attacker, and add to
+      // the bitboard 'attackers' the possibly X-ray attackers behind it.

       nextVictim = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
 
       nextVictim = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
 

-      if (nextVictim == KING)
-      {
-          // Our only attacker is the king. If the opponent still has
-          // attackers we must give up. Otherwise we make the move and
-          // (having no more attackers) the opponent must give up.
-          if (!(attackers & pieces(~stm)))
-              opponentToMove = !opponentToMove;
-          break;
-      }
+      stm = ~stm; // Switch side to move

 
 

-      // Assume the opponent can win the next piece for free and switch sides
-      balance += PieceValue[MG][nextVictim];
-      opponentToMove = !opponentToMove;
+      // Negamax the balance with alpha = balance, beta = balance+1 and
+      // add nextVictim's value.
+      //
+      //      (balance, balance+1) -> (-balance-1, -balance)
+      //
+      assert(balance < VALUE_ZERO);

 
 

-      // If balance is negative after receiving a free piece then give up
-      if (balance < VALUE_ZERO)
-          break;
+      balance = -balance - 1 - PieceValue[MG][nextVictim];

 
 

-      // Complete the process of switching sides. The first line swaps
-      // all negative numbers with non-negative numbers. The compiler
-      // probably knows that it is just the bitwise negation ~balance.
-      balance = -balance-1;
-      stm = ~stm;
+      // If balance is still non-negative after giving away nextVictim then we
+      // win. The only thing to be careful about it is that we should revert
+      // stm if we captured with the king when the opponent still has attackers.
+      if (balance >= VALUE_ZERO)
+      {
+          if (nextVictim == KING && (attackers & pieces(stm)))
+              stm = ~stm;
+          break;
+      }
+      assert(nextVictim != KING);

   }
   }

-
-  // If the opponent gave up we win, otherwise we lose.
-  return opponentToMove;
+  return us != stm; // We break the above loop when stm loses

 }
 
 
 }