Introduce 'follow up' moves

When we have a fail-high of a quiet move, store it in
a Followupmoves table indexed by the previous move of
the same color (instead of immediate previous move as
is in countermoves case).

Then use this table for quiet moves ordering in the same
way we are already doing with countermoves.

These followup moves will be tried just after countermoves
and before remaining quiet moves.

Passed both short TC
LLR: 2.95 (-2.94,2.94) [-1.50,4.50]
Total: 10350 W: 1998 L: 1866 D: 6486

And long TC
LLR: 2.95 (-2.94,2.94) [0.00,6.00]
Total: 14066 W: 2303 L: 2137 D: 9626

bench: 7205153

diff --git a/src/movepick.cpp b/src/movepick.cpp
index ba30a2bcded328e13288fc1422ced52193779d34..2a57605e164fa0ceeb5c34f2e26bce6cc2af8a5b 100644 (file)
--- a/src/movepick.cpp
+++ b/src/movepick.cpp
@@ -71,13 +71,14 @@ namespace {
 /// ordering is at the current node.
 
 MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const HistoryStats& h,
 /// ordering is at the current node.
 
 MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const HistoryStats& h,

-                       Move* cm, Search::Stack* s) : pos(p), history(h), depth(d) {
+                       Move* cm, Move* fm, Search::Stack* s) : pos(p), history(h), depth(d) {

 
   assert(d > DEPTH_ZERO);
 
   cur = end = moves;
   endBadCaptures = moves + MAX_MOVES - 1;
   countermoves = cm;
 
   assert(d > DEPTH_ZERO);
 
   cur = end = moves;
   endBadCaptures = moves + MAX_MOVES - 1;
   countermoves = cm;

+  followupmoves = fm;

   ss = s;
 
   if (p.checkers())
   ss = s;
 
   if (p.checkers())


@@ -230,15 +231,28 @@ void MovePicker::generate_next() {
       killers[0].move = ss->killers[0];
       killers[1].move = ss->killers[1];
       killers[2].move = killers[3].move = MOVE_NONE;
       killers[0].move = ss->killers[0];
       killers[1].move = ss->killers[1];
       killers[2].move = killers[3].move = MOVE_NONE;

+      killers[4].move = killers[5].move = MOVE_NONE;

 
       // Be sure countermoves are different from killers
       for (int i = 0; i < 2; ++i)
 
       // Be sure countermoves are different from killers
       for (int i = 0; i < 2; ++i)

-          if (countermoves[i] != cur->move && countermoves[i] != (cur+1)->move)
+          if (   countermoves[i] != (cur+0)->move
+              && countermoves[i] != (cur+1)->move)

               (end++)->move = countermoves[i];
 
       if (countermoves[1] && countermoves[1] == countermoves[0]) // Due to SMP races
           killers[3].move = MOVE_NONE;
 
               (end++)->move = countermoves[i];
 
       if (countermoves[1] && countermoves[1] == countermoves[0]) // Due to SMP races
           killers[3].move = MOVE_NONE;
 

+      // Be sure followupmoves are different from killers and countermoves
+      for (int i = 0; i < 2; ++i)
+          if (   followupmoves[i] != (cur+0)->move
+              && followupmoves[i] != (cur+1)->move
+              && followupmoves[i] != (cur+2)->move
+              && followupmoves[i] != (cur+3)->move)
+              (end++)->move = followupmoves[i];
+
+      if (followupmoves[1] && followupmoves[1] == followupmoves[0]) // Due to SMP races
+          (--end)->move = MOVE_NONE;
+

       return;
 
   case QUIETS_1_S1:
       return;
 
   case QUIETS_1_S1:


@@ -330,7 +344,9 @@ Move MovePicker::next_move<false>() {
               && move != killers[0].move
               && move != killers[1].move
               && move != killers[2].move
               && move != killers[0].move
               && move != killers[1].move
               && move != killers[2].move

-              && move != killers[3].move)
+              && move != killers[3].move
+              && move != killers[4].move
+              && move != killers[5].move)

               return move;
           break;
 
               return move;
           break;
 

diff --git a/src/movepick.h b/src/movepick.h
index 96986c84658723667b024f90627d3f221e24573f..21ea9ab3e2292afc1835059cbdfaf8ed74128892 100644 (file)
--- a/src/movepick.h
+++ b/src/movepick.h
@@ -69,7 +69,7 @@ private:
 
 typedef Stats< true, Value> GainsStats;
 typedef Stats<false, Value> HistoryStats;
 
 typedef Stats< true, Value> GainsStats;
 typedef Stats<false, Value> HistoryStats;

-typedef Stats<false, std::pair<Move, Move> > CountermovesStats;
+typedef Stats<false, std::pair<Move, Move> > MovesStats;

 
 
 /// MovePicker class is used to pick one pseudo legal move at a time from the
 
 
 /// MovePicker class is used to pick one pseudo legal move at a time from the


@@ -86,7 +86,7 @@ class MovePicker {
 public:
   MovePicker(const Position&, Move, Depth, const HistoryStats&, Square);
   MovePicker(const Position&, Move, const HistoryStats&, PieceType);
 public:
   MovePicker(const Position&, Move, Depth, const HistoryStats&, Square);
   MovePicker(const Position&, Move, const HistoryStats&, PieceType);

-  MovePicker(const Position&, Move, Depth, const HistoryStats&, Move*, Search::Stack*);
+  MovePicker(const Position&, Move, Depth, const HistoryStats&, Move*, Move*, Search::Stack*);

 
   template<bool SpNode> Move next_move();
 
 
   template<bool SpNode> Move next_move();
 


@@ -98,9 +98,10 @@ private:
   const HistoryStats& history;
   Search::Stack* ss;
   Move* countermoves;
   const HistoryStats& history;
   Search::Stack* ss;
   Move* countermoves;

+  Move* followupmoves;

   Depth depth;
   Move ttMove;
   Depth depth;
   Move ttMove;

-  ExtMove killers[4];
+  ExtMove killers[6];

   Square recaptureSquare;
   int captureThreshold, stage;
   ExtMove *cur, *end, *endQuiets, *endBadCaptures;
   Square recaptureSquare;
   int captureThreshold, stage;
   ExtMove *cur, *end, *endQuiets, *endBadCaptures;

diff --git a/src/search.cpp b/src/search.cpp
index a08256d740953b00caeb0eca075ade01e33679bb..d59fc521eedcba2815ae3cdeaf92f4bdb6e80730 100644 (file)
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -83,7 +83,7 @@ namespace {
   Value DrawValue[COLOR_NB];
   HistoryStats History;
   GainsStats Gains;
   Value DrawValue[COLOR_NB];
   HistoryStats History;
   GainsStats Gains;

-  CountermovesStats Countermoves;
+  MovesStats Countermoves, Followupmoves;

 
   template <NodeType NT>
   Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode);
 
   template <NodeType NT>
   Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode);


@@ -304,6 +304,7 @@ namespace {
     History.clear();
     Gains.clear();
     Countermoves.clear();
     History.clear();
     Gains.clear();
     Countermoves.clear();

+    Followupmoves.clear();

 
     PVSize = Options["MultiPV"];
     Skill skill(Options["Skill Level"]);
 
     PVSize = Options["MultiPV"];
     Skill skill(Options["Skill Level"]);


@@ -499,7 +500,7 @@ namespace {
 
     moveCount = quietCount = 0;
     bestValue = -VALUE_INFINITE;
 
     moveCount = quietCount = 0;
     bestValue = -VALUE_INFINITE;

-    ss->currentMove = (ss+1)->excludedMove = bestMove = MOVE_NONE;
+    ss->currentMove = ss->ttMove = (ss+1)->excludedMove = bestMove = MOVE_NONE;

     ss->ply = (ss-1)->ply + 1;
     (ss+1)->skipNullMove = false; (ss+1)->reduction = DEPTH_ZERO;
     (ss+2)->killers[0] = (ss+2)->killers[1] = MOVE_NONE;
     ss->ply = (ss-1)->ply + 1;
     (ss+1)->skipNullMove = false; (ss+1)->reduction = DEPTH_ZERO;
     (ss+2)->killers[0] = (ss+2)->killers[1] = MOVE_NONE;


@@ -532,7 +533,7 @@ namespace {
     excludedMove = ss->excludedMove;
     posKey = excludedMove ? pos.exclusion_key() : pos.key();
     tte = TT.probe(posKey);
     excludedMove = ss->excludedMove;
     posKey = excludedMove ? pos.exclusion_key() : pos.key();
     tte = TT.probe(posKey);

-    ttMove = RootNode ? RootMoves[PVIdx].pv[0] : tte ? tte->move() : MOVE_NONE;
+    ss->ttMove = ttMove = RootNode ? RootMoves[PVIdx].pv[0] : tte ? tte->move() : MOVE_NONE;

     ttValue = tte ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE;
 
     // At PV nodes we check for exact scores, whilst at non-PV nodes we check for
     ttValue = tte ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE;
 
     // At PV nodes we check for exact scores, whilst at non-PV nodes we check for


@@ -550,7 +551,7 @@ namespace {
         TT.refresh(tte);
         ss->currentMove = ttMove; // Can be MOVE_NONE
 
         TT.refresh(tte);
         ss->currentMove = ttMove; // Can be MOVE_NONE
 

-        // If ttMove is quiet, update killers, history, and counter move on TT hit
+        // If ttMove is quiet, update killers, history, counter move and followup move on TT hit

         if (ttValue >= beta && ttMove && !pos.capture_or_promotion(ttMove) && !inCheck)
             update_stats(pos, ss, ttMove, depth, NULL, 0);
 
         if (ttValue >= beta && ttMove && !pos.capture_or_promotion(ttMove) && !inCheck)
             update_stats(pos, ss, ttMove, depth, NULL, 0);
 


@@ -712,7 +713,11 @@ moves_loop: // When in check and at SpNode search starts from here
     Move countermoves[] = { Countermoves[pos.piece_on(prevMoveSq)][prevMoveSq].first,
                             Countermoves[pos.piece_on(prevMoveSq)][prevMoveSq].second };
 
     Move countermoves[] = { Countermoves[pos.piece_on(prevMoveSq)][prevMoveSq].first,
                             Countermoves[pos.piece_on(prevMoveSq)][prevMoveSq].second };
 

-    MovePicker mp(pos, ttMove, depth, History, countermoves, ss);
+    Square prevOwnMoveSq = to_sq((ss-2)->currentMove);
+    Move followupmoves[] = { Followupmoves[pos.piece_on(prevOwnMoveSq)][prevOwnMoveSq].first,
+                             Followupmoves[pos.piece_on(prevOwnMoveSq)][prevOwnMoveSq].second };
+
+    MovePicker mp(pos, ttMove, depth, History, countermoves, followupmoves, ss);

     CheckInfo ci(pos);
     value = bestValue; // Workaround a bogus 'uninitialized' warning under gcc
     improving =   ss->staticEval >= (ss-2)->staticEval
     CheckInfo ci(pos);
     value = bestValue; // Workaround a bogus 'uninitialized' warning under gcc
     improving =   ss->staticEval >= (ss-2)->staticEval


@@ -1029,7 +1034,7 @@ moves_loop: // When in check and at SpNode search starts from here
              PvNode && bestMove ? BOUND_EXACT : BOUND_UPPER,
              depth, bestMove, ss->staticEval);
 
              PvNode && bestMove ? BOUND_EXACT : BOUND_UPPER,
              depth, bestMove, ss->staticEval);
 

-    // Quiet best move: update killers, history and countermoves
+    // Quiet best move: update killers, history, countermoves and followupmoves

     if (bestValue >= beta && !pos.capture_or_promotion(bestMove) && !inCheck)
         update_stats(pos, ss, bestMove, depth, quietsSearched, quietCount - 1);
 
     if (bestValue >= beta && !pos.capture_or_promotion(bestMove) && !inCheck)
         update_stats(pos, ss, bestMove, depth, quietsSearched, quietCount - 1);
 


@@ -1264,7 +1269,7 @@ moves_loop: // When in check and at SpNode search starts from here
   }
 
 
   }
 
 

-  // update_stats() updates killers, history and countermoves stats after a fail-high
+  // update_stats() updates killers, history, countermoves and followupmoves stats after a fail-high

   // of a quiet move.
 
   void update_stats(Position& pos, Stack* ss, Move move, Depth depth, Move* quiets, int quietsCnt) {
   // of a quiet move.
 
   void update_stats(Position& pos, Stack* ss, Move move, Depth depth, Move* quiets, int quietsCnt) {


@@ -1290,6 +1295,12 @@ moves_loop: // When in check and at SpNode search starts from here
         Square prevMoveSq = to_sq((ss-1)->currentMove);
         Countermoves.update(pos.piece_on(prevMoveSq), prevMoveSq, move);
     }
         Square prevMoveSq = to_sq((ss-1)->currentMove);
         Countermoves.update(pos.piece_on(prevMoveSq), prevMoveSq, move);
     }

+
+    if (is_ok((ss-2)->currentMove) && (ss-1)->currentMove == (ss-1)->ttMove)
+    {
+        Square prevOwnMoveSq = to_sq((ss-2)->currentMove);
+        Followupmoves.update(pos.piece_on(prevOwnMoveSq), prevOwnMoveSq, move);
+    }

   }
 
 
   }
 
 

diff --git a/src/search.h b/src/search.h
index ab1076cd61891559d84d198940880e6cbf988f61..25e71a845c36c201b54fbd405e7fc2587d76a656 100644 (file)
--- a/src/search.h
+++ b/src/search.h
@@ -41,6 +41,7 @@ struct Stack {
   SplitPoint* splitPoint;
   int ply;
   Move currentMove;
   SplitPoint* splitPoint;
   int ply;
   Move currentMove;

+  Move ttMove;

   Move excludedMove;
   Move killers[2];
   Depth reduction;
   Move excludedMove;
   Move killers[2];
   Depth reduction;