Improve move order near the root

Current move histories are known to work well near the leaves, whilst at
higher depths they aren't very helpful. To address this problem this
patch introduces a table dedicated for what's happening at plies 0-3.
It's structured like mainHistory with ply index instead of color.
It get cleared with each new search and is filled during iterative
deepening at higher depths when recording successful quiet moves near
the root or traversing nodes which were in the principal variation
(ttPv).

Medium TC (20+0.2):
https://tests.stockfishchess.org/tests/view/5e4d358790a0a02810d096dc
LLR: 2.94 (-2.94,2.94) {-0.50,1.50}
Total: 100910 W: 16682 L: 16376 D: 67852
Ptnml(0-2): 1177, 10983, 25883, 11181, 1231

LTC:
https://tests.stockfishchess.org/tests/view/5e4e2cb790a0a02810d09714
LLR: 2.95 (-2.94,2.94) {0.25,1.75}
Total: 80444 W: 10495 L: 10095 D: 59854
Ptnml(0-2): 551, 7479, 23803, 7797, 592

closes https://github.com/official-stockfish/Stockfish/pull/2557

Bench: 4705960

diff --git a/src/movepick.cpp b/src/movepick.cpp
index 025f5b82cdeb2ae808d23c0e75a955862b48524b..575c902228b6804c54dd5181af0e6880694ad96d 100644 (file)
--- a/src/movepick.cpp
+++ b/src/movepick.cpp
@@ -56,10 +56,10 @@ namespace {
 /// ordering is at the current node.
 
 /// MovePicker constructor for the main search
-MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const ButterflyHistory* mh,
-                       const CapturePieceToHistory* cph, const PieceToHistory** ch, Move cm, Move* killers)
-           : pos(p), mainHistory(mh), captureHistory(cph), continuationHistory(ch),
-             refutations{{killers[0], 0}, {killers[1], 0}, {cm, 0}}, depth(d) {
+MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const ButterflyHistory* mh, const LowPlyHistory* lp,
+                       const CapturePieceToHistory* cph, const PieceToHistory** ch, Move cm, Move* killers, int pl)
+           : pos(p), mainHistory(mh), lowPlyHistory(lp), captureHistory(cph), continuationHistory(ch),
+             refutations{{killers[0], 0}, {killers[1], 0}, {cm, 0}}, depth(d) , ply(pl) {
 
   assert(d > 0);
 
@@ -115,7 +115,8 @@ void MovePicker::score() {
                    + 2 * (*continuationHistory[0])[pos.moved_piece(m)][to_sq(m)]
                    + 2 * (*continuationHistory[1])[pos.moved_piece(m)][to_sq(m)]
                    + 2 * (*continuationHistory[3])[pos.moved_piece(m)][to_sq(m)]
-                   +     (*continuationHistory[5])[pos.moved_piece(m)][to_sq(m)];
+                   +     (*continuationHistory[5])[pos.moved_piece(m)][to_sq(m)]
+                   + (ply < MAX_LPH ?  4 * (*lowPlyHistory)[ply][from_to(m)] : 0);
 
       else // Type == EVASIONS
       {

diff --git a/src/movepick.h b/src/movepick.h
index cdedc9b616f9f78c6a652626c0c0a5ba096ed71b..33c4b08602bbd78ecdfd1a978ef287a43f713ec5 100644 (file)
--- a/src/movepick.h
+++ b/src/movepick.h
@@ -88,6 +88,12 @@ enum StatsType { NoCaptures, Captures };
 /// the move's from and to squares, see www.chessprogramming.org/Butterfly_Boards
 typedef Stats<int16_t, 10692, COLOR_NB, int(SQUARE_NB) * int(SQUARE_NB)> ButterflyHistory;
 
+/// LowPlyHistory at higher depths records successful quiet moves on plies 0 to 3
+/// and quiet moves which are/were in the PV (ttPv)
+/// It get cleared with each new search and get filled during iterative deepening
+constexpr int MAX_LPH = 4;
+typedef Stats<int16_t, 10692, MAX_LPH, int(SQUARE_NB) * int(SQUARE_NB)> LowPlyHistory;
+
 /// CounterMoveHistory stores counter moves indexed by [piece][to] of the previous
 /// move, see www.chessprogramming.org/Countermove_Heuristic
 typedef Stats<Move, NOT_USED, PIECE_NB, SQUARE_NB> CounterMoveHistory;
@@ -123,10 +129,12 @@ public:
                                            const PieceToHistory**,
                                            Square);
   MovePicker(const Position&, Move, Depth, const ButterflyHistory*,
+                                           const LowPlyHistory*,
                                            const CapturePieceToHistory*,
                                            const PieceToHistory**,
                                            Move,
-                                           Move*);
+                                           Move*,
+                                           int);
   Move next_move(bool skipQuiets = false);
 
 private:
@@ -137,6 +145,7 @@ private:
 
   const Position& pos;
   const ButterflyHistory* mainHistory;
+  const LowPlyHistory* lowPlyHistory;
   const CapturePieceToHistory* captureHistory;
   const PieceToHistory** continuationHistory;
   Move ttMove;
@@ -145,6 +154,7 @@ private:
   Square recaptureSquare;
   Value threshold;
   Depth depth;
+  int ply;
   ExtMove moves[MAX_MOVES];
 };
 

