Convert killers to a vector

[stockfish] / src / search.cpp

diff --git a/src/search.cpp b/src/search.cpp
index 02907a80f9d63dcc883a508c6791f76fd7660bfa..a4ea9aa4b36e455057c66aa6934b99896fe62dca 100644 (file)
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -144,7 +144,7 @@ namespace {
   bool UseFutilityPruning = true;
 
   // Margins for futility pruning in the quiescence search, at frontier
   bool UseFutilityPruning = true;
 
   // Margins for futility pruning in the quiescence search, at frontier

-  // nodes, and at pre-frontier nodes:
+  // nodes, and at pre-frontier nodes

   Value FutilityMargin0 = Value(0x80);
   Value FutilityMargin1 = Value(0x100);
   Value FutilityMargin2 = Value(0x300);
   Value FutilityMargin0 = Value(0x80);
   Value FutilityMargin1 = Value(0x100);
   Value FutilityMargin2 = Value(0x300);


@@ -167,21 +167,22 @@ namespace {
   Depth PawnEndgameExtension[2] = {OnePly, OnePly};
   Depth MateThreatExtension[2] = {Depth(0), Depth(0)};
 
   Depth PawnEndgameExtension[2] = {OnePly, OnePly};
   Depth MateThreatExtension[2] = {Depth(0), Depth(0)};
 

-  // Search depth at iteration 1:
+  // Search depth at iteration 1

   const Depth InitialDepth = OnePly /*+ OnePly/2*/;
 
   // Node counters
   int NodesSincePoll;
   int NodesBetweenPolls = 30000;
 
   const Depth InitialDepth = OnePly /*+ OnePly/2*/;
 
   // Node counters
   int NodesSincePoll;
   int NodesBetweenPolls = 30000;
 

-  // Iteration counter:
+  // Iteration counter

   int Iteration;
   int Iteration;

+  bool LastIterations;

 
   // Scores and number of times the best move changed for each iteration:
   Value ValueByIteration[PLY_MAX_PLUS_2];
   int BestMoveChangesByIteration[PLY_MAX_PLUS_2];
 
 
   // Scores and number of times the best move changed for each iteration:
   Value ValueByIteration[PLY_MAX_PLUS_2];
   int BestMoveChangesByIteration[PLY_MAX_PLUS_2];
 

-  // MultiPV mode:
+  // MultiPV mode

   int MultiPV = 1;
 
   // Time managment variables
   int MultiPV = 1;
 
   // Time managment variables


@@ -237,6 +238,7 @@ namespace {
                 Depth depth, int ply, int threadID);
   void sp_search(SplitPoint *sp, int threadID);
   void sp_search_pv(SplitPoint *sp, int threadID);
                 Depth depth, int ply, int threadID);
   void sp_search(SplitPoint *sp, int threadID);
   void sp_search_pv(SplitPoint *sp, int threadID);

+  void init_search_stack(SearchStack ss);

   void init_search_stack(SearchStack ss[]);
   void init_node(const Position &pos, SearchStack ss[], int ply, int threadID);
   void update_pv(SearchStack ss[], int ply);
   void init_search_stack(SearchStack ss[]);
   void init_node(const Position &pos, SearchStack ss[], int ply, int threadID);
   void update_pv(SearchStack ss[], int ply);


@@ -297,6 +299,9 @@ Lock IOLock;
 
 History H;  // Should be made local?
 
 
 History H;  // Should be made local?
 

+// The empty search stack
+SearchStack EmptySearchStack;
+

 
 ////
 //// Functions
 
 ////
 //// Functions


@@ -561,6 +566,9 @@ void init_threads() {
       // Wait until the thread has finished launching:
       while (!Threads[i].running);
   }
       // Wait until the thread has finished launching:
       while (!Threads[i].running);
   }

+
+  // Init also the empty search stack
+  init_search_stack(EmptySearchStack);

 }
 
 
 }
 
 


