Introduce Counter Move History tables

Introduce a counter move history table which additionally is indexed by the last move's piece and target square.
For quiet move ordering use now the sum of standard and counter move history table.

STC:
LLR: 2.96 (-2.94,2.94) [-1.50,4.50]
Total: 4747 W: 1005 L: 885 D: 2857

LTC:
LLR: 2.95 (-2.94,2.94) [0.00,6.00]
Total: 5726 W: 1001 L: 872 D: 3853

Because of reported low NPS on multi core test
STC (7 threads):
ELO: 7.26 +-3.3 (95%) LOS: 100.0%
Total: 14937 W: 2710 L: 2398 D: 9829

Bench: 7725341

Resolves #282

diff --git a/src/movepick.cpp b/src/movepick.cpp
index b3f413bf1ffa0bd20255ccd5f25893839dfd1e45..d6a40d70af4c7d2d37305fe1f60dde62d6f51791 100644 (file)
--- a/src/movepick.cpp
+++ b/src/movepick.cpp
@@ -67,8 +67,8 @@ 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, const HistoryStats& h,
-                       Move* cm, Move* fm, Search::Stack* s) : pos(p), history(h), depth(d) {
+MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const HistoryStats& h, const CounterMovesHistoryStats& cmh,
+                       Move* cm, Move* fm, Search::Stack* s) : pos(p), history(h), counterMovesHistory(cmh), depth(d) {
 
   assert(d > DEPTH_ZERO);
 
@@ -87,8 +87,8 @@ MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const HistoryStats&
   endMoves += (ttMove != MOVE_NONE);
 }
 
-MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const HistoryStats& h,
-                       Square s) : pos(p), history(h) {
+MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const HistoryStats& h, const CounterMovesHistoryStats& cmh,
+                       Square s) : pos(p), history(h), counterMovesHistory(cmh) {
 
   assert(d <= DEPTH_ZERO);
 
@@ -112,8 +112,8 @@ MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const HistoryStats&
   endMoves += (ttMove != MOVE_NONE);
 }
 
