Implement a fallback system when aspiration search fails low and we are out of time.
authorJoona Kiiski <joona.kiiski@gmail.com>
Sun, 12 Apr 2009 20:25:05 +0000 (23:25 +0300)
committerMarco Costalba <mcostalba@gmail.com>
Sat, 18 Apr 2009 08:11:15 +0000 (09:11 +0100)
However also this patch is immediately reverted. For three reasons:
1) the case it affects is very rare (and then we are likely to lose anyway),
   so we can well live without this.

2) Because the case is so rare it's hard to test this change properly.

3) To perform fallback search, we must reset so many global variables that this
   patch is very likely both buggy and extremely bad style.

Consider including this again if we clean-up global variables one day...

Signed-off-by: Marco Costalba <mcostalba@gmail.com>
src/search.cpp

index b8d6a3a58ef7d3f6f953eca5f0665cec2a1b0cc6..76b79dda74cb189693857247157ac21600e2fb1f 100644 (file)
@@ -259,7 +259,7 @@ namespace {
   // Time managment variables
   int SearchStartTime;
   int MaxNodes, MaxDepth;
-  int MaxSearchTime, AbsoluteMaxSearchTime, ExtraSearchTime;
+  int MaxSearchTime, AbsoluteMaxSearchTime, EmergencyMaxSearchTime, ExtraSearchTime;
   Move EasyMove;
   int RootMoveNumber;
   bool InfiniteSearch;
@@ -520,9 +520,11 @@ void think(const Position &pos, bool infinite, bool ponder, int side_to_move,
       {
           MaxSearchTime = myTime / 30 + myIncrement;
           AbsoluteMaxSearchTime = Max(myTime / 4, myIncrement - 100);
+          EmergencyMaxSearchTime = Max(myTime / 2, myIncrement - 100);
       } else { // Blitz game without increment
           MaxSearchTime = myTime / 30;
           AbsoluteMaxSearchTime = myTime / 8;
+          EmergencyMaxSearchTime = myTime / 4;
       }
   }
   else // (x moves) / (y minutes)
@@ -531,9 +533,11 @@ void think(const Position &pos, bool infinite, bool ponder, int side_to_move,
       {
           MaxSearchTime = myTime / 2;
           AbsoluteMaxSearchTime = Min(myTime / 2, myTime - 500);
+          EmergencyMaxSearchTime = myTime - 500;
       } else {
           MaxSearchTime = myTime / Min(movesToGo, 20);
           AbsoluteMaxSearchTime = Min((4 * myTime) / movesToGo, myTime / 3);
+          EmergencyMaxSearchTime = Min((8 * myTime) / movesToGo, myTime / 2);
       }
   }
 
@@ -700,6 +704,9 @@ namespace {
     Position p(pos);
     SearchStack ss[PLY_MAX_PLUS_2];
 
+    Value alpha;
+    Value beta;
+
     // searchMoves are verified, copied, scored and sorted
     RootMoveList rml(p, searchMoves);
 
@@ -729,9 +736,6 @@ namespace {
         std::cout << "info depth " << Iteration << std::endl;
 
         //Calculate dynamic search window based on previous iterations.
-        Value alpha;
-        Value beta;
-
         if (MultiPV == 1 && Iteration >= 6) {
           Value prevDelta1 = IterationInfo[Iteration - 1].speculated_value() - IterationInfo[Iteration - 2].speculated_value();
           Value prevDelta2 = IterationInfo[Iteration - 2].speculated_value() - IterationInfo[Iteration - 3].speculated_value();
@@ -750,13 +754,14 @@ namespace {
 
         // Search to the current depth
         Value value = root_search(p, ss, rml, alpha, beta);
-        if (AbortSearch)
-          break; //Value cannot be trusted. Break out immediately!
 
         // Write PV to transposition table, in case the relevant entries have
         // been overwritten during the search:
         TT.insert_pv(p, ss[0].pv);
 
+        if (AbortSearch)
+          break; //Value cannot be trusted. Break out immediately!
+
         //Save info about search result
         Value speculated_value = value;
         bool fHigh = false;
@@ -826,7 +831,6 @@ namespace {
 
             if (stopSearch)
             {
-                //FIXME: Implement fail-low emergency measures
                 if (!PonderSearch)
                     break;
                 else
@@ -838,6 +842,34 @@ namespace {
             break;
     }
 
+    if (FailLow)
+    {
+      //Here we face the rare, but extremely difficult case:
+      //Our aspiration search has failed low and we've run out of time!
+      //So we have no move to play!
+      //Now use the emergency time and try as quickly as possible to
+      //find even one playable move.
+
+      //FIXME: this is only for grepping logs purpose. Remove me when we are sure that this stuff really works!!
+      if (AbortSearch)
+        std::cout << "info depth " << 999 << std::endl;
+      else
+        std::cout << "info depth " << 998 << std::endl;
+
+      //Prepare variables for emergency search
+      AbortSearch = false;
+      FailLow = false;
+      AbsoluteMaxSearchTime = EmergencyMaxSearchTime;
+      MaxSearchTime = EmergencyMaxSearchTime;
+      ExtraSearchTime = 0;
+      rml.sort();
+
+      std::cout << "info depth " << Iteration << std::endl;
+
+     //Cause we failed low, it's _likely_ that we couldn't get over alpha anyway.
+      root_search(p, ss, rml, -VALUE_INFINITE, alpha);
+    }
+
     rml.sort();
 
     // If we are pondering, we shouldn't print the best move before we
@@ -891,7 +923,6 @@ namespace {
 
   Value root_search(Position &pos, SearchStack ss[], RootMoveList &rml, Value alpha, Value beta) {
 
-    //FIXME: Implement bestValue
     Value oldAlpha = alpha;
     Value value;
     Bitboard dcCandidates = pos.discovered_check_candidates(pos.side_to_move());