Optimisation of Position::see and Position::see_sign

Stephane's patch removes the only usage of Position::see, where the
returned value isn't immediately compared with a value. So I replaced
this function by its optimised and more specific version see_ge. This
function also supersedes the function Position::see_sign.

bool Position::see_ge(Move m, Value v) const;

This function tests if the SEE of a move is greater or equal than a
given value. We use forward iteration on captures instread of backward
one, therefore we don't need the swapList array. Also we stop as soon
as we have enough information to obtain the result, avoiding unnecessary
calls to the min_attacker function.

Speed tests (Windows 7), 20 runs for each engine:
Test engine: mean 866648, st. dev. 5964
Base engine: mean 846751, st. dev. 22846
Speedup: 1.023

Speed test by Stephane Nicolet

Fishtest STC test:
LLR: 2.96 (-2.94,2.94) [0.00,5.00]
Total: 26040 W: 4675 L: 4442 D: 16923
http://tests.stockfishchess.org/tests/view/57f648990ebc59038170fa03

No functional change.

diff --git a/src/movepick.cpp b/src/movepick.cpp
index 1ec56c2f700a7c2a30bedd371af100fc6a29e9ec..95e60003f00b6eafc9d5f5592e0cdd22c64bedef 100644 (file)
--- a/src/movepick.cpp
+++ b/src/movepick.cpp
@@ -115,7 +115,7 @@ MovePicker::MovePicker(const Position& p, Move ttm, Value th)
   ttMove =   ttm
           && pos.pseudo_legal(ttm)
           && pos.capture(ttm)
   ttMove =   ttm
           && pos.pseudo_legal(ttm)
           && pos.capture(ttm)

-          && pos.see(ttm) > threshold ? ttm : MOVE_NONE;
+          && pos.see_ge(ttm, threshold + 1)? ttm : MOVE_NONE;

 
   stage += (ttMove == MOVE_NONE);
 }
 
   stage += (ttMove == MOVE_NONE);
 }


