Rename yields_to_threat and prevents_threat
[stockfish] / src / search.cpp
index 07405d42beed4a52f586d0ccae66c4b327797226..085d124ee66b994819a1e8e71e20bf99eb3532cd 100644 (file)
@@ -99,8 +99,8 @@ namespace {
   Value value_to_tt(Value v, int ply);
   Value value_from_tt(Value v, int ply);
   bool check_is_dangerous(Position& pos, Move move, Value futilityBase, Value beta);
   Value value_to_tt(Value v, int ply);
   Value value_from_tt(Value v, int ply);
   bool check_is_dangerous(Position& pos, Move move, Value futilityBase, Value beta);
-  bool yields_to_threat(const Position& pos, Move move, Move threat);
-  bool prevents_threat(const Position& pos, Move move, Move threat);
+  bool allows_move(const Position& pos, Move first, Move second);
+  bool prevents_move(const Position& pos, Move first, Move second);
   string uci_pv(const Position& pos, int depth, Value alpha, Value beta);
 
   struct Skill {
   string uci_pv(const Position& pos, int depth, Value alpha, Value beta);
 
   struct Skill {
@@ -188,7 +188,7 @@ void Search::think() {
   {
       RootMoves.push_back(MOVE_NONE);
       sync_cout << "info depth 0 score "
   {
       RootMoves.push_back(MOVE_NONE);
       sync_cout << "info depth 0 score "
-                << score_to_uci(RootPos.in_check() ? -VALUE_MATE : VALUE_DRAW)
+                << score_to_uci(RootPos.checkers() ? -VALUE_MATE : VALUE_DRAW)
                 << sync_endl;
 
       goto finalize;
                 << sync_endl;
 
       goto finalize;
@@ -208,7 +208,7 @@ void Search::think() {
   if (Options["Contempt Factor"] && !Options["UCI_AnalyseMode"])
   {
       int cf = Options["Contempt Factor"] * PawnValueMg / 100; // From centipawns
   if (Options["Contempt Factor"] && !Options["UCI_AnalyseMode"])
   {
       int cf = Options["Contempt Factor"] * PawnValueMg / 100; // From centipawns
-      cf = cf * MaterialTable::game_phase(RootPos) / PHASE_MIDGAME; // Scale down with phase
+      cf = cf * Material::game_phase(RootPos) / PHASE_MIDGAME; // Scale down with phase
       DrawValue[ RootColor] = VALUE_DRAW - Value(cf);
       DrawValue[~RootColor] = VALUE_DRAW + Value(cf);
   }
       DrawValue[ RootColor] = VALUE_DRAW - Value(cf);
       DrawValue[~RootColor] = VALUE_DRAW + Value(cf);
   }
@@ -482,16 +482,17 @@ namespace {
     Key posKey;
     Move ttMove, move, excludedMove, bestMove, threatMove;
     Depth ext, newDepth;
     Key posKey;
     Move ttMove, move, excludedMove, bestMove, threatMove;
     Depth ext, newDepth;
-    Value bestValue, value, ttValue, ttValueUpper;
+    Value bestValue, value, ttValue;
     Value eval, nullValue, futilityValue;
     bool inCheck, givesCheck, pvMove, singularExtensionNode;
     Value eval, nullValue, futilityValue;
     bool inCheck, givesCheck, pvMove, singularExtensionNode;
-    bool captureOrPromotion, dangerous, doFullDepthSearch;
+    bool captureOrPromotion, dangerous, doFullDepthSearch, threatExtension;
     int moveCount, playedMoveCount;
 
     // Step 1. Initialize node
     Thread* thisThread = pos.this_thread();
     moveCount = playedMoveCount = 0;
     int moveCount, playedMoveCount;
 
     // Step 1. Initialize node
     Thread* thisThread = pos.this_thread();
     moveCount = playedMoveCount = 0;
-    inCheck = pos.in_check();
+    threatExtension = false;
+    inCheck = pos.checkers();
 
     if (SpNode)
     {
 
     if (SpNode)
     {
@@ -544,43 +545,31 @@ namespace {
     tte = TT.probe(posKey);
     ttMove = RootNode ? RootMoves[PVIdx].pv[0] : tte ? tte->move() : MOVE_NONE;
     ttValue = tte ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE;
     tte = TT.probe(posKey);
     ttMove = RootNode ? RootMoves[PVIdx].pv[0] : tte ? tte->move() : MOVE_NONE;
     ttValue = tte ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE;
-    ttValueUpper = tte ? value_from_tt(tte->value_upper(), ss->ply) : VALUE_NONE;
 
     // At PV nodes we check for exact scores, while at non-PV nodes we check for
     // a fail high/low. Biggest advantage at probing at PV nodes is to have a
     // smooth experience in analysis mode. We don't probe at Root nodes otherwise
     // we should also update RootMoveList to avoid bogus output.
 
     // At PV nodes we check for exact scores, while at non-PV nodes we check for
     // a fail high/low. Biggest advantage at probing at PV nodes is to have a
     // smooth experience in analysis mode. We don't probe at Root nodes otherwise
     // we should also update RootMoveList to avoid bogus output.
-    if (!RootNode && tte)
+    if (   !RootNode
+        && tte
+        && tte->depth() >= depth
+        && ttValue != VALUE_NONE // Only in case of TT access race
+        && (           PvNode ?  tte->type() == BOUND_EXACT
+            : ttValue >= beta ? (tte->type() & BOUND_LOWER)
+                              : (tte->type() & BOUND_UPPER)))
     {
     {
-        // Fail High
-        if (  (tte->type() & BOUND_LOWER)
-            && ttValue >= beta
-            && tte->depth() >= depth
-            && ttValue != VALUE_NONE) // Only in case of TT access race
-        {
-            // Update killers, we assume ttMove caused a cut-off
-            if (    ttMove
-                && !pos.is_capture_or_promotion(ttMove)
-                &&  ttMove != ss->killers[0])
-            {
-                ss->killers[1] = ss->killers[0];
-                ss->killers[0] = ttMove;
-            }
-            TT.refresh(tte);
-            ss->currentMove = ttMove; // Can be MOVE_NONE
-            return ttValue;
-        }
+        TT.refresh(tte);
+        ss->currentMove = ttMove; // Can be MOVE_NONE
 
 
-        // Fail Low
-        if (  (tte->type() & BOUND_UPPER)
-            && ttValueUpper < beta
-            && tte->depth_upper() >= depth
-            && ttValueUpper != VALUE_NONE) // Only in case of TT access race
+        if (    ttValue >= beta
+            &&  ttMove
+            && !pos.is_capture_or_promotion(ttMove)
+            &&  ttMove != ss->killers[0])
         {
         {
-            TT.refresh(tte);
-            ss->currentMove = ttMove; // Can be MOVE_NONE
-            return ttValueUpper;
+            ss->killers[1] = ss->killers[0];
+            ss->killers[0] = ttMove;
         }
         }
+        return ttValue;
     }
 
     // Step 5. Evaluate the position statically and update parent's gain statistics
     }
 
     // Step 5. Evaluate the position statically and update parent's gain statistics
@@ -687,16 +676,15 @@ namespace {
             // The null move failed low, which means that we may be faced with
             // some kind of threat. If the previous move was reduced, check if
             // the move that refuted the null move was somehow connected to the
             // The null move failed low, which means that we may be faced with
             // some kind of threat. If the previous move was reduced, check if
             // the move that refuted the null move was somehow connected to the
-            // move which was reduced. If a connection is found, return a fail
-            // low score (which will cause the reduced move to fail high in the
-            // parent node, which will trigger a re-search with full depth).
+            // move which was reduced. If a connection is found extend moves that
+            // defend against threat.
             threatMove = (ss+1)->currentMove;
 
             if (   depth < 5 * ONE_PLY
                 && (ss-1)->reduction
                 && threatMove != MOVE_NONE
             threatMove = (ss+1)->currentMove;
 
             if (   depth < 5 * ONE_PLY
                 && (ss-1)->reduction
                 && threatMove != MOVE_NONE
-                && yields_to_threat(pos, (ss-1)->currentMove, threatMove))
-                return beta - 1;
+                && allows_move(pos, (ss-1)->currentMove, threatMove))
+                threatExtension = true;
         }
     }
 
         }
     }
 
@@ -814,6 +802,9 @@ split_point_start: // At split points actual search starts from here
       if (PvNode && dangerous)
           ext = ONE_PLY;
 
       if (PvNode && dangerous)
           ext = ONE_PLY;
 
+      else if (threatExtension && prevents_move(pos, move, threatMove))
+          ext = ONE_PLY;
+
       else if (givesCheck && pos.see_sign(move) >= 0)
           ext = ONE_PLY / 2;
 
       else if (givesCheck && pos.see_sign(move) >= 0)
           ext = ONE_PLY / 2;
 
@@ -856,7 +847,7 @@ split_point_start: // At split points actual search starts from here
           // Move count based pruning
           if (   depth < 16 * ONE_PLY
               && moveCount >= FutilityMoveCounts[depth]
           // Move count based pruning
           if (   depth < 16 * ONE_PLY
               && moveCount >= FutilityMoveCounts[depth]
-              && (!threatMove || !prevents_threat(pos, move, threatMove)))
+              && (!threatMove || !prevents_move(pos, move, threatMove)))
           {
               if (SpNode)
                   sp->mutex.lock();
           {
               if (SpNode)
                   sp->mutex.lock();
@@ -1015,9 +1006,10 @@ split_point_start: // At split points actual search starts from here
       // Step 19. Check for splitting the search
       if (   !SpNode
           &&  depth >= Threads.min_split_depth()
       // Step 19. Check for splitting the search
       if (   !SpNode
           &&  depth >= Threads.min_split_depth()
-          &&  bestValue < beta
           &&  Threads.available_slave_exists(thisThread))
       {
           &&  Threads.available_slave_exists(thisThread))
       {
+          assert(bestValue < beta);
+
           bestValue = Threads.split<FakeSplit>(pos, ss, alpha, beta, bestValue, &bestMove,
                                                depth, threatMove, moveCount, mp, NT);
           if (bestValue >= beta)
           bestValue = Threads.split<FakeSplit>(pos, ss, alpha, beta, bestValue, &bestMove,
                                                depth, threatMove, moveCount, mp, NT);
           if (bestValue >= beta)
@@ -1092,7 +1084,7 @@ split_point_start: // At split points actual search starts from here
     const bool PvNode = (NT == PV);
 
     assert(NT == PV || NT == NonPV);
     const bool PvNode = (NT == PV);
 
     assert(NT == PV || NT == NonPV);
-    assert(InCheck == pos.in_check());
+    assert(InCheck == !!pos.checkers());
     assert(alpha >= -VALUE_INFINITE && alpha < beta && beta <= VALUE_INFINITE);
     assert(PvNode || (alpha == beta - 1));
     assert(depth <= DEPTH_ZERO);
     assert(alpha >= -VALUE_INFINITE && alpha < beta && beta <= VALUE_INFINITE);
     assert(PvNode || (alpha == beta - 1));
     assert(depth <= DEPTH_ZERO);
@@ -1101,7 +1093,7 @@ split_point_start: // At split points actual search starts from here
     const TTEntry* tte;
     Key posKey;
     Move ttMove, move, bestMove;
     const TTEntry* tte;
     Key posKey;
     Move ttMove, move, bestMove;
-    Value bestValue, value, ttValue, ttValueUpper, futilityValue, futilityBase, oldAlpha;
+    Value bestValue, value, ttValue, futilityValue, futilityBase, oldAlpha;
     bool givesCheck, enoughMaterial, evasionPrunable, fromNull;
     Depth ttDepth;
 
     bool givesCheck, enoughMaterial, evasionPrunable, fromNull;
     Depth ttDepth;
 
@@ -1123,34 +1115,21 @@ split_point_start: // At split points actual search starts from here
     tte = TT.probe(posKey);
     ttMove = tte ? tte->move() : MOVE_NONE;
     ttValue = tte ? value_from_tt(tte->value(),ss->ply) : VALUE_NONE;
     tte = TT.probe(posKey);
     ttMove = tte ? tte->move() : MOVE_NONE;
     ttValue = tte ? value_from_tt(tte->value(),ss->ply) : VALUE_NONE;
-    ttValueUpper = tte ? value_from_tt(tte->value_upper(),ss->ply) : VALUE_NONE;
 
     // Decide whether or not to include checks, this fixes also the type of
     // TT entry depth that we are going to use. Note that in qsearch we use
     // only two types of depth in TT: DEPTH_QS_CHECKS or DEPTH_QS_NO_CHECKS.
     ttDepth = InCheck || depth >= DEPTH_QS_CHECKS ? DEPTH_QS_CHECKS
                                                   : DEPTH_QS_NO_CHECKS;
 
     // Decide whether or not to include checks, this fixes also the type of
     // TT entry depth that we are going to use. Note that in qsearch we use
     // only two types of depth in TT: DEPTH_QS_CHECKS or DEPTH_QS_NO_CHECKS.
     ttDepth = InCheck || depth >= DEPTH_QS_CHECKS ? DEPTH_QS_CHECKS
                                                   : DEPTH_QS_NO_CHECKS;
-    if (tte)
+    if (   tte
+        && tte->depth() >= ttDepth
+        && ttValue != VALUE_NONE // Only in case of TT access race
+        && (           PvNode ?  tte->type() == BOUND_EXACT
+            : ttValue >= beta ? (tte->type() & BOUND_LOWER)
+                              : (tte->type() & BOUND_UPPER)))
     {
     {
-        // Fail High
-        if (  (tte->type() & BOUND_LOWER)
-            && ttValue >= beta
-            && tte->depth() >= ttDepth
-            && ttValue != VALUE_NONE) // Only in case of TT access race
-        {
-            ss->currentMove = ttMove; // Can be MOVE_NONE
-            return ttValue;
-        }
-
-        // Fail Low
-        if (  (tte->type() & BOUND_UPPER)
-            && ttValueUpper < beta
-            && tte->depth_upper() >= ttDepth
-            && ttValueUpper != VALUE_NONE) // Only in case of TT access race
-        {
-            ss->currentMove = ttMove; // Can be MOVE_NONE
-            return ttValueUpper;
-        }
+        ss->currentMove = ttMove; // Can be MOVE_NONE
+        return ttValue;
     }
 
     // Evaluate the position statically
     }
 
     // Evaluate the position statically
@@ -1367,39 +1346,40 @@ split_point_start: // At split points actual search starts from here
   }
 
 
   }
 
 
-  // yields_to_threat() tests whether the move at previous ply yields to the so
-  // called threat move (the best move returned from a null search that fails
-  // low). Here 'yields to' means that the move somehow made the threat possible
-  // for instance if the moving piece is the same in both moves.
+  // allows_move() tests whether the move at previous ply (first) somehow makes a
+  // second move possible, for instance if the moving piece is the same in both
+  // moves. Normally the second move is the threat move (the best move returned
+  // from a null search that fails low).
 
 
-  bool yields_to_threat(const Position& pos, Move move, Move threat) {
+  bool allows_move(const Position& pos, Move first, Move second) {
 
 
-    assert(is_ok(move));
-    assert(is_ok(threat));
-    assert(color_of(pos.piece_on(from_sq(threat))) == ~pos.side_to_move());
+    assert(is_ok(first));
+    assert(is_ok(second));
+    assert(color_of(pos.piece_on(from_sq(second))) == ~pos.side_to_move());
+    assert(color_of(pos.piece_on(to_sq(first))) == ~pos.side_to_move());
 
 
-    Square mfrom = from_sq(move);
-    Square mto = to_sq(move);
-    Square tfrom = from_sq(threat);
-    Square tto = to_sq(threat);
+    Square m1from = from_sq(first);
+    Square m2from = from_sq(second);
+    Square m1to = to_sq(first);
+    Square m2to = to_sq(second);
 
 
-    // The piece is the same or threat's destination was vacated by the move
-    if (mto == tfrom || tto == mfrom)
+    // The piece is the same or second's destination was vacated by the first move
+    if (m1to == m2from || m2to == m1from)
         return true;
 
         return true;
 
-    // Threat moves through the vacated square
-    if (between_bb(tfrom, tto) & mfrom)
+    // Second one moves through the square vacated by first one
+    if (between_bb(m2from, m2to) & m1from)
       return true;
 
       return true;
 
-    // Threat's destination is defended by the move's piece
-    Bitboard matt = pos.attacks_from(pos.piece_on(mto), mto, pos.pieces() ^ tfrom);
-    if (matt & tto)
+    // Second's destination is defended by the first move's piece
+    Bitboard m1att = pos.attacks_from(pos.piece_on(m1to), m1to, pos.pieces() ^ m2from);
+    if (m1att & m2to)
         return true;
 
         return true;
 
-    // Threat gives a discovered check through the move's checking piece
-    if (matt & pos.king_square(pos.side_to_move()))
+    // Second move gives a discovered check through the first's checking piece
+    if (m1att & pos.king_square(pos.side_to_move()))
     {
     {
-        assert(between_bb(mto, pos.king_square(pos.side_to_move())) & tfrom);
+        assert(between_bb(m1to, pos.king_square(pos.side_to_move())) & m2from);
         return true;
     }
 
         return true;
     }
 
@@ -1407,51 +1387,52 @@ split_point_start: // At split points actual search starts from here
   }
 
 
   }
 
 
-  // prevents_threat() tests whether a move is able to defend against the so
-  // called threat move (the best move returned from a null search that fails
-  // low). In this case will not be pruned.
+  // prevents_move() tests whether a move (first) is able to defend against an
+  // opponent's move (second). In this case will not be pruned. Normally the
+  // second move is the threat move (the best move returned from a null search
+  // that fails low).
 
 
-  bool prevents_threat(const Position& pos, Move move, Move threat) {
+  bool prevents_move(const Position& pos, Move first, Move second) {
 
 
-    assert(is_ok(move));
-    assert(is_ok(threat));
-    assert(!pos.is_capture_or_promotion(move));
-    assert(!pos.is_passed_pawn_push(move));
+    assert(is_ok(first));
+    assert(is_ok(second));
+    assert(!pos.is_capture_or_promotion(first));
+    assert(!pos.is_passed_pawn_push(first));
 
 
-    Square mfrom = from_sq(move);
-    Square mto = to_sq(move);
-    Square tfrom = from_sq(threat);
-    Square tto = to_sq(threat);
+    Square m1from = from_sq(first);
+    Square m2from = from_sq(second);
+    Square m1to = to_sq(first);
+    Square m2to = to_sq(second);
 
     // Don't prune moves of the threatened piece
 
     // Don't prune moves of the threatened piece
-    if (mfrom == tto)
+    if (m1from == m2to)
         return true;
 
     // If the threatened piece has value less than or equal to the value of the
     // threat piece, don't prune moves which defend it.
         return true;
 
     // If the threatened piece has value less than or equal to the value of the
     // threat piece, don't prune moves which defend it.
-    if (    pos.is_capture(threat)
-        && (   PieceValue[MG][pos.piece_on(tfrom)] >= PieceValue[MG][pos.piece_on(tto)]
-            || type_of(pos.piece_on(tfrom)) == KING))
+    if (    pos.is_capture(second)
+        && (   PieceValue[MG][pos.piece_on(m2from)] >= PieceValue[MG][pos.piece_on(m2to)]
+            || type_of(pos.piece_on(m2from)) == KING))
     {
         // Update occupancy as if the piece and the threat are moving
     {
         // Update occupancy as if the piece and the threat are moving
-        Bitboard occ = pos.pieces() ^ mfrom ^ mto ^ tfrom;
-        Piece piece = pos.piece_on(mfrom);
+        Bitboard occ = pos.pieces() ^ m1from ^ m1to ^ m2from;
+        Piece piece = pos.piece_on(m1from);
 
         // The moved piece attacks the square 'tto' ?
 
         // The moved piece attacks the square 'tto' ?
-        if (pos.attacks_from(piece, mto, occ) & tto)
+        if (pos.attacks_from(piece, m1to, occ) & m2to)
             return true;
 
         // Scan for possible X-ray attackers behind the moved piece
             return true;
 
         // Scan for possible X-ray attackers behind the moved piece
-        Bitboard xray =  (attacks_bb<  ROOK>(tto, occ) & pos.pieces(color_of(piece), QUEEN, ROOK))
-                       | (attacks_bb<BISHOP>(tto, occ) & pos.pieces(color_of(piece), QUEEN, BISHOP));
+        Bitboard xray =  (attacks_bb<  ROOK>(m2to, occ) & pos.pieces(color_of(piece), QUEEN, ROOK))
+                       | (attacks_bb<BISHOP>(m2to, occ) & pos.pieces(color_of(piece), QUEEN, BISHOP));
 
         // Verify attackers are triggered by our move and not already existing
 
         // Verify attackers are triggered by our move and not already existing
-        if (xray && (xray ^ (xray & pos.attacks_from<QUEEN>(tto))))
+        if (xray && (xray ^ (xray & pos.attacks_from<QUEEN>(m2to))))
             return true;
     }
 
     // Don't prune safe moves which block the threat path
             return true;
     }
 
     // Don't prune safe moves which block the threat path
-    if ((between_bb(tfrom, tto) & mto) && pos.see_sign(move) >= 0)
+    if ((between_bb(m2from, m2to) & m1to) && pos.see_sign(first) >= 0)
         return true;
 
     return false;
         return true;
 
     return false;
@@ -1564,7 +1545,8 @@ void RootMove::extract_pv_from_tt(Position& pos) {
   do {
       pv.push_back(m);
 
   do {
       pv.push_back(m);
 
-      assert(pos.move_is_legal(pv[ply]));
+      assert(MoveList<LEGAL>(pos).contains(pv[ply]));
+
       pos.do_move(pv[ply++], *st++);
       tte = TT.probe(pos.key());
 
       pos.do_move(pv[ply++], *st++);
       tte = TT.probe(pos.key());
 
@@ -1596,7 +1578,8 @@ void RootMove::insert_pv_in_tt(Position& pos) {
       if (!tte || tte->move() != pv[ply]) // Don't overwrite correct entries
           TT.store(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, pv[ply]);
 
       if (!tte || tte->move() != pv[ply]) // Don't overwrite correct entries
           TT.store(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, pv[ply]);
 
-      assert(pos.move_is_legal(pv[ply]));
+      assert(MoveList<LEGAL>(pos).contains(pv[ply]));
+
       pos.do_move(pv[ply++], *st++);
 
   } while (pv[ply] != MOVE_NONE);
       pos.do_move(pv[ply++], *st++);
 
   } while (pv[ply] != MOVE_NONE);