diff --git a/src/search.cpp b/src/search.cpp
index c3ebf9abc302dd0974e25fef4a6bc32d19e43956..3f860ac5e5b9d073e93ab6f1f476a6a49e9c9eff 100644 (file)
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -156,7 +156,7 @@ namespace {
   Value value_from_tt(Value v, int ply, int r50c);
   void update_pv(Move* pv, Move move, Move* childPv);
   void update_continuation_histories(Stack* ss, Piece pc, Square to, int bonus);
-  void update_quiet_stats(const Position& pos, Stack* ss, Move move, int bonus);
+  void update_quiet_stats(const Position& pos, Stack* ss, Move move, int bonus, int depth);
   void update_all_stats(const Position& pos, Stack* ss, Move bestMove, Value bestValue, Value beta, Square prevSq,
                         Move* quietsSearched, int quietCount, Move* capturesSearched, int captureCount, Depth depth);
 
@@ -695,6 +695,10 @@ namespace {
     ttMove =  rootNode ? thisThread->rootMoves[thisThread->pvIdx].pv[0]
             : ttHit    ? tte->move() : MOVE_NONE;
     ttPv = PvNode || (ttHit && tte->is_pv());
+
+    if (ttPv && depth > 12 && ss->ply - 1 < MAX_LPH && !pos.captured_piece() && is_ok((ss-1)->currentMove))
+        thisThread->lowPlyHistory[ss->ply - 1][from_to((ss-1)->currentMove)] << stat_bonus(depth - 5);
+
     // thisThread->ttHitAverage can be used to approximate the running average of ttHit
     thisThread->ttHitAverage =   (ttHitAverageWindow - 1) * thisThread->ttHitAverage / ttHitAverageWindow
                                 + ttHitAverageResolution * ttHit;
@@ -713,7 +717,7 @@ namespace {
             if (ttValue >= beta)
             {
                 if (!pos.capture_or_promotion(ttMove))
-                    update_quiet_stats(pos, ss, ttMove, stat_bonus(depth));
+                    update_quiet_stats(pos, ss, ttMove, stat_bonus(depth), depth);
 
                 // Extra penalty for early quiet moves of the previous ply
                 if ((ss-1)->moveCount <= 2 && !priorCapture)
@@ -948,10 +952,12 @@ moves_loop: // When in check, search starts from here
     Move countermove = thisThread->counterMoves[pos.piece_on(prevSq)][prevSq];
 
     MovePicker mp(pos, ttMove, depth, &thisThread->mainHistory,
+                                      &thisThread->lowPlyHistory,
                                       &thisThread->captureHistory,
                                       contHist,
                                       countermove,
-                                      ss->killers);
+                                      ss->killers,
+                                      depth > 12 && ttPv ? ss->ply : MAX_PLY);
 
     value = bestValue;
     singularLMR = moveCountPruning = false;
@@ -1633,7 +1639,7 @@ moves_loop: // When in check, search starts from here
 
     if (!pos.capture_or_promotion(bestMove))
     {
-        update_quiet_stats(pos, ss, bestMove, bonus2);
+        update_quiet_stats(pos, ss, bestMove, bonus2, depth);
 
         // Decrease all the non-best quiet moves
         for (int i = 0; i < quietCount; ++i)
@@ -1673,7 +1679,7 @@ moves_loop: // When in check, search starts from here
 
   // update_quiet_stats() updates move sorting heuristics
 
-  void update_quiet_stats(const Position& pos, Stack* ss, Move move, int bonus) {
+  void update_quiet_stats(const Position& pos, Stack* ss, Move move, int bonus, int depth) {
 
     if (ss->killers[0] != move)
     {
@@ -1694,6 +1700,9 @@ moves_loop: // When in check, search starts from here
         Square prevSq = to_sq((ss-1)->currentMove);
         thisThread->counterMoves[pos.piece_on(prevSq)][prevSq] = move;
     }
+
+    if (depth > 12 && ss->ply < MAX_LPH)
+        thisThread->lowPlyHistory[ss->ply][from_to(move)] << stat_bonus(depth - 7);
   }
 
   // When playing with strength handicap, choose best move among a set of RootMoves

diff --git a/src/thread.cpp b/src/thread.cpp
index 10ec96dddbae31005fb2fee3c79e0753e34d41eb..b5cb87d9356974553a50bea29c92342f67c9c173 100644 (file)
--- a/src/thread.cpp
+++ b/src/thread.cpp
@@ -68,6 +68,7 @@ void Thread::clear() {
 
   counterMoves.fill(MOVE_NONE);
   mainHistory.fill(0);
+  lowPlyHistory.fill(0);
   captureHistory.fill(0);
 
   for (bool inCheck : { false, true })
@@ -211,6 +212,7 @@ void ThreadPool::start_thinking(Position& pos, StateListPtr& states,
       th->rootDepth = th->completedDepth = 0;
       th->rootMoves = rootMoves;
       th->rootPos.set(pos.fen(), pos.is_chess960(), &setupStates->back(), th);
+      th->lowPlyHistory.fill(0);
   }
 
   setupStates->back() = tmp;

diff --git a/src/thread.h b/src/thread.h
index 63629e338124e5a6e12a44205698205c601be29c..41d2b8f6d271769df032888d7c633bb7c20a6581 100644 (file)
--- a/src/thread.h
+++ b/src/thread.h
@@ -71,6 +71,7 @@ public:
   Depth rootDepth, completedDepth;
   CounterMoveHistory counterMoves;
   ButterflyHistory mainHistory;
+  LowPlyHistory lowPlyHistory;
   CapturePieceToHistory captureHistory;
   ContinuationHistory continuationHistory[2][2];
   Score contempt;