@@ -201,7 +201,7 @@ Move MovePicker::next_move() {
           move = pick_best(cur++, endMoves);
           if (move != ttMove)
           {
           move = pick_best(cur++, endMoves);
           if (move != ttMove)
           {

-              if (pos.see_sign(move) >= VALUE_ZERO)
+              if (pos.see_ge(move, VALUE_ZERO))

                   return move;
 
               // Losing capture, move it to the beginning of the array
                   return move;
 
               // Losing capture, move it to the beginning of the array


@@ -295,7 +295,7 @@ Move MovePicker::next_move() {
       {
           move = pick_best(cur++, endMoves);
           if (   move != ttMove
       {
           move = pick_best(cur++, endMoves);
           if (   move != ttMove

-              && pos.see(move) > threshold)
+              && pos.see_ge(move, threshold + 1))

               return move;
       }
       break;
               return move;
       }
       break;

diff --git a/src/position.cpp b/src/position.cpp
index 9fe5f893c9da5f199577abeb283fa7942d4bee6e..c09a953b62e3a7612d53f03069266a2a00493d6d 100644 (file)
--- a/src/position.cpp
+++ b/src/position.cpp
@@ -955,102 +955,83 @@ Key Position::key_after(Move m) const {
 }
 
 
 }
 
 

-/// Position::see() is a static exchange evaluator: It tries to estimate the
-/// material gain or loss resulting from a move.
+/// Position::see_ge (Static Exchange Evaluation Greater or Equal) tests if the
+/// SEE value of move is greater or equal to the given value. We'll use an
+/// algorithm similar to alpha-beta pruning with a null window.

 
 

-Value Position::see_sign(Move m) const {
+bool Position::see_ge(Move m, Value v) const {

 
   assert(is_ok(m));
 
 
   assert(is_ok(m));
 

-  // Early return if SEE cannot be negative because captured piece value
-  // is not less then capturing one. Note that king moves always return
-  // here because king midgame value is set to 0.
-  if (PieceValue[MG][moved_piece(m)] <= PieceValue[MG][piece_on(to_sq(m))])
-      return VALUE_KNOWN_WIN;
-
-  return see(m);
-}
-
-Value Position::see(Move m) const {
-
-  Square from, to;
-  Bitboard occupied, attackers, stmAttackers;
-  Value swapList[32];
-  int slIndex = 1;
-  PieceType nextVictim;
-  Color stm;
-
-  assert(is_ok(m));
-
-  from = from_sq(m);
-  to = to_sq(m);
-  swapList[0] = PieceValue[MG][piece_on(to)];
-  stm = color_of(piece_on(from));
-  occupied = pieces() ^ from;
-
-  // Castling moves are implemented as king capturing the rook so cannot
-  // be handled correctly. Simply return VALUE_ZERO that is always correct
-  // unless in the rare case the rook ends up under attack.
+  // Castling moves are implemented as king capturing the rook so cannot be
+  // handled correctly. Simply assume the SEE value is VALUE_ZERO that is always
+  // correct unless in the rare case the rook ends up under attack.

   if (type_of(m) == CASTLING)
   if (type_of(m) == CASTLING)

-      return VALUE_ZERO;
+      return VALUE_ZERO >= v;
+
+  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;

 
   if (type_of(m) == ENPASSANT)
   {
 
   if (type_of(m) == ENPASSANT)
   {

-      occupied ^= to - pawn_push(stm); // Remove the captured pawn
-      swapList[0] = PieceValue[MG][PAWN];
+      occupied = SquareBB[to - pawn_push(~stm)]; // Remove the captured pawn
+      balance = PieceValue[MG][PAWN];
+  }
+  else
+  {
+      balance = PieceValue[MG][piece_on(to)];
+      occupied = 0;

   }
 
   }
 

-  // Find all attackers to the destination square, with the moving piece
-  // removed, but possibly an X-ray attacker added behind it.
-  attackers = attackers_to(to, occupied) & occupied;
+  if (balance < v)
+      return false;

 
 

-  // If the opponent has no attackers we are finished
-  stm = ~stm;
-  stmAttackers = attackers & pieces(stm);
-  occupied ^= to; // For the case when captured piece is a pinner
+  if (nextVictim == KING)
+      return true;
+
+  balance -= PieceValue[MG][nextVictim];
+
+  if (balance >= v)
+      return true;

 
 

-  // Don't allow pinned pieces to attack pieces except the king as long all
-  // pinners are on their original square.
-  if (!(st->pinnersForKing[stm] & ~occupied))
-      stmAttackers &= ~st->blockersForKing[stm];
+  bool relativeStm = true; // True if the opponent is to move
+  occupied ^= pieces() ^ from ^ to;

 
 

-  if (!stmAttackers)
-        return swapList[0];
+  // Find all attackers to the destination square, with the moving piece removed,
+  // but possibly an X-ray attacker added behind it.
+  Bitboard attackers = attackers_to(to, occupied) & occupied;

 
 

-  // The destination square is defended, which makes things rather more
-  // difficult to compute. We proceed by building up a "swap list" containing
-  // the material gain or loss at each stop in a sequence of captures to the
-  // destination square, where the sides alternately capture, and always
-  // capture with the least valuable piece. After each capture, we look for
-  // new X-ray attacks from behind the capturing piece.
-  nextVictim = type_of(piece_on(from));
+  while (true)
+  {
+      stmAttackers = attackers & pieces(stm);

 
 

-  do {
-      assert(slIndex < 32);
+      // Don't allow pinned pieces to attack pieces except the king as long all
+      // pinners are on their original square.
+      if (!(st->pinnersForKing[stm] & ~occupied))
+          stmAttackers &= ~st->blockersForKing[stm];

 
 

-      // Add the new entry to the swap list
-      swapList[slIndex] = -swapList[slIndex - 1] + PieceValue[MG][nextVictim];
+      if (!stmAttackers)
+          return relativeStm;

 
       // Locate and remove the next least valuable attacker
       nextVictim = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);
 
       // Locate and remove the next least valuable attacker
       nextVictim = min_attacker<PAWN>(byTypeBB, to, stmAttackers, occupied, attackers);

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

 
 

-      // Don't allow pinned pieces to attack pieces except the king
-      if (   nextVictim != KING
-          && !(st->pinnersForKing[stm] & ~occupied))
-          stmAttackers &= ~st->blockersForKing[stm];
+      if (nextVictim == KING)
+          return relativeStm == bool(attackers & pieces(~stm));

 
 

-      ++slIndex;
+      balance += relativeStm ?  PieceValue[MG][nextVictim]
+                             : -PieceValue[MG][nextVictim];

 
 

-  } while (stmAttackers && (nextVictim != KING || (--slIndex, false))); // Stop before a king capture
+      relativeStm = !relativeStm;

 
 

-  // Having built the swap list, we negamax through it to find the best
-  // achievable score from the point of view of the side to move.
-  while (--slIndex)
-      swapList[slIndex - 1] = std::min(-swapList[slIndex], swapList[slIndex - 1]);
+      if (relativeStm == (balance >= v))
+          return relativeStm;

 
 

-  return swapList[0];
+      stm = ~stm;
+  }

 }
 
 
 }
 
 

diff --git a/src/position.h b/src/position.h
index 9830619eac80eb11b4c7ef7ba6131a77d4bd5247..e74a3c713128939a1a2d9e558a5c1e0345de4139 100644 (file)
--- a/src/position.h
+++ b/src/position.h
@@ -133,8 +133,7 @@ public:
   void undo_null_move();
 
   // Static Exchange Evaluation
   void undo_null_move();
 
   // Static Exchange Evaluation

-  Value see(Move m) const;
-  Value see_sign(Move m) const;
+  bool see_ge(Move m, Value value) const;

 
   // Accessing hash keys
   Key key() const;
 
   // Accessing hash keys
   Key key() const;

diff --git a/src/search.cpp b/src/search.cpp
index 64cdb325ebce53c3a785747767cf76109b5daa31..eae3468074d18e0ba9d4c2bea5cd0c2702292d08 100644 (file)
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -889,7 +889,7 @@ moves_loop: // When in check search starts from here
       // Step 12. Extend checks
       if (    givesCheck
           && !moveCountPruning
       // Step 12. Extend checks
       if (    givesCheck
           && !moveCountPruning

-          &&  pos.see_sign(move) >= VALUE_ZERO)
+          &&  pos.see_ge(move, VALUE_ZERO))

           extension = ONE_PLY;
 
       // Singular extension search. If all moves but one fail low on a search of
           extension = ONE_PLY;
 
       // Singular extension search. If all moves but one fail low on a search of


@@ -946,11 +946,11 @@ moves_loop: // When in check search starts from here
 
               // Prune moves with negative SEE
               if (   lmrDepth < 8
 
               // Prune moves with negative SEE
               if (   lmrDepth < 8

-                  && pos.see_sign(move) < Value(-35 * lmrDepth * lmrDepth))
+                  && !pos.see_ge(move, Value(-35 * lmrDepth * lmrDepth)))

                   continue;
           }
           else if (   depth < 7 * ONE_PLY
                   continue;
           }
           else if (   depth < 7 * ONE_PLY

-                   && pos.see_sign(move) < Value(-35 * depth / ONE_PLY * depth / ONE_PLY))
+                   && !pos.see_ge(move, Value(-35 * depth / ONE_PLY * depth / ONE_PLY)))

                   continue;
       }
 
                   continue;
       }
 


