Remove Stack/thread dependence in movepick

as a lower level routine, movepicker should not depend on the
search stack or the thread class, removing a circular dependency.
Instead of copying the search stack into the movepicker object,
as well as accessing the thread class for one of the histories,
pass the required fields explicitly to the constructor (removing
the need for thread.h and implicitly search.h in movepick.cpp).
The signature is thus longer, but more explicit:

Also some renaming of histories structures while there.

passed STC [-3,1], suggesting a small elo impact:

LLR: 3.13 (-2.94,2.94) [-3.00,1.00]
Total: 381053 W: 68071 L: 68551 D: 244431
elo =   -0.438 +-    0.660 LOS:    9.7%

No functional change.

diff --git a/src/movepick.cpp b/src/movepick.cpp
index 55c685476dcdd481c898b32104a76e0f8c29044b..1f946eadca40d65ed2ccfea3abf1fdf524129809 100644 (file)
--- a/src/movepick.cpp
+++ b/src/movepick.cpp
@@ -21,7 +21,6 @@
 #include <cassert>
 
 #include "movepick.h"
-#include "thread.h"
 
 namespace {
 
@@ -67,23 +66,21 @@ namespace {
 /// search captures, promotions, and some checks) and how important good move
 /// ordering is at the current node.
 
-MovePicker::MovePicker(const Position& p, Move ttm, Depth d, Search::Stack* s)
-           : pos(p), ss(s), depth(d) {
+MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const ButterflyHistory* mh,
+                       const PieceToHistory** ch, Move cm, Move* killers_p)
+           : pos(p), mainHistory(mh), contHistory(ch), countermove(cm),
+             killers{killers_p[0], killers_p[1]}, depth(d){
 
   assert(d > DEPTH_ZERO);
 
-  Square prevSq = to_sq((ss-1)->currentMove);
-  countermove = pos.this_thread()->counterMoves[pos.piece_on(prevSq)][prevSq];
-  killers[0] = ss->killers[0];
-  killers[1] = ss->killers[1];
-
   stage = pos.checkers() ? EVASION : MAIN_SEARCH;
   ttMove = ttm && pos.pseudo_legal(ttm) ? ttm : MOVE_NONE;
   stage += (ttMove == MOVE_NONE);
 }
 
-MovePicker::MovePicker(const Position& p, Move ttm, Depth d, Square s)
-           : pos(p) {
+MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const ButterflyHistory* mh,
+                       const PieceToHistory** ch, Square s)
+           : pos(p), mainHistory(mh), contHistory(ch) {
 
   assert(d <= DEPTH_ZERO);
 
@@ -143,33 +140,22 @@ void MovePicker::score<CAPTURES>() {
 template<>
 void MovePicker::score<QUIETS>() {
 
-  const ButterflyHistory& history = pos.this_thread()->history;
-
-  const PieceToHistory& cmh = *(ss-1)->history;
-  const PieceToHistory& fmh = *(ss-2)->history;
-  const PieceToHistory& fm2 = *(ss-4)->history;
-
-  Color c = pos.side_to_move();
-
   for (auto& m : *this)
-      m.value =  cmh[pos.moved_piece(m)][to_sq(m)]
-               + fmh[pos.moved_piece(m)][to_sq(m)]
-               + fm2[pos.moved_piece(m)][to_sq(m)]
-               + history[c][from_to(m)];
+      m.value =  (*mainHistory)[pos.side_to_move()][from_to(m)]
+               + (*contHistory[0])[pos.moved_piece(m)][to_sq(m)]
+               + (*contHistory[1])[pos.moved_piece(m)][to_sq(m)]
+               + (*contHistory[3])[pos.moved_piece(m)][to_sq(m)];
 }
 
 template<>
 void MovePicker::score<EVASIONS>() {
   // Try captures ordered by MVV/LVA, then non-captures ordered by stats heuristics
-  const ButterflyHistory& history = pos.this_thread()->history;
-  Color c = pos.side_to_move();
-
   for (auto& m : *this)
       if (pos.capture(m))
           m.value =  PieceValue[MG][pos.piece_on(to_sq(m))]
                    - Value(type_of(pos.moved_piece(m))) + (1 << 28);
       else
-          m.value = history[c][from_to(m)];
+          m.value = (*mainHistory)[pos.side_to_move()][from_to(m)];
 }
 
 

diff --git a/src/movepick.h b/src/movepick.h
index a7cac4ba85ba64c03ceb29f64a0aa2eca7d5a939..afd573ea459badabd1aa208b5d6dd498d49d455b 100644 (file)
--- a/src/movepick.h
+++ b/src/movepick.h
@@ -49,14 +49,14 @@ typedef StatBoards<PIECE_NB, SQUARE_NB> PieceToBoards;
 /// ordering decisions. It uses ButterflyBoards as backing store.
 struct ButterflyHistory : public ButterflyBoards {
 
-  void update(Color c, Move m, int v) {
+  void update(Color c, Move m, int bonus) {
 
     const int D = 324;
     auto& entry = (*this)[c][from_to(m)];
 
-    assert(abs(v) <= D); // Consistency check for below formula
+    assert(abs(bonus) <= D); // Consistency check for below formula
 
-    entry += v * 32 - entry * abs(v) / D;
+    entry += bonus * 32 - entry * abs(bonus) / D;
 
     assert(abs(entry) <= 32 * D);
   }
@@ -65,26 +65,27 @@ struct ButterflyHistory : public ButterflyBoards {
 /// PieceToHistory is like ButterflyHistory, but is based on PieceToBoards
 struct PieceToHistory : public PieceToBoards {
 
-  void update(Piece pc, Square to, int v) {
+  void update(Piece pc, Square to, int bonus) {
 
     const int D = 936;
     auto& entry = (*this)[pc][to];
 
-    assert(abs(v) <= D); // Consistency check for below formula
+    assert(abs(bonus) <= D); // Consistency check for below formula
 
-    entry += v * 32 - entry * abs(v) / D;
+    entry += bonus * 32 - entry * abs(bonus) / D;
 
     assert(abs(entry) <= 32 * D);
   }
 };
 
-/// CounterMoveStat stores counter moves indexed by [piece][to] of the previous
+/// CounterMoveHistory stores counter moves indexed by [piece][to] of the previous
 /// move, see chessprogramming.wikispaces.com/Countermove+Heuristic
-typedef StatBoards<PIECE_NB, SQUARE_NB, Move> CounterMoveStat;
+typedef StatBoards<PIECE_NB, SQUARE_NB, Move> CounterMoveHistory;
 
-/// CounterMoveHistoryStat is like CounterMoveStat but instead of a move it
-/// stores a full history (based on PieceTo boards instead of ButterflyBoards).
-typedef StatBoards<PIECE_NB, SQUARE_NB, PieceToHistory> CounterMoveHistoryStat;
+/// ContinuationHistory is the history of a given pair of moves, usually the
+/// current one given a previous one. History table is based on PieceToBoards
+/// instead of ButterflyBoards.
+typedef StatBoards<PIECE_NB, SQUARE_NB, PieceToHistory> ContinuationHistory;
 
 
 /// MovePicker class is used to pick one pseudo legal move at a time from the
@@ -93,17 +94,14 @@ typedef StatBoards<PIECE_NB, SQUARE_NB, PieceToHistory> CounterMoveHistoryStat;
 /// when MOVE_NONE is returned. In order to improve the efficiency of the alpha
 /// beta algorithm, MovePicker attempts to return the moves which are most likely
 /// to get a cut-off first.
-namespace Search { struct Stack; }
 
 class MovePicker {
 public:
   MovePicker(const MovePicker&) = delete;
   MovePicker& operator=(const MovePicker&) = delete;
-
   MovePicker(const Position&, Move, Value);
-  MovePicker(const Position&, Move, Depth, Square);
-  MovePicker(const Position&, Move, Depth, Search::Stack*);
-
+  MovePicker(const Position&, Move, Depth, const ButterflyHistory*, const PieceToHistory**, Square);
+  MovePicker(const Position&, Move, Depth, const ButterflyHistory*, const PieceToHistory**, Move, Move*);
   Move next_move(bool skipQuiets = false);
 
 private:
@@ -112,15 +110,14 @@ private:
   ExtMove* end() { return endMoves; }
 
   const Position& pos;
-  const Search::Stack* ss;
-  Move killers[2];
-  Move countermove;
-  Depth depth;
-  Move ttMove;
+  const ButterflyHistory* mainHistory;
+  const PieceToHistory** contHistory;
+  Move ttMove, countermove, killers[2];
+  ExtMove *cur, *endMoves, *endBadCaptures;
+  int stage;
   Square recaptureSquare;
   Value threshold;
-  int stage;
-  ExtMove *cur, *endMoves, *endBadCaptures;
+  Depth depth;
   ExtMove moves[MAX_MOVES];
 };
 

diff --git a/src/search.cpp b/src/search.cpp
index a59d8d9b0868174f4dd17a91b0794f8eb668095e..94052ef5a482bacc44968c35be562c0eda4cf6e3 100644 (file)
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -151,7 +151,7 @@ namespace {
   Value value_to_tt(Value v, int ply);
   Value value_from_tt(Value v, int ply);
   void update_pv(Move* pv, Move move, Move* childPv);
-  void update_cm_stats(Stack* ss, Piece pc, Square s, int bonus);
+  void update_continuation_histories(Stack* ss, Piece pc, Square to, int bonus);
   void update_stats(const Position& pos, Stack* ss, Move move, Move* quiets, int quietsCnt, int bonus);
 
 } // namespace
@@ -192,13 +192,13 @@ void Search::clear() {
   for (Thread* th : Threads)
   {
       th->counterMoves.fill(MOVE_NONE);
-      th->history.fill(0);
+      th->mainHistory.fill(0);
 
-      for (auto& to : th->counterMoveHistory)
+      for (auto& to : th->contHistory)
           for (auto& h : to)
               h.fill(0);
 
-      th->counterMoveHistory[NO_PIECE][0].fill(CounterMovePruneThreshold - 1);
+      th->contHistory[NO_PIECE][0].fill(CounterMovePruneThreshold - 1);
   }
 
   Threads.main()->callsCnt = 0;
@@ -334,7 +334,7 @@ void Thread::search() {
 
   std::memset(ss-4, 0, 7 * sizeof(Stack));
   for (int i = 4; i > 0; i--)
-     (ss-i)->history = &this->counterMoveHistory[NO_PIECE][0]; // Use as sentinel
+     (ss-i)->contHistory = &this->contHistory[NO_PIECE][0]; // Use as sentinel
 
   bestValue = delta = alpha = -VALUE_INFINITE;
   beta = VALUE_INFINITE;
@@ -591,7 +591,7 @@ namespace {
     assert(0 <= ss->ply && ss->ply < MAX_PLY);
 
     ss->currentMove = (ss+1)->excludedMove = bestMove = MOVE_NONE;
-    ss->history = &thisThread->counterMoveHistory[NO_PIECE][0];
+    ss->contHistory = &thisThread->contHistory[NO_PIECE][0];
     (ss+2)->killers[0] = (ss+2)->killers[1] = MOVE_NONE;
     Square prevSq = to_sq((ss-1)->currentMove);
 
@@ -623,14 +623,14 @@ namespace {
 
                 // Extra penalty for a quiet TT move in previous ply when it gets refuted
                 if ((ss-1)->moveCount == 1 && !pos.captured_piece())
-                    update_cm_stats(ss-1, pos.piece_on(prevSq), prevSq, -stat_bonus(depth + ONE_PLY));
+                    update_continuation_histories(ss-1, pos.piece_on(prevSq), prevSq, -stat_bonus(depth + ONE_PLY));
             }
             // Penalty for a quiet ttMove that fails low
             else if (!pos.capture_or_promotion(ttMove))
             {
                 int penalty = -stat_bonus(depth);
-                thisThread->history.update(pos.side_to_move(), ttMove, penalty);
-                update_cm_stats(ss, pos.moved_piece(ttMove), to_sq(ttMove), penalty);
+                thisThread->mainHistory.update(pos.side_to_move(), ttMove, penalty);
+                update_continuation_histories(ss, pos.moved_piece(ttMove), to_sq(ttMove), penalty);
             }
         }
         return ttValue;
@@ -734,7 +734,7 @@ namespace {
         Depth R = ((823 + 67 * depth / ONE_PLY) / 256 + std::min((eval - beta) / PawnValueMg, 3)) * ONE_PLY;
 
         ss->currentMove = MOVE_NULL;
-        ss->history = &thisThread->counterMoveHistory[NO_PIECE][0];
+        ss->contHistory = &thisThread->contHistory[NO_PIECE][0];
 
         pos.do_null_move(st);
         Value nullValue = depth-R < ONE_PLY ? -qsearch<NonPV, false>(pos, ss+1, -beta, -beta+1)
@@ -776,7 +776,7 @@ namespace {
             if (pos.legal(move))
             {
                 ss->currentMove = move;
-                ss->history = &thisThread->counterMoveHistory[pos.moved_piece(move)][to_sq(move)];
+                ss->contHistory = &thisThread->contHistory[pos.moved_piece(move)][to_sq(move)];
 
                 assert(depth >= 5 * ONE_PLY);
                 pos.do_move(move, st);
@@ -801,11 +801,10 @@ namespace {
 
 moves_loop: // When in check search starts from here
 
-    const PieceToHistory& cmh = *(ss-1)->history;
-    const PieceToHistory& fmh = *(ss-2)->history;
-    const PieceToHistory& fm2 = *(ss-4)->history;
+    const PieceToHistory* contHist[] = { (ss-1)->contHistory, (ss-2)->contHistory, nullptr, (ss-4)->contHistory };
+    Move countermove = thisThread->counterMoves[pos.piece_on(prevSq)][prevSq];
 
-    MovePicker mp(pos, ttMove, depth, ss);
+    MovePicker mp(pos, ttMove, depth, &thisThread->mainHistory, contHist, countermove, ss->killers);
     value = bestValue; // Workaround a bogus 'uninitialized' warning under gcc
     improving =   ss->staticEval >= (ss-2)->staticEval
             /* || ss->staticEval == VALUE_NONE Already implicit in the previous condition */
@@ -907,8 +906,8 @@ moves_loop: // When in check search starts from here
 
               // Countermoves based pruning
               if (   lmrDepth < 3
-                  && (cmh[moved_piece][to_sq(move)] < CounterMovePruneThreshold)
-                  && (fmh[moved_piece][to_sq(move)] < CounterMovePruneThreshold))
+                  && (*contHist[0])[moved_piece][to_sq(move)] < CounterMovePruneThreshold
+                  && (*contHist[1])[moved_piece][to_sq(move)] < CounterMovePruneThreshold)
                   continue;
 
               // Futility pruning: parent node
@@ -943,7 +942,7 @@ moves_loop: // When in check search starts from here
 
       // Update the current move (this must be done after singular extension search)
       ss->currentMove = move;
-      ss->history = &thisThread->counterMoveHistory[moved_piece][to_sq(move)];
+      ss->contHistory = &thisThread->contHistory[moved_piece][to_sq(move)];
 
       // Step 14. Make the move
       pos.do_move(move, st, givesCheck);
@@ -975,11 +974,11 @@ moves_loop: // When in check search starts from here
                        && !pos.see_ge(make_move(to_sq(move), from_sq(move))))
                   r -= 2 * ONE_PLY;
 
-              ss->statScore =  cmh[moved_piece][to_sq(move)]
-                             + fmh[moved_piece][to_sq(move)]
-                             + fm2[moved_piece][to_sq(move)]
-                             + thisThread->history[~pos.side_to_move()][from_to(move)]
-                             - 4000; // Correction factor
+              ss->statScore =  thisThread->mainHistory[~pos.side_to_move()][from_to(move)]
+                             + (*contHist[0])[moved_piece][to_sq(move)]
+                             + (*contHist[1])[moved_piece][to_sq(move)]
+                             + (*contHist[3])[moved_piece][to_sq(move)]
+                             - 4000;
 
               // Decrease/increase reduction by comparing opponent's stat score
               if (ss->statScore > 0 && (ss-1)->statScore < 0)
@@ -1115,13 +1114,13 @@ moves_loop: // When in check search starts from here
 
         // Extra penalty for a quiet TT move in previous ply when it gets refuted
         if ((ss-1)->moveCount == 1 && !pos.captured_piece())
-            update_cm_stats(ss-1, pos.piece_on(prevSq), prevSq, -stat_bonus(depth + ONE_PLY));
+            update_continuation_histories(ss-1, pos.piece_on(prevSq), prevSq, -stat_bonus(depth + ONE_PLY));
     }
     // Bonus for prior countermove that caused the fail low
     else if (    depth >= 3 * ONE_PLY
              && !pos.captured_piece()
              && is_ok((ss-1)->currentMove))
-        update_cm_stats(ss-1, pos.piece_on(prevSq), prevSq, stat_bonus(depth));
+        update_continuation_histories(ss-1, pos.piece_on(prevSq), prevSq, stat_bonus(depth));
 
     if (!excludedMove)
         tte->save(posKey, value_to_tt(bestValue, ss->ply),
@@ -1241,7 +1240,8 @@ moves_loop: // When in check search starts from here
     // to search the moves. Because the depth is <= 0 here, only captures,
     // queen promotions and checks (only if depth >= DEPTH_QS_CHECKS) will
     // be generated.
-    MovePicker mp(pos, ttMove, depth, to_sq((ss-1)->currentMove));
+    const PieceToHistory* contHist[4] = {};
+    MovePicker mp(pos, ttMove, depth, &pos.this_thread()->mainHistory, contHist, to_sq((ss-1)->currentMove));
 
     // Loop through the moves until no moves remain or a beta cutoff occurs
     while ((move = mp.next_move()) != MOVE_NONE)
@@ -1385,13 +1385,14 @@ moves_loop: // When in check search starts from here
   }
 
 
-  // update_cm_stats() updates countermove and follow-up move history
+  // update_continuation_histories() updates histories of the move pairs formed
+  // by moves at ply -1, -2, and -4 with current move.
 
-  void update_cm_stats(Stack* ss, Piece pc, Square s, int bonus) {
+  void update_continuation_histories(Stack* ss, Piece pc, Square to, int bonus) {
 
     for (int i : {1, 2, 4})
         if (is_ok((ss-i)->currentMove))
-            (ss-i)->history->update(pc, s, bonus);
+            (ss-i)->contHistory->update(pc, to, bonus);
   }
 
 
@@ -1408,20 +1409,20 @@ moves_loop: // When in check search starts from here
 
     Color c = pos.side_to_move();
     Thread* thisThread = pos.this_thread();
-    thisThread->history.update(c, move, bonus);
-    update_cm_stats(ss, pos.moved_piece(move), to_sq(move), bonus);
+    thisThread->mainHistory.update(c, move, bonus);
+    update_continuation_histories(ss, pos.moved_piece(move), to_sq(move), bonus);
 
     if (is_ok((ss-1)->currentMove))
     {
         Square prevSq = to_sq((ss-1)->currentMove);
-        thisThread->counterMoves[pos.piece_on(prevSq)][prevSq]=move;
+        thisThread->counterMoves[pos.piece_on(prevSq)][prevSq] = move;
     }
 
     // Decrease all the other played quiet moves
     for (int i = 0; i < quietsCnt; ++i)
     {
-        thisThread->history.update(c, quiets[i], -bonus);
-        update_cm_stats(ss, pos.moved_piece(quiets[i]), to_sq(quiets[i]), -bonus);
+        thisThread->mainHistory.update(c, quiets[i], -bonus);
+        update_continuation_histories(ss, pos.moved_piece(quiets[i]), to_sq(quiets[i]), -bonus);
     }
   }
 

diff --git a/src/search.h b/src/search.h
index a2a02edac3ed2c63217808aee07c23b459a4abab..477570e3919e3d40c7d0092e44a61630a4357e61 100644 (file)
--- a/src/search.h
+++ b/src/search.h
@@ -37,7 +37,7 @@ namespace Search {
 
 struct Stack {
   Move* pv;
-  PieceToHistory* history;
+  PieceToHistory* contHistory;
   int ply;
   Move currentMove;
   Move excludedMove;

diff --git a/src/thread.h b/src/thread.h
index 35cf3efeb53aea704394f20a11bf36d86c815561..c1b635b7ea4db61dfca33ed0ee3423e3eeefb862 100644 (file)
--- a/src/thread.h
+++ b/src/thread.h
@@ -67,9 +67,9 @@ public:
   Search::RootMoves rootMoves;
   Depth rootDepth;
   Depth completedDepth;
-  CounterMoveStat counterMoves;
-  ButterflyHistory history;
-  CounterMoveHistoryStat counterMoveHistory;
+  CounterMoveHistory counterMoves;
+  ButterflyHistory mainHistory;
+  ContinuationHistory contHistory;
 };