Introduce capture history table for capture move sorting

Introduce capture move history table indexed by moved piece,
target square and captured piece type for sorting capture moves.

STC:
LLR: 2.95 (-2.94,2.94) [0.00,5.00]
Total: 11374 W: 2096 L: 1924 D: 7354
http://tests.stockfishchess.org/tests/view/59fac8dc0ebc590ccbb89fc5

LTC:
LLR: 2.95 (-2.94,2.94) [0.00,5.00]
Total: 24791 W: 3196 L: 3001 D: 18594
http://tests.stockfishchess.org/tests/view/59fae4d20ebc590ccbb89fd9

Bench: 5536775

diff --git a/src/movepick.cpp b/src/movepick.cpp
index 1c0de699641688bae41a96d75858d05c5c0215e8..06935b0d9d13c321db0e6d373f8308bcddd7bf7b 100644 (file)
--- a/src/movepick.cpp
+++ b/src/movepick.cpp
@@ -68,8 +68,8 @@ namespace {
 
 /// MovePicker constructor for the main search
 MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const ButterflyHistory* mh,
 
 /// MovePicker constructor for the main search
 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),
+                       const CapturePieceToHistory* cph, const PieceToHistory** ch, Move cm, Move* killers_p)
+           : pos(p), mainHistory(mh), captureHistory(cph), contHistory(ch), countermove(cm),

              killers{killers_p[0], killers_p[1]}, depth(d){
 
   assert(d > DEPTH_ZERO);
              killers{killers_p[0], killers_p[1]}, depth(d){
 
   assert(d > DEPTH_ZERO);


@@ -80,8 +80,8 @@ MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const ButterflyHist
 }
 
 /// MovePicker constructor for quiescence search
 }
 
 /// MovePicker constructor for quiescence search

-MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const ButterflyHistory* mh, Square s)
-           : pos(p), mainHistory(mh) {
+MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const ButterflyHistory* mh,  const CapturePieceToHistory* cph, Square s)
+           : pos(p), mainHistory(mh), captureHistory(cph) {

 
   assert(d <= DEPTH_ZERO);
 
 
   assert(d <= DEPTH_ZERO);
 


@@ -107,8 +107,8 @@ MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const ButterflyHist
 
 /// MovePicker constructor for ProbCut: we generate captures with SEE higher
 /// than or equal to the given threshold.
 
 /// MovePicker constructor for ProbCut: we generate captures with SEE higher
 /// than or equal to the given threshold.

-MovePicker::MovePicker(const Position& p, Move ttm, Value th)
-           : pos(p), threshold(th) {
+MovePicker::MovePicker(const Position& p, Move ttm, Value th, const CapturePieceToHistory* cph)
+           : pos(p), captureHistory(cph), threshold(th) {

 
   assert(!pos.checkers());
 
 
   assert(!pos.checkers());
 


@@ -132,7 +132,7 @@ void MovePicker::score() {
   for (auto& m : *this)
       if (Type == CAPTURES)
           m.value =  PieceValue[MG][pos.piece_on(to_sq(m))]
   for (auto& m : *this)
       if (Type == CAPTURES)
           m.value =  PieceValue[MG][pos.piece_on(to_sq(m))]

-                   - Value(200 * relative_rank(pos.side_to_move(), to_sq(m)));
+                   + Value((*captureHistory)[pos.moved_piece(m)][to_sq(m)][type_of(pos.piece_on(to_sq(m)))]);

 
       else if (Type == QUIETS)
           m.value =  (*mainHistory)[pos.side_to_move()][from_to(m)]
 
       else if (Type == QUIETS)
           m.value =  (*mainHistory)[pos.side_to_move()][from_to(m)]

diff --git a/src/movepick.h b/src/movepick.h
index 66fc1bdba4a929bd1680eeb5715a9786581881f2..db9439f715ed1860718f712d9afb855987117fd9 100644 (file)
--- a/src/movepick.h
+++ b/src/movepick.h
@@ -22,6 +22,7 @@
 #define MOVEPICK_H_INCLUDED
 
 #include <array>
 #define MOVEPICK_H_INCLUDED
 
 #include <array>

+#include <limits>

 
 #include "movegen.h"
 #include "position.h"
 
 #include "movegen.h"
 #include "position.h"


@@ -39,7 +40,7 @@ struct StatBoards : public std::array<std::array<T, Size2>, Size1> {
   void update(T& entry, int bonus, const int D) {
 
     assert(abs(bonus) <= D); // Ensure range is [-32 * D, 32 * D]
   void update(T& entry, int bonus, const int D) {
 
     assert(abs(bonus) <= D); // Ensure range is [-32 * D, 32 * D]

-    assert(abs(32 * D) < INT16_MAX); // Ensure we don't overflow
+    assert(abs(32 * D) < (std::numeric_limits<T>::max)()); // Ensure we don't overflow

 
     entry += bonus * 32 - entry * abs(bonus) / D;
 
 
     entry += bonus * 32 - entry * abs(bonus) / D;
 


@@ -47,6 +48,26 @@ struct StatBoards : public std::array<std::array<T, Size2>, Size1> {
   }
 };
 
   }
 };
 

+/// StatCubes is a generic 3-dimensional array used to store various statistics
+template<int Size1, int Size2, int Size3, typename T = int16_t>
+struct StatCubes : public std::array<std::array<std::array<T, Size3>, Size2>, Size1> {
+
+  void fill(const T& v) {
+    T* p = &(*this)[0][0][0];
+    std::fill(p, p + sizeof(*this) / sizeof(*p), v);
+  }
+
+  void update(T& entry, int bonus, const int D, const int W) {
+
+    assert(abs(bonus) <= D); // Ensure range is [-W * D, W * D]
+    assert(abs(W * D) < (std::numeric_limits<T>::max)()); // Ensure we don't overflow
+
+    entry += bonus * W - entry * abs(bonus) / D;
+
+    assert(abs(entry) <= W * D);
+  }
+};
+

 /// ButterflyBoards are 2 tables (one for each color) indexed by the move's from
 /// and to squares, see chessprogramming.wikispaces.com/Butterfly+Boards
 typedef StatBoards<COLOR_NB, int(SQUARE_NB) * int(SQUARE_NB)> ButterflyBoards;
 /// ButterflyBoards are 2 tables (one for each color) indexed by the move's from
 /// and to squares, see chessprogramming.wikispaces.com/Butterfly+Boards
 typedef StatBoards<COLOR_NB, int(SQUARE_NB) * int(SQUARE_NB)> ButterflyBoards;


@@ -54,6 +75,9 @@ typedef StatBoards<COLOR_NB, int(SQUARE_NB) * int(SQUARE_NB)> ButterflyBoards;
 /// PieceToBoards are addressed by a move's [piece][to] information
 typedef StatBoards<PIECE_NB, SQUARE_NB> PieceToBoards;
 
 /// PieceToBoards are addressed by a move's [piece][to] information
 typedef StatBoards<PIECE_NB, SQUARE_NB> PieceToBoards;
 

+/// CapturePieceToBoards are addressed by a move's [piece][to][captured piece type] information
+typedef StatCubes<PIECE_NB, SQUARE_NB, PIECE_TYPE_NB> CapturePieceToBoards;
+

 /// ButterflyHistory records how often quiet moves have been successful or
 /// unsuccessful during the current search, and is used for reduction and move
 /// ordering decisions. It uses ButterflyBoards as backing store.
 /// ButterflyHistory records how often quiet moves have been successful or
 /// unsuccessful during the current search, and is used for reduction and move
 /// ordering decisions. It uses ButterflyBoards as backing store.


@@ -72,6 +96,14 @@ struct PieceToHistory : public PieceToBoards {
   }
 };
 
   }
 };
 

+/// CapturePieceToHistory is like PieceToHistory, but is based on CapturePieceToBoards
+struct CapturePieceToHistory : public CapturePieceToBoards {
+
+  void update(Piece pc, Square to, PieceType captured, int bonus) {
+    StatCubes::update((*this)[pc][to][captured], bonus, 324, 2);
+  }
+};
+

 /// 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> CounterMoveHistory;
 /// 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> CounterMoveHistory;


@@ -93,9 +125,9 @@ class MovePicker {
 public:
   MovePicker(const MovePicker&) = delete;
   MovePicker& operator=(const MovePicker&) = delete;
 public:
   MovePicker(const MovePicker&) = delete;
   MovePicker& operator=(const MovePicker&) = delete;

-  MovePicker(const Position&, Move, Value);
-  MovePicker(const Position&, Move, Depth, const ButterflyHistory*, Square);
-  MovePicker(const Position&, Move, Depth, const ButterflyHistory*, const PieceToHistory**, Move, Move*);
+  MovePicker(const Position&, Move, Value, const CapturePieceToHistory*);
+  MovePicker(const Position&, Move, Depth, const ButterflyHistory*,  const CapturePieceToHistory*, Square);
+  MovePicker(const Position&, Move, Depth, const ButterflyHistory*, const CapturePieceToHistory*, const PieceToHistory**, Move, Move*);

   Move next_move(bool skipQuiets = false);
 
 private:
   Move next_move(bool skipQuiets = false);
 
 private:


@@ -105,6 +137,7 @@ private:
 
   const Position& pos;
   const ButterflyHistory* mainHistory;
 
   const Position& pos;
   const ButterflyHistory* mainHistory;

+  const CapturePieceToHistory* captureHistory;

   const PieceToHistory** contHistory;
   Move ttMove, countermove, killers[2];
   ExtMove *cur, *endMoves, *endBadCaptures;
   const PieceToHistory** contHistory;
   Move ttMove, countermove, killers[2];
   ExtMove *cur, *endMoves, *endBadCaptures;

diff --git a/src/search.cpp b/src/search.cpp
index 34a478c54d33a7dc380d9a0c8505ef949a730915..7945170484d20181dee1bdbfe3b559bb079b58ad 100644 (file)
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -109,6 +109,7 @@ namespace {
   void update_pv(Move* pv, Move move, Move* childPv);
   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);
   void update_pv(Move* pv, Move move, Move* childPv);
   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);

+  void update_capture_stats(const Position& pos, Move move, Move* captures, int captureCnt, int bonus);

   bool pv_is_draw(Position& pos);
 
   // perft() is our utility to verify move generation. All the leaf nodes up
   bool pv_is_draw(Position& pos);
 
   // perft() is our utility to verify move generation. All the leaf nodes up


@@ -500,7 +501,7 @@ namespace {
     assert(!(PvNode && cutNode));
     assert(depth / ONE_PLY * ONE_PLY == depth);
 
     assert(!(PvNode && cutNode));
     assert(depth / ONE_PLY * ONE_PLY == depth);
 

-    Move pv[MAX_PLY+1], quietsSearched[64];
+    Move pv[MAX_PLY+1], capturesSearched[32], quietsSearched[64];

     StateInfo st;
     TTEntry* tte;
     Key posKey;
     StateInfo st;
     TTEntry* tte;
     Key posKey;


@@ -510,12 +511,12 @@ namespace {
     bool ttHit, inCheck, givesCheck, singularExtensionNode, improving;
     bool captureOrPromotion, doFullDepthSearch, moveCountPruning, skipQuiets, ttCapture, pvExact;
     Piece movedPiece;
     bool ttHit, inCheck, givesCheck, singularExtensionNode, improving;
     bool captureOrPromotion, doFullDepthSearch, moveCountPruning, skipQuiets, ttCapture, pvExact;
     Piece movedPiece;

-    int moveCount, quietCount;
+    int moveCount, captureCount, quietCount;

 
     // Step 1. Initialize node
     Thread* thisThread = pos.this_thread();
     inCheck = pos.checkers();
 
     // Step 1. Initialize node
     Thread* thisThread = pos.this_thread();
     inCheck = pos.checkers();

-    moveCount = quietCount = ss->moveCount = 0;
+    moveCount = captureCount = quietCount = ss->moveCount = 0;

     ss->statScore = 0;
     bestValue = -VALUE_INFINITE;
 
     ss->statScore = 0;
     bestValue = -VALUE_INFINITE;
 


@@ -579,6 +580,8 @@ namespace {
             {
                 if (!pos.capture_or_promotion(ttMove))
                     update_stats(pos, ss, ttMove, nullptr, 0, stat_bonus(depth));
             {
                 if (!pos.capture_or_promotion(ttMove))
                     update_stats(pos, ss, ttMove, nullptr, 0, stat_bonus(depth));

+                else
+                    update_capture_stats(pos, ttMove, nullptr, 0, stat_bonus(depth));

 
                 // Extra penalty for a quiet TT move in previous ply when it gets refuted
                 if ((ss-1)->moveCount == 1 && !pos.captured_piece())
 
                 // Extra penalty for a quiet TT move in previous ply when it gets refuted
                 if ((ss-1)->moveCount == 1 && !pos.captured_piece())


@@ -729,7 +732,7 @@ namespace {
 
         assert(is_ok((ss-1)->currentMove));
 
 
         assert(is_ok((ss-1)->currentMove));
 

-        MovePicker mp(pos, ttMove, rbeta - ss->staticEval);
+        MovePicker mp(pos, ttMove, rbeta - ss->staticEval, &thisThread->captureHistory);

 
         while ((move = mp.next_move()) != MOVE_NONE)
             if (pos.legal(move))
 
         while ((move = mp.next_move()) != MOVE_NONE)
             if (pos.legal(move))


@@ -763,7 +766,7 @@ moves_loop: // When in check search starts from here
     const PieceToHistory* contHist[] = { (ss-1)->contHistory, (ss-2)->contHistory, nullptr, (ss-4)->contHistory };
     Move countermove = thisThread->counterMoves[pos.piece_on(prevSq)][prevSq];
 
     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, &thisThread->mainHistory, contHist, countermove, ss->killers);
+    MovePicker mp(pos, ttMove, depth, &thisThread->mainHistory, &thisThread->captureHistory, 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 */
     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 */


@@ -1054,6 +1057,8 @@ moves_loop: // When in check search starts from here
 
       if (!captureOrPromotion && move != bestMove && quietCount < 64)
           quietsSearched[quietCount++] = move;
 
       if (!captureOrPromotion && move != bestMove && quietCount < 64)
           quietsSearched[quietCount++] = move;

+      else if (captureOrPromotion && move != bestMove && captureCount < 32)
+          capturesSearched[captureCount++] = move;

     }
 
     // The following condition would detect a stop only after move loop has been
     }
 
     // The following condition would detect a stop only after move loop has been


@@ -1079,6 +1084,8 @@ moves_loop: // When in check search starts from here
         // Quiet best move: update move sorting heuristics
         if (!pos.capture_or_promotion(bestMove))
             update_stats(pos, ss, bestMove, quietsSearched, quietCount, stat_bonus(depth));
         // Quiet best move: update move sorting heuristics
         if (!pos.capture_or_promotion(bestMove))
             update_stats(pos, ss, bestMove, quietsSearched, quietCount, stat_bonus(depth));

+        else
+            update_capture_stats(pos, bestMove, capturesSearched, captureCount, stat_bonus(depth));

 
         // Extra penalty for a quiet TT move in previous ply when it gets refuted
         if ((ss-1)->moveCount == 1 && !pos.captured_piece())
 
         // Extra penalty for a quiet TT move in previous ply when it gets refuted
         if ((ss-1)->moveCount == 1 && !pos.captured_piece())


@@ -1207,7 +1214,7 @@ 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.
     // 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, &pos.this_thread()->mainHistory, to_sq((ss-1)->currentMove));
+    MovePicker mp(pos, ttMove, depth, &pos.this_thread()->mainHistory, &pos.this_thread()->captureHistory, 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)
 
     // Loop through the moves until no moves remain or a beta cutoff occurs
     while ((move = mp.next_move()) != MOVE_NONE)


@@ -1362,6 +1369,26 @@ moves_loop: // When in check search starts from here
   }
 
 
   }
 
 

+  // update_capture_stats() updates move sorting heuristics when a new capture best move is found
+
+  void update_capture_stats(const Position& pos, Move move,
+                            Move* captures, int captureCnt, int bonus) {
+
+      CapturePieceToHistory& captureHistory =  pos.this_thread()->captureHistory;
+      Piece moved_piece = pos.moved_piece(move);
+      PieceType captured = type_of(pos.piece_on(to_sq(move)));
+      captureHistory.update(moved_piece,to_sq(move), captured, bonus);
+
+      // Decrease all the other played capture moves
+      for (int i = 0; i < captureCnt; ++i)
+      {
+          moved_piece = pos.moved_piece(captures[i]);
+          captured = type_of(pos.piece_on(to_sq(captures[i])));
+          captureHistory.update(moved_piece, to_sq(captures[i]), captured, -bonus);
+      }
+  }
+
+

   // update_stats() updates move sorting heuristics when a new quiet best move is found
 
   void update_stats(const Position& pos, Stack* ss, Move move,
   // update_stats() updates move sorting heuristics when a new quiet best move is found
 
   void update_stats(const Position& pos, Stack* ss, Move move,

diff --git a/src/thread.cpp b/src/thread.cpp
index eb360869b53380510513ff134938f0ba515e5cb8..3f3f26cd63f4e6e6f354a1d26ff4fc25febc4640 100644 (file)
--- a/src/thread.cpp
+++ b/src/thread.cpp
@@ -58,6 +58,7 @@ void Thread::clear() {
 
   counterMoves.fill(MOVE_NONE);
   mainHistory.fill(0);
 
   counterMoves.fill(MOVE_NONE);
   mainHistory.fill(0);

+  captureHistory.fill(0);

 
   for (auto& to : contHistory)
       for (auto& h : to)
 
   for (auto& to : contHistory)
       for (auto& h : to)

diff --git a/src/thread.h b/src/thread.h
index 3e9d92446fb5b1c7960fa9b0587b9bb612ad8526..1780abe1da85d821a51312457315b6aa0697e27d 100644 (file)
--- a/src/thread.h
+++ b/src/thread.h
@@ -69,6 +69,7 @@ public:
   Depth rootDepth, completedDepth;
   CounterMoveHistory counterMoves;
   ButterflyHistory mainHistory;
   Depth rootDepth, completedDepth;
   CounterMoveHistory counterMoves;
   ButterflyHistory mainHistory;

+  CapturePieceToHistory captureHistory;

   ContinuationHistory contHistory;
 };
 
   ContinuationHistory contHistory;
 };