@@ -992,7 +992,7 @@ moves_loop: // When in check search starts from here
               // because the destination square is empty.
               else if (   type_of(move) == NORMAL
                        && type_of(pos.piece_on(to_sq(move))) != PAWN
               // because the destination square is empty.
               else if (   type_of(move) == NORMAL
                        && type_of(pos.piece_on(to_sq(move))) != PAWN

-                       && pos.see(make_move(to_sq(move), from_sq(move))) < VALUE_ZERO)
+                       && !pos.see_ge(make_move(to_sq(move), from_sq(move)),  VALUE_ZERO))

                   r -= 2 * ONE_PLY;
 
               // Decrease/increase reduction for moves with a good/bad history
                   r -= 2 * ONE_PLY;
 
               // Decrease/increase reduction for moves with a good/bad history


@@ -1302,7 +1302,7 @@ moves_loop: // When in check search starts from here
               continue;
           }
 
               continue;
           }
 

-          if (futilityBase <= alpha && pos.see(move) <= VALUE_ZERO)
+          if (futilityBase <= alpha && !pos.see_ge(move, VALUE_ZERO + 1))

           {
               bestValue = std::max(bestValue, futilityBase);
               continue;
           {
               bestValue = std::max(bestValue, futilityBase);
               continue;


@@ -1317,7 +1317,7 @@ moves_loop: // When in check search starts from here
       // Don't search moves with negative SEE values
       if (  (!InCheck || evasionPrunable)
           &&  type_of(move) != PROMOTION
       // Don't search moves with negative SEE values
       if (  (!InCheck || evasionPrunable)
           &&  type_of(move) != PROMOTION

-          &&  pos.see_sign(move) < VALUE_ZERO)
+          &&  !pos.see_ge(move, VALUE_ZERO))

           continue;
 
       // Speculative prefetch as early as possible
           continue;
 
       // Speculative prefetch as early as possible