X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=ec4272a9e0f9bcb7ebf601515621e34be4e632ba;hp=0c5ead46754c20411fe6ab3de99953dceb884524;hb=51c3af9dd01951cf23f17c5f7c6cb9f7c32dccdc;hpb=e9de96f0e417dc706882b645d14dbf41e7ccc467

diff --git a/src/search.cpp b/src/search.cpp
index 0c5ead46..ec4272a9 100644
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -28,7 +28,6 @@
 #include <iostream>
 #include <sstream>
 
-#include "bitcount.h"
 #include "book.h"
 #include "evaluate.h"
 #include "history.h"
@@ -193,16 +192,6 @@ namespace {
 
   /// Variables initialized by UCI options
 
-  // Adjustable playing strength
-  int Slowdown = 0;
-  const int SlowdownArray[32] = {
-    19, 41, 70, 110, 160, 230, 320, 430, 570, 756, 1000, 1300, 1690, 2197,
-    2834, 3600, 4573, 5809, 7700, 9863, 12633, 16181, 20726, 26584, 34005,
-    43557, 55792, 71463, 91536, 117247, 150180, 192363
-  };
-  int Strength;
-  const int MaxStrength = 25;
-
   // Minimum number of full depth (i.e. non-reduced) moves at PV and non-PV nodes
   int LMRPVMoves, LMRNonPVMoves; // heavy SMP read access for the latter
 
@@ -289,7 +278,7 @@ namespace {
   Value qsearch(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID);
   void sp_search(SplitPoint* sp, int threadID);
   void sp_search_pv(SplitPoint* sp, int threadID);
-  void init_node(const Position& pos, SearchStack ss[], int ply, int threadID);
+  void init_node(SearchStack ss[], int ply, int threadID);
   void update_pv(SearchStack ss[], int ply);
   void sp_update_pv(SearchStack* pss, SearchStack ss[], int ply);
   bool connected_moves(const Position& pos, Move m1, Move m2);
@@ -302,7 +291,6 @@ namespace {
   bool ok_to_history(const Position& pos, Move m);
   void update_history(const Position& pos, Move m, Depth depth, Move movesSearched[], int moveCount);
   void update_killers(Move m, SearchStack& ss);
-  void slowdown(const Position& pos);
 
   bool fail_high_ply_1();
   int current_search_time();
@@ -311,6 +299,7 @@ namespace {
   void ponderhit();
   void print_current_line(SearchStack ss[], int ply, int threadID);
   void wait_for_stop_or_ponderhit();
+  void init_ss_array(SearchStack ss[]);
 
   void idle_loop(int threadID, SplitPoint* waitSp);
   void init_split_point_stack();
@@ -319,7 +308,9 @@ namespace {
   bool thread_is_available(int slave, int master);
   bool idle_thread_exists(int master);
   bool split(const Position& pos, SearchStack* ss, int ply,
-             Value *alpha, Value *beta, Value *bestValue, Depth depth, int *moves,
+             Value *alpha, Value *beta, Value *bestValue,
+             const Value futilityValue, const Value approximateValue,
+             Depth depth, int *moves,
              MovePicker *mp, Bitboard dcCandidates, int master, bool pvNode);
   void wake_sleeping_threads();
 
@@ -423,10 +414,8 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move,
 
   read_weights(pos.side_to_move());
 
-  // Set the number of active threads. If UCI_LimitStrength is enabled, never
-  // use more than one thread.
-  int newActiveThreads =
-    get_option_value_bool("UCI_LimitStrength")? 1 : get_option_value_int("Threads");
+  // Set the number of active threads
+  int newActiveThreads = get_option_value_int("Threads");
   if (newActiveThreads != ActiveThreads)
   {
       ActiveThreads = newActiveThreads;
@@ -439,19 +428,6 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move,
   for (int i = 1; i < ActiveThreads; i++)
       assert(thread_is_available(i, 0));
 
-  // Set playing strength
-  if (get_option_value_bool("UCI_LimitStrength"))
-  {
-      Strength = (get_option_value_int("UCI_Elo") - 2100) / 25;
-      Slowdown =
-        (Strength == MaxStrength)? 0 : SlowdownArray[Max(0, 31-Strength)];
-  }
-  else
-  {
-      Strength = MaxStrength;
-      Slowdown = 0;
-  }
-
   // Set thinking time
   int myTime = time[side_to_move];
   int myIncrement = increment[side_to_move];
@@ -472,7 +448,8 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move,
       if (movesToGo == 1)
       {
           MaxSearchTime = myTime / 2;
-          AbsoluteMaxSearchTime = Min(myTime / 2, myTime - 500);
+          AbsoluteMaxSearchTime = 
+             (myTime > 3000)? (myTime - 500) : ((myTime * 3) / 4);
       } else {
           MaxSearchTime = myTime / Min(movesToGo, 20);
           AbsoluteMaxSearchTime = Min((4 * myTime) / movesToGo, myTime / 3);
@@ -496,13 +473,10 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move,
       NodesBetweenPolls = Min(MaxNodes, 30000);
       InfiniteSearch = true; // HACK
   }
-  else if (Slowdown) {
-      if (Slowdown > 50000) NodesBetweenPolls = 30;
-      else if (Slowdown > 10000) NodesBetweenPolls = 100;
-      else if (Slowdown > 1000) NodesBetweenPolls = 500;
-      else if (Slowdown > 100) NodesBetweenPolls = 3000;
-      else NodesBetweenPolls = 15000;
-  }
+  else if (myTime && myTime < 1000)
+      NodesBetweenPolls = 1000;
+  else if (myTime && myTime < 5000)
+      NodesBetweenPolls = 5000;
   else
       NodesBetweenPolls = 30000;
 
@@ -523,9 +497,9 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move,
   {
       Value v = id_loop(pos, searchMoves);
       loseOnTime = (   UseLSNFiltering
-                     && myTime < LSNTime
-                     && myIncrement == 0
-                     && v < -LSNValue);
+                    && myTime < LSNTime
+                    && myIncrement == 0
+                    && v < -LSNValue);
   }
   else
   {
@@ -658,14 +632,19 @@ namespace {
     // searchMoves are verified, copied, scored and sorted
     RootMoveList rml(p, searchMoves);
 
+    // Print RootMoveList c'tor startup scoring to the standard output,
+    // so that we print information also for iteration 1.
+    std::cout << "info depth " << 1 << "\ninfo depth " << 1
+              << " score " << value_to_string(rml.get_move_score(0))
+              << " time " << current_search_time()
+              << " nodes " << nodes_searched()
+              << " nps " << nps()
+              << " pv " << rml.get_move(0) << "\n";
+
     // Initialize
     TT.new_search();
     H.clear();
-    for (int i = 0; i < 3; i++)
-    {
-        ss[i].init(i);
-        ss[i].initKillers();
-    }
+    init_ss_array(ss);
     IterationInfo[1] = IterationInfoType(rml.get_move_score(0), rml.get_move_score(0));
     Iteration = 1;
 
@@ -916,7 +895,7 @@ namespace {
         else
         {
             if (   newDepth >= 3*OnePly
-                && i >= MultiPV + LMRPVMoves - 2 // Remove -2 and decrease LMRPVMoves instead ?
+                && i >= MultiPV + LMRPVMoves
                 && !dangerous
                 && !moveIsCapture
                 && !move_is_promotion(move)
@@ -972,7 +951,7 @@ namespace {
             // Update PV
             rml.set_move_score(i, value);
             update_pv(ss, 0);
-            TT.extract_pv(pos, ss[0].pv);
+            TT.extract_pv(pos, ss[0].pv, PLY_MAX);
             rml.set_move_pv(i, ss[0].pv);
 
             if (MultiPV == 1)
@@ -999,7 +978,10 @@ namespace {
                 std::cout << std::endl;
 
                 if (UseLogFile)
-                    LogFile << pretty_pv(pos, current_search_time(), Iteration, nodes_searched(), value, ss[0].pv)
+                    LogFile << pretty_pv(pos, current_search_time(), Iteration, nodes_searched(), value, 
+                                         ((value >= beta)? VALUE_TYPE_LOWER
+                                          : ((value <= alpha)? VALUE_TYPE_UPPER : VALUE_TYPE_EXACT)),
+                                         ss[0].pv)
                             << std::endl;
 
                 if (value > alpha)
@@ -1056,7 +1038,7 @@ namespace {
 
     // Initialize, and make an early exit in case of an aborted search,
     // an instant draw, maximum ply reached, etc.
-    init_node(pos, ss, ply, threadID);
+    init_node(ss, ply, threadID);
 
     // After init_node() that calls poll()
     if (AbortSearch || thread_should_stop(threadID))
@@ -1068,7 +1050,7 @@ namespace {
     EvalInfo ei;
 
     if (ply >= PLY_MAX - 1)
-        return evaluate(pos, ei, threadID);
+        return pos.is_check() ? quick_evaluate(pos) : evaluate(pos, ei, threadID);
 
     // Mate distance pruning
     Value oldAlpha = alpha;
@@ -1091,16 +1073,16 @@ namespace {
 
     // Initialize a MovePicker object for the current position, and prepare
     // to search all moves
-    MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]);
-
     Move move, movesSearched[256];
     int moveCount = 0;
     Value value, bestValue = -VALUE_INFINITE;
-    Bitboard dcCandidates = mp.discovered_check_candidates();
     Color us = pos.side_to_move();
     bool isCheck = pos.is_check();
     bool mateThreat = pos.has_mate_threat(opposite_color(us));
 
+    MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]);
+    Bitboard dcCandidates = mp.discovered_check_candidates();
+
     // Loop through all legal moves until no moves remain or a beta cutoff
     // occurs.
     while (   alpha < beta
@@ -1109,7 +1091,7 @@ namespace {
     {
       assert(move_is_ok(move));
 
-      bool singleReply = (isCheck && mp.number_of_moves() == 1);
+      bool singleReply = (isCheck && mp.number_of_evasions() == 1);
       bool moveIsCheck = pos.move_is_check(move, dcCandidates);
       bool moveIsCapture = pos.move_is_capture(move);
 
@@ -1196,7 +1178,7 @@ namespace {
           && idle_thread_exists(threadID)
           && !AbortSearch
           && !thread_should_stop(threadID)
-          && split(pos, ss, ply, &alpha, &beta, &bestValue, depth,
+          && split(pos, ss, ply, &alpha, &beta, &bestValue, VALUE_NONE, VALUE_NONE, depth,
                    &moveCount, &mp, dcCandidates, threadID, true))
           break;
     }
@@ -1246,7 +1228,7 @@ namespace {
 
     // Initialize, and make an early exit in case of an aborted search,
     // an instant draw, maximum ply reached, etc.
-    init_node(pos, ss, ply, threadID);
+    init_node(ss, ply, threadID);
 
     // After init_node() that calls poll()
     if (AbortSearch || thread_should_stop(threadID))
@@ -1258,7 +1240,7 @@ namespace {
     EvalInfo ei;
 
     if (ply >= PLY_MAX - 1)
-        return evaluate(pos, ei, threadID);
+        return pos.is_check() ? quick_evaluate(pos) : evaluate(pos, ei, threadID);
 
     // Mate distance pruning
     if (value_mated_in(ply) >= beta)
@@ -1358,6 +1340,10 @@ namespace {
     bool useFutilityPruning =   depth < SelectiveDepth
                              && !isCheck;
 
+    // Avoid calling evaluate() if we already have the score in TT
+    if (tte && (tte->type() & VALUE_TYPE_EVAL))
+        futilityValue = value_from_tt(tte->value(), ply) + FutilityMargins[int(depth) - 2];
+
     // Loop through all legal moves until no moves remain or a beta cutoff
     // occurs.
     while (   bestValue < beta
@@ -1366,7 +1352,7 @@ namespace {
     {
       assert(move_is_ok(move));
 
-      bool singleReply = (isCheck && mp.number_of_moves() == 1);
+      bool singleReply = (isCheck && mp.number_of_evasions() == 1);
       bool moveIsCheck = pos.move_is_check(move, dcCandidates);
       bool moveIsCapture = pos.move_is_capture(move);
 
@@ -1385,7 +1371,8 @@ namespace {
       {
           // History pruning. See ok_to_prune() definition
           if (   moveCount >= 2 + int(depth)
-              && ok_to_prune(pos, move, ss[ply].threatMove, depth))
+              && ok_to_prune(pos, move, ss[ply].threatMove, depth)
+              && bestValue > value_mated_in(PLY_MAX))
               continue;
 
           // Value based pruning
@@ -1452,7 +1439,7 @@ namespace {
           && idle_thread_exists(threadID)
           && !AbortSearch
           && !thread_should_stop(threadID)
-          && split(pos, ss, ply, &beta, &beta, &bestValue, depth, &moveCount,
+          && split(pos, ss, ply, &beta, &beta, &bestValue, futilityValue, approximateEval, depth, &moveCount,
                    &mp, dcCandidates, threadID, false))
         break;
     }
@@ -1502,7 +1489,7 @@ namespace {
 
     // Initialize, and make an early exit in case of an aborted search,
     // an instant draw, maximum ply reached, etc.
-    init_node(pos, ss, ply, threadID);
+    init_node(ss, ply, threadID);
 
     // After init_node() that calls poll()
     if (AbortSearch || thread_should_stop(threadID))
@@ -1535,7 +1522,7 @@ namespace {
     if (isCheck)
         staticValue = -VALUE_INFINITE;
 
-    else if (tte && tte->type() == VALUE_TYPE_EVAL)
+    else if (tte && (tte->type() & VALUE_TYPE_EVAL))
     {
         // Use the cached evaluation score if possible
         assert(ei.futilityMargin == Value(0));
@@ -1545,8 +1532,8 @@ namespace {
     else
         staticValue = evaluate(pos, ei, threadID);
 
-    if (ply == PLY_MAX - 1)
-        return evaluate(pos, ei, threadID);
+    if (ply >= PLY_MAX - 1)
+        return pos.is_check() ? quick_evaluate(pos) : evaluate(pos, ei, threadID);
 
     // Initialize "stand pat score", and return it immediately if it is
     // at least beta.
@@ -1556,7 +1543,7 @@ namespace {
     {
         // Store the score to avoid a future costly evaluation() call
         if (!isCheck && !tte && ei.futilityMargin == 0)
-            TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EVAL, Depth(-127*OnePly), MOVE_NONE);
+            TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EV_LO, Depth(-127*OnePly), MOVE_NONE);
 
         return bestValue;
     }
@@ -1644,9 +1631,13 @@ namespace {
     Move m = ss[ply].pv[ply];
     if (!pvNode)
     {
+        // If bestValue isn't changed it means it is still the static evaluation of
+        // the node, so keep this info to avoid a future costly evaluation() call.
+        ValueType type = (bestValue == staticValue && !ei.futilityMargin ? VALUE_TYPE_EV_UP : VALUE_TYPE_UPPER);
         Depth d = (depth == Depth(0) ? Depth(0) : Depth(-1));
+
         if (bestValue < beta)
-            TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, d, MOVE_NONE);
+            TT.store(pos.get_key(), value_to_tt(bestValue, ply), type, d, MOVE_NONE);
         else
             TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, d, m);
     }
@@ -1704,10 +1695,37 @@ namespace {
       if (    useFutilityPruning
           && !dangerous
           && !moveIsCapture
-          && !move_is_promotion(move)
-          &&  moveCount >= 2 + int(sp->depth)
-          &&  ok_to_prune(pos, move, ss[sp->ply].threatMove, sp->depth))
-        continue;
+          && !move_is_promotion(move))
+      {
+          // History pruning. See ok_to_prune() definition
+          if (   moveCount >= 2 + int(sp->depth)
+              && ok_to_prune(pos, move, ss[sp->ply].threatMove, sp->depth)
+              && sp->bestValue > value_mated_in(PLY_MAX))
+              continue;
+
+          // Value based pruning
+          if (sp->approximateEval < sp->beta)
+          {
+              if (sp->futilityValue == VALUE_NONE)
+              {
+                  EvalInfo ei;
+                  sp->futilityValue =  evaluate(pos, ei, threadID)
+                                    + FutilityMargins[int(sp->depth) - 2];
+              }
+
+              if (sp->futilityValue < sp->beta)
+              {
+                  if (sp->futilityValue > sp->bestValue) // Less then 1% of cases
+                  {
+                      lock_grab(&(sp->lock));
+                      if (sp->futilityValue > sp->bestValue)
+                          sp->bestValue = sp->futilityValue;
+                      lock_release(&(sp->lock));
+                  }
+                  continue;
+              }
+          }
+      }
 
       // Make and search the move.
       StateInfo st;
@@ -1741,21 +1759,24 @@ namespace {
           break;
 
       // New best move?
-      lock_grab(&(sp->lock));
-      if (value > sp->bestValue && !thread_should_stop(threadID))
+      if (value > sp->bestValue) // Less then 2% of cases
       {
-          sp->bestValue = value;
-          if (sp->bestValue >= sp->beta)
+          lock_grab(&(sp->lock));
+          if (value > sp->bestValue && !thread_should_stop(threadID))
           {
-              sp_update_pv(sp->parentSstack, ss, sp->ply);
-              for (int i = 0; i < ActiveThreads; i++)
-                  if (i != threadID && (i == sp->master || sp->slaves[i]))
-                      Threads[i].stop = true;
+              sp->bestValue = value;
+              if (sp->bestValue >= sp->beta)
+              {
+                  sp_update_pv(sp->parentSstack, ss, sp->ply);
+                  for (int i = 0; i < ActiveThreads; i++)
+                      if (i != threadID && (i == sp->master || sp->slaves[i]))
+                          Threads[i].stop = true;
 
-              sp->finished = true;
-        }
+                  sp->finished = true;
+              }
+          }
+          lock_release(&(sp->lock));
       }
-      lock_release(&(sp->lock));
     }
 
     lock_grab(&(sp->lock));
@@ -1962,7 +1983,7 @@ namespace {
     bool includeAllMoves = (searchMoves[0] == MOVE_NONE);
 
     // Generate all legal moves
-    MoveStack* last = generate_legal_moves(pos, mlist);
+    MoveStack* last = generate_moves(pos, mlist);
 
     // Add each move to the moves[] array
     for (MoveStack* cur = mlist; cur != last; cur++)
@@ -1978,6 +1999,7 @@ namespace {
         // Find a quick score for the move
         StateInfo st;
         SearchStack ss[PLY_MAX_PLUS_2];
+        init_ss_array(ss);
 
         moves[count].move = cur->move;
         pos.do_move(moves[count].move, st);
@@ -2089,14 +2111,11 @@ namespace {
   // NodesBetweenPolls nodes, init_node() also calls poll(), which polls
   // for user input and checks whether it is time to stop the search.
 
-  void init_node(const Position& pos, SearchStack ss[], int ply, int threadID) {
+  void init_node(SearchStack ss[], int ply, int threadID) {
 
     assert(ply >= 0 && ply < PLY_MAX);
     assert(threadID >= 0 && threadID < ActiveThreads);
 
-    if (Slowdown && Iteration >= 3)
-      slowdown(pos);
-
     Threads[threadID].nodes++;
 
     if (threadID == 0)
@@ -2153,7 +2172,9 @@ namespace {
   // the second move is assumed to be a move from the current position.
 
   bool connected_moves(const Position& pos, Move m1, Move m2) {
+
     Square f1, t1, f2, t2;
+    Piece p;
 
     assert(move_is_ok(m1));
     assert(move_is_ok(m2));
@@ -2179,31 +2200,32 @@ namespace {
       return true;
 
     // Case 4: The destination square for m2 is attacked by the moving piece in m1
-    if (pos.piece_attacks_square(pos.piece_on(t1), t1, t2))
+    p = pos.piece_on(t1);
+    if (bit_is_set(pos.attacks_from(p, t1), t2))
         return true;
 
     // Case 5: Discovered check, checking piece is the piece moved in m1
-    if (   piece_is_slider(pos.piece_on(t1))
+    if (   piece_is_slider(p)
         && bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), f2)
-        && !bit_is_set(squares_between(t2, pos.king_square(pos.side_to_move())), t2))
+        && !bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), t2))
     {
         Bitboard occ = pos.occupied_squares();
         Color us = pos.side_to_move();
         Square ksq = pos.king_square(us);
         clear_bit(&occ, f2);
-        if (pos.type_of_piece_on(t1) == BISHOP)
+        if (type_of_piece(p) == BISHOP)
         {
             if (bit_is_set(bishop_attacks_bb(ksq, occ), t1))
                 return true;
         }
-        else if (pos.type_of_piece_on(t1) == ROOK)
+        else if (type_of_piece(p) == ROOK)
         {
             if (bit_is_set(rook_attacks_bb(ksq, occ), t1))
                 return true;
         }
         else
         {
-            assert(pos.type_of_piece_on(t1) == QUEEN);
+            assert(type_of_piece(p) == QUEEN);
             if (bit_is_set(queen_attacks_bb(ksq, occ), t1))
                 return true;
         }
@@ -2431,20 +2453,6 @@ namespace {
   }
 
 
-  // slowdown() simply wastes CPU cycles doing nothing useful. It's used
-  // in strength handicap mode.
-
-  void slowdown(const Position &pos) {
-    int i, n;
-    n = Slowdown;
-    for (i = 0; i < n; i++)  {
-        Square s = Square(i&63);
-        if (count_1s(pos.attacks_to(s)) > 63)
-            std::cout << "This can't happen, but I put this string here anyway, in order to prevent the compiler from optimizing away the useless computation." << std::endl;
-    }
-  }
-
-
   // fail_high_ply_1() checks if some thread is currently resolving a fail
   // high at ply 1 at the node below the first root node.  This information
   // is used for time managment.
@@ -2591,6 +2599,18 @@ namespace {
   }
 
 
+  // init_ss_array() does a fast reset of the first entries of a SearchStack array
+
+  void init_ss_array(SearchStack ss[]) {
+
+    for (int i = 0; i < 3; i++)
+    {
+        ss[i].init(i);
+        ss[i].initKillers();
+    }
+  }
+
+
   // wait_for_stop_or_ponderhit() is called when the maximum depth is reached
   // while the program is pondering.  The point is to work around a wrinkle in
   // the UCI protocol:  When pondering, the engine is not allowed to give a
@@ -2768,7 +2788,8 @@ namespace {
   // splitPoint->cpus becomes 0), split() returns true.
 
   bool split(const Position& p, SearchStack* sstck, int ply,
-             Value* alpha, Value* beta, Value* bestValue, Depth depth, int* moves,
+             Value* alpha, Value* beta, Value* bestValue, const Value futilityValue,
+             const Value approximateEval, Depth depth, int* moves,
              MovePicker* mp, Bitboard dcCandidates, int master, bool pvNode) {
 
     assert(p.is_ok());
@@ -2808,6 +2829,8 @@ namespace {
     splitPoint->pvNode = pvNode;
     splitPoint->dcCandidates = dcCandidates;
     splitPoint->bestValue = *bestValue;
+    splitPoint->futilityValue = futilityValue;
+    splitPoint->approximateEval = approximateEval;
     splitPoint->master = master;
     splitPoint->mp = mp;
     splitPoint->moves = *moves;