-MovePicker::MovePicker(const Position& p, Move ttm, const HistoryStats& h, PieceType pt)
-                       : pos(p), history(h) {
+MovePicker::MovePicker(const Position& p, Move ttm, const HistoryStats& h, const CounterMovesHistoryStats& cmh, PieceType pt)
+                       : pos(p), history(h), counterMovesHistory(cmh) {
 
   assert(!pos.checkers());
 
@@ -162,8 +162,13 @@ void MovePicker::score<CAPTURES>() {
 
 template<>
 void MovePicker::score<QUIETS>() {
+  Square prevMoveSq = to_sq((ss-1)->currentMove);
+  Piece prevMovePiece = pos.piece_on(prevMoveSq);
+  const HistoryStats &cmh = counterMovesHistory[prevMovePiece][prevMoveSq];
+
   for (auto& m : *this)
-      m.value = history[pos.moved_piece(m)][to_sq(m)];
+      m.value =  history[pos.moved_piece(m)][to_sq(m)]
+               + cmh[pos.moved_piece(m)][to_sq(m)];
 }
 
 template<>

diff --git a/src/movepick.h b/src/movepick.h
index 44be9636e45974a67b3d6cf47817b87295d6dad0..9ffebc0038157c0be17f3094dc4a911e12578115 100644 (file)
--- a/src/movepick.h
+++ b/src/movepick.h
@@ -43,6 +43,7 @@ struct Stats {
   static const Value Max = Value(250);
 
   const T* operator[](Piece pc) const { return table[pc]; }
+  T* operator[](Piece pc) { return table[pc]; }
   void clear() { std::memset(table, 0, sizeof(table)); }
 
   void update(Piece pc, Square to, Move m) {
@@ -70,6 +71,7 @@ private:
 typedef Stats< true, Value> GainsStats;
 typedef Stats<false, Value> HistoryStats;
 typedef Stats<false, std::pair<Move, Move> > MovesStats;
+typedef Stats<false, HistoryStats> CounterMovesHistoryStats;
 
 
 /// MovePicker class is used to pick one pseudo legal move at a time from the
@@ -84,9 +86,9 @@ public:
   MovePicker(const MovePicker&) = delete;
   MovePicker& operator=(const MovePicker&) = delete;
 
-  MovePicker(const Position&, Move, Depth, const HistoryStats&, Square);
-  MovePicker(const Position&, Move, const HistoryStats&, PieceType);
-  MovePicker(const Position&, Move, Depth, const HistoryStats&, Move*, Move*, Search::Stack*);
+  MovePicker(const Position&, Move, Depth, const HistoryStats&, const CounterMovesHistoryStats&, Square);
+  MovePicker(const Position&, Move, const HistoryStats&, const CounterMovesHistoryStats&, PieceType);
+  MovePicker(const Position&, Move, Depth, const HistoryStats&, const CounterMovesHistoryStats&, Move*, Move*, Search::Stack*);
 
   template<bool SpNode> Move next_move();
 
@@ -98,6 +100,7 @@ private:
 
   const Position& pos;
   const HistoryStats& history;
+  const CounterMovesHistoryStats& counterMovesHistory;
   Search::Stack* ss;
   Move* countermoves;
   Move* followupmoves;

diff --git a/src/search.cpp b/src/search.cpp
index 501d6c60b447f5b132ddcc6ef3a307b47d8235dd..f374b462f8a0169be2a28399cb313975b653af56 100644 (file)
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -95,6 +95,7 @@ namespace {
   double BestMoveChanges;
   Value DrawValue[COLOR_NB];
   HistoryStats History;
+  CounterMovesHistoryStats CounterMovesHistory;
   GainsStats Gains;
   MovesStats Countermoves, Followupmoves;
 
@@ -289,6 +290,7 @@ namespace {
 
     TT.new_search();
     History.clear();
+    CounterMovesHistory.clear();
     Gains.clear();
     Countermoves.clear();
     Followupmoves.clear();
@@ -687,7 +689,7 @@ namespace {
         assert((ss-1)->currentMove != MOVE_NONE);
         assert((ss-1)->currentMove != MOVE_NULL);
 
-        MovePicker mp(pos, ttMove, History, pos.captured_piece_type());
+        MovePicker mp(pos, ttMove, History, CounterMovesHistory, pos.captured_piece_type());
         CheckInfo ci(pos);
 
         while ((move = mp.next_move<false>()) != MOVE_NONE)
@@ -726,7 +728,7 @@ moves_loop: // When in check and at SpNode search starts from here
     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);
+    MovePicker mp(pos, ttMove, depth, History, CounterMovesHistory, countermoves, followupmoves, ss);
     CheckInfo ci(pos);
     value = bestValue; // Workaround a bogus 'uninitialized' warning under gcc
     improving =   ss->staticEval >= (ss-2)->staticEval
@@ -1192,7 +1194,7 @@ moves_loop: // When in check and at SpNode 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, History, to_sq((ss-1)->currentMove));
+    MovePicker mp(pos, ttMove, depth, History, CounterMovesHistory, to_sq((ss-1)->currentMove));
     CheckInfo ci(pos);
 
     // Loop through the moves until no moves remain or a beta cutoff occurs
@@ -1356,7 +1358,16 @@ moves_loop: // When in check and at SpNode search starts from here
     if (is_ok((ss-1)->currentMove))
     {
         Square prevMoveSq = to_sq((ss-1)->currentMove);
-        Countermoves.update(pos.piece_on(prevMoveSq), prevMoveSq, move);
+        Piece prevMovePiece = pos.piece_on(prevMoveSq);
+        Countermoves.update(prevMovePiece, prevMoveSq, move);
+
+        HistoryStats& cmh = CounterMovesHistory[prevMovePiece][prevMoveSq];
+        cmh.update(pos.moved_piece(move), to_sq(move), bonus);
+        for (int i = 0; i < quietsCnt; ++i)
+        {
+            Move m = quiets[i];
+            cmh.update(pos.moved_piece(m), to_sq(m), -bonus);
+        }
     }
 
     if (is_ok((ss-2)->currentMove) && (ss-1)->currentMove == (ss-1)->ttMove)