@@ -617,6 +625,7 @@ namespace {
     ValueByIteration[0] = Value(0);
     ValueByIteration[1] = rml.get_move_score(0);
     Iteration = 1;
     ValueByIteration[0] = Value(0);
     ValueByIteration[1] = rml.get_move_score(0);
     Iteration = 1;

+    LastIterations = false;

 
     EasyMove = rml.scan_for_easy_move();
 
 
     EasyMove = rml.scan_for_easy_move();
 


@@ -675,6 +684,9 @@ namespace {
             if (ExtraSearchTime > 0 && TimeAdvantage > 2 * MaxSearchTime)
                 ExtraSearchTime += MaxSearchTime / 2;
 
             if (ExtraSearchTime > 0 && TimeAdvantage > 2 * MaxSearchTime)
                 ExtraSearchTime += MaxSearchTime / 2;
 

+            // Try to guess if the current iteration is the last one or the last two
+            LastIterations = (current_search_time() > ((MaxSearchTime + ExtraSearchTime)*58) / 128);
+

             // Stop search if most of MaxSearchTime is consumed at the end of the
             // iteration.  We probably don't have enough time to search the first
             // move at the next iteration anyway.
             // Stop search if most of MaxSearchTime is consumed at the end of the
             // iteration.  We probably don't have enough time to search the first
             // move at the next iteration anyway.


@@ -933,8 +945,7 @@ namespace {
 
     // Initialize a MovePicker object for the current position, and prepare
     // to search all moves
 
     // Initialize a MovePicker object for the current position, and prepare
     // to search all moves

-    MovePicker mp = MovePicker(pos, true, ttMove, ss[ply].mateKiller,
-                               ss[ply].killer1, ss[ply].killer2, depth);
+    MovePicker mp = MovePicker(pos, true, ttMove, ss[ply], depth);

 
     Move move, movesSearched[256];
     int moveCount = 0;
 
     Move move, movesSearched[256];
     int moveCount = 0;


@@ -960,11 +971,11 @@ namespace {
       movesSearched[moveCount++] = ss[ply].currentMove = move;
 
       if (moveIsCapture)
       movesSearched[moveCount++] = ss[ply].currentMove = move;
 
       if (moveIsCapture)

-          ss[ply].currentMoveCaptureValue =  pos.midgame_value_of_piece_on(move_to(move));
+          ss[ply].currentMoveCaptureValue = pos.midgame_value_of_piece_on(move_to(move));

       else if (move_is_ep(move))
       else if (move_is_ep(move))

-          ss[ply].currentMoveCaptureValue =  PawnValueMidgame;
+          ss[ply].currentMoveCaptureValue = PawnValueMidgame;

       else
       else

-          ss[ply].currentMoveCaptureValue =  Value(0);
+          ss[ply].currentMoveCaptureValue = Value(0);

 
       // Decide the new search depth
       Depth ext = extension(pos, move, true, moveIsCheck, singleReply, mateThreat);
 
       // Decide the new search depth
       Depth ext = extension(pos, move, true, moveIsCheck, singleReply, mateThreat);


@@ -987,8 +998,8 @@ namespace {
             && !move_promotion(move)
             && !moveIsPassedPawnPush
             && !move_is_castle(move)
             && !move_promotion(move)
             && !moveIsPassedPawnPush
             && !move_is_castle(move)

-            &&  move != ss[ply].killer1
-            &&  move != ss[ply].killer2)
+            &&  move != ss[ply].killers[0]
+            &&  move != ss[ply].killers[1])

         {
             ss[ply].reduction = OnePly;
             value = -search(pos, ss, -alpha, newDepth-OnePly, ply+1, true, threadID);
         {
             ss[ply].reduction = OnePly;
             value = -search(pos, ss, -alpha, newDepth-OnePly, ply+1, true, threadID);


@@ -1070,10 +1081,10 @@ namespace {
         if (ok_to_history(pos, m)) // Only non capture moves are considered
         {
             update_history(pos, m, depth, movesSearched, moveCount);
         if (ok_to_history(pos, m)) // Only non capture moves are considered
         {
             update_history(pos, m, depth, movesSearched, moveCount);

-            if (m != ss[ply].killer1)
+            if (m != ss[ply].killers[0])

             {
             {

-                ss[ply].killer2 = ss[ply].killer1;
-                ss[ply].killer1 = m;
+                ss[ply].killers[1] = ss[ply].killers[0];
+                ss[ply].killers[0] = m;

             }
         }
         TT.store(pos, value_to_tt(bestValue, ply), depth, m, VALUE_TYPE_LOWER);
             }
         }
         TT.store(pos, value_to_tt(bestValue, ply), depth, m, VALUE_TYPE_LOWER);


@@ -1143,7 +1154,8 @@ namespace {
 
         UndoInfo u;
         pos.do_null_move(u);
 
         UndoInfo u;
         pos.do_null_move(u);

-        Value nullValue = -search(pos, ss, -(beta-1), depth-4*OnePly, ply+1, false, threadID);
+        int R = (depth > 7 ? 4 : 3);
+        Value nullValue = -search(pos, ss, -(beta-1), depth-R*OnePly, ply+1, false, threadID);

         pos.undo_null_move(u);
 
         if (nullValue >= beta)
         pos.undo_null_move(u);
 
         if (nullValue >= beta)


@@ -1191,8 +1203,7 @@ namespace {
 
     // Initialize a MovePicker object for the current position, and prepare
     // to search all moves:
 
     // Initialize a MovePicker object for the current position, and prepare
     // to search all moves:

-    MovePicker mp = MovePicker(pos, false, ttMove, ss[ply].mateKiller,
-                               ss[ply].killer1, ss[ply].killer2, depth);
+    MovePicker mp = MovePicker(pos, false, ttMove, ss[ply], depth);

 
     Move move, movesSearched[256];
     int moveCount = 0;
 
     Move move, movesSearched[256];
     int moveCount = 0;


@@ -1261,8 +1272,8 @@ namespace {
           && !move_promotion(move)
           && !moveIsPassedPawnPush
           && !move_is_castle(move)
           && !move_promotion(move)
           && !moveIsPassedPawnPush
           && !move_is_castle(move)

-          &&  move != ss[ply].killer1
-          &&  move != ss[ply].killer2)
+          &&  move != ss[ply].killers[0]
+          &&  move != ss[ply].killers[1])

       {
           ss[ply].reduction = OnePly;
           value = -search(pos, ss, -(beta-1), newDepth-OnePly, ply+1, true, threadID);
       {
           ss[ply].reduction = OnePly;
           value = -search(pos, ss, -(beta-1), newDepth-OnePly, ply+1, true, threadID);


@@ -1321,10 +1332,10 @@ namespace {
         if (ok_to_history(pos, m)) // Only non capture moves are considered
         {
             update_history(pos, m, depth, movesSearched, moveCount);
         if (ok_to_history(pos, m)) // Only non capture moves are considered
         {
             update_history(pos, m, depth, movesSearched, moveCount);

-            if (m != ss[ply].killer1)
+            if (m != ss[ply].killers[0])

             {
             {

-                ss[ply].killer2 = ss[ply].killer1;
-                ss[ply].killer1 = m;
+                ss[ply].killers[1] = ss[ply].killers[0];
+                ss[ply].killers[0] = m;

             }
         }
         TT.store(pos, value_to_tt(bestValue, ply), depth, m, VALUE_TYPE_LOWER);
             }
         }
         TT.store(pos, value_to_tt(bestValue, ply), depth, m, VALUE_TYPE_LOWER);


@@ -1382,12 +1393,13 @@ namespace {
     // Initialize a MovePicker object for the current position, and prepare
     // to search the moves.  Because the depth is <= 0 here, only captures,
     // queen promotions and checks (only if depth == 0) will be generated.
     // Initialize a MovePicker object for the current position, and prepare
     // to search the moves.  Because the depth is <= 0 here, only captures,
     // queen promotions and checks (only if depth == 0) will be generated.

-    MovePicker mp = MovePicker(pos, false, MOVE_NONE, MOVE_NONE, MOVE_NONE,
-                               MOVE_NONE, depth);
+    MovePicker mp = MovePicker(pos, false, MOVE_NONE, EmptySearchStack, depth, &ei);

     Move move;
     int moveCount = 0;
     Bitboard dcCandidates = mp.discovered_check_candidates();
     bool isCheck = pos.is_check();
     Move move;
     int moveCount = 0;
     Bitboard dcCandidates = mp.discovered_check_candidates();
     bool isCheck = pos.is_check();

+    bool pvNode = (beta - alpha != 1);
+    bool enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMidgame;

 
     // Loop through the moves until no moves remain or a beta cutoff
     // occurs.
 
     // Loop through the moves until no moves remain or a beta cutoff
     // occurs.


@@ -1408,8 +1420,8 @@ namespace {
           && !moveIsCheck
           && !move_promotion(move)
           && !moveIsPassedPawnPush
           && !moveIsCheck
           && !move_promotion(move)
           && !moveIsPassedPawnPush

-          &&  beta - alpha == 1
-          &&  pos.non_pawn_material(pos.side_to_move()) > RookValueMidgame)
+          && !pvNode
+          &&  enoughMaterial)

       {
           Value futilityValue = staticValue
                               + Max(pos.midgame_value_of_piece_on(move_to(move)),
       {
           Value futilityValue = staticValue
                               + Max(pos.midgame_value_of_piece_on(move_to(move)),


@@ -1425,9 +1437,10 @@ namespace {
           }
       }
 
           }
       }
 

-      // Don't search captures and checks with negative SEE values.
+      // Don't search captures and checks with negative SEE values

       if (   !isCheck
           && !move_promotion(move)
       if (   !isCheck
           && !move_promotion(move)

+          && !pvNode

           && (pos.midgame_value_of_piece_on(move_from(move)) >
               pos.midgame_value_of_piece_on(move_to(move)))
           &&  pos.see(move) < 0)
           && (pos.midgame_value_of_piece_on(move_from(move)) >
               pos.midgame_value_of_piece_on(move_to(move)))
           &&  pos.see(move) < 0)


@@ -1463,6 +1476,18 @@ namespace {
     // Update transposition table
     TT.store(pos, value_to_tt(bestValue, ply), depth, MOVE_NONE, VALUE_TYPE_EXACT);
 
     // Update transposition table
     TT.store(pos, value_to_tt(bestValue, ply), depth, MOVE_NONE, VALUE_TYPE_EXACT);
 

+    // Update killers only for good check moves
+    Move m = ss[ply].currentMove;
+    if (alpha >= beta && ok_to_history(pos, m)) // Only non capture moves are considered
+    {
+        // Wrong to update history when depth is <= 0
+
+        if (m != ss[ply].killers[0])
+        {
+            ss[ply].killers[1] = ss[ply].killers[0];
+            ss[ply].killers[0] = m;
+        }
+    }

     return bestValue;
   }
 
     return bestValue;
   }
 


@@ -1531,8 +1556,8 @@ namespace {
           && !moveIsPassedPawnPush
           && !move_promotion(move)
           && !move_is_castle(move)
           && !moveIsPassedPawnPush
           && !move_promotion(move)
           && !move_is_castle(move)

-          &&  move != ss[sp->ply].killer1
-          &&  move != ss[sp->ply].killer2)
+          &&  move != ss[sp->ply].killers[0]
+          &&  move != ss[sp->ply].killers[1])

       {
           ss[sp->ply].reduction = OnePly;
           value = -search(pos, ss, -(sp->beta-1), newDepth - OnePly, sp->ply+1, true, threadID);
       {
           ss[sp->ply].reduction = OnePly;
           value = -search(pos, ss, -(sp->beta-1), newDepth - OnePly, sp->ply+1, true, threadID);


@@ -1639,8 +1664,8 @@ namespace {
           && !moveIsPassedPawnPush
           && !move_promotion(move)
           && !move_is_castle(move)
           && !moveIsPassedPawnPush
           && !move_promotion(move)
           && !move_is_castle(move)

-          &&  move != ss[sp->ply].killer1
-          &&  move != ss[sp->ply].killer2)
+          &&  move != ss[sp->ply].killers[0]
+          &&  move != ss[sp->ply].killers[1])

       {
           ss[sp->ply].reduction = OnePly;
           value = -search(pos, ss, -sp->alpha, newDepth - OnePly, sp->ply+1, true, threadID);
       {
           ss[sp->ply].reduction = OnePly;
           value = -search(pos, ss, -sp->alpha, newDepth - OnePly, sp->ply+1, true, threadID);


@@ -1871,17 +1896,28 @@ namespace {
 
   // init_search_stack() initializes a search stack at the beginning of a
   // new search from the root.
 
   // init_search_stack() initializes a search stack at the beginning of a
   // new search from the root.

+  void init_search_stack(SearchStack ss) {
+
+    ss.pv[0] = MOVE_NONE;
+    ss.pv[1] = MOVE_NONE;
+    ss.currentMove = MOVE_NONE;
+    ss.threatMove = MOVE_NONE;
+    ss.reduction = Depth(0);
+    for (int j = 0; j < KILLER_MAX; j++)
+        ss.killers[j] = MOVE_NONE;    
+  }

 
   void init_search_stack(SearchStack ss[]) {
 
   void init_search_stack(SearchStack ss[]) {

-    for(int i = 0; i < 3; i++) {
-      ss[i].pv[i] = MOVE_NONE;
-      ss[i].pv[i+1] = MOVE_NONE;
-      ss[i].currentMove = MOVE_NONE;
-      ss[i].mateKiller = MOVE_NONE;
-      ss[i].killer1 = MOVE_NONE;
-      ss[i].killer2 = MOVE_NONE;
-      ss[i].threatMove = MOVE_NONE;
-      ss[i].reduction = Depth(0);
+
+    for (int i = 0; i < 3; i++)
+    {
+        ss[i].pv[i] = MOVE_NONE;
+        ss[i].pv[i+1] = MOVE_NONE;
+        ss[i].currentMove = MOVE_NONE;
+        ss[i].threatMove = MOVE_NONE;
+        ss[i].reduction = Depth(0);
+        for (int j = 0; j < KILLER_MAX; j++)
+            ss[i].killers[j] = MOVE_NONE;

     }
   }
 
     }
   }
 


@@ -1908,7 +1944,7 @@ namespace {
 
     ss[ply].pv[ply] = ss[ply].pv[ply+1] = ss[ply].currentMove = MOVE_NONE;
     ss[ply+2].mateKiller = MOVE_NONE;
 
     ss[ply].pv[ply] = ss[ply].pv[ply+1] = ss[ply].currentMove = MOVE_NONE;
     ss[ply+2].mateKiller = MOVE_NONE;

-    ss[ply+2].killer1 = ss[ply+2].killer2 = MOVE_NONE;
+    ss[ply+2].killers[0] = ss[ply+2].killers[1] = MOVE_NONE;

     ss[ply].threatMove = MOVE_NONE;
     ss[ply].reduction = Depth(0);
     ss[ply].currentMoveCaptureValue = Value(0);
     ss[ply].threatMove = MOVE_NONE;
     ss[ply].reduction = Depth(0);
     ss[ply].currentMoveCaptureValue = Value(0);


@@ -2038,9 +2074,9 @@ namespace {
     if (mateThreat)
         result += MateThreatExtension[pvNode];
 
     if (mateThreat)
         result += MateThreatExtension[pvNode];
 

-    if (   pos.midgame_value_of_piece_on(move_to(m)) >= RookValueMidgame\r
-        && (  pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK)\r
-            - pos.midgame_value_of_piece_on(move_to(m)) == Value(0))\r
+    if (   pos.midgame_value_of_piece_on(move_to(m)) >= RookValueMidgame
+        && (  pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK)
+            - pos.midgame_value_of_piece_on(move_to(m)) == Value(0))

         && !move_promotion(m))
         result += PawnEndgameExtension[pvNode];
     
         && !move_promotion(m))
         result += PawnEndgameExtension[pvNode];
     


@@ -2137,13 +2173,11 @@ namespace {
 
 
   // ok_to_history() returns true if a move m can be stored
 
 
   // ok_to_history() returns true if a move m can be stored

-  // in history. Should be a non capturing move.
+  // in history. Should be a non capturing move nor a promotion.

 
   bool ok_to_history(const Position& pos, Move m) {
 
 
   bool ok_to_history(const Position& pos, Move m) {
 

-    return    pos.square_is_empty(move_to(m))
-          && !move_promotion(m)
-          && !move_is_ep(m);
+    return !pos.move_is_capture(m) && !move_promotion(m);

   }
 
 
   }
 
 


@@ -2156,8 +2190,11 @@ namespace {
     H.success(pos.piece_on(move_from(m)), m, depth);
 
     for (int i = 0; i < moveCount - 1; i++)
     H.success(pos.piece_on(move_from(m)), m, depth);
 
     for (int i = 0; i < moveCount - 1; i++)

-        if (ok_to_history(pos, movesSearched[i]) && m != movesSearched[i])
+    {
+        assert(m != movesSearched[i]);
+        if (ok_to_history(pos, movesSearched[i]))

             H.failure(pos.piece_on(move_from(movesSearched[i])), movesSearched[i]);
             H.failure(pos.piece_on(move_from(movesSearched[i])), movesSearched[i]);

+    }

   }
 
   // fail_high_ply_1() checks if some thread is currently resolving a fail
   }
 
   // fail_high_ply_1() checks if some thread is currently resolving a fail