Introduce pawn structure based history

Original idea by Seer chess engine https://github.com/connormcmonigle/seer-nnue,
coding done by @Disservin, code refactoring done by @locutus2 to match the style
of other histories.

This patch introduces pawn structure based history, which assings moves values
based on last digits of pawn structure hash and piece type of moved piece and
landing square of the move. Idea is that good places for pieces are quite often
determined by pawn structure of position. Used in 3 different places
- sorting of quiet moves, sorting of quiet check evasions and in history based
pruning in search.

Passed STC:
https://tests.stockfishchess.org/tests/view/65391d08cc309ae83955dbaf
LLR: 2.95 (-2.94,2.94) <0.00,2.00>
Total: 155488 W: 39408 L: 38913 D: 77167
Ptnml(0-2): 500, 18427, 39408, 18896, 513

Passed LTC:
https://tests.stockfishchess.org/tests/view/653a36a2cc309ae83955f181
LLR: 2.94 (-2.94,2.94) <0.50,2.50>
Total: 70110 W: 17548 L: 17155 D: 35407
Ptnml(0-2): 33, 7859, 18889, 8230, 44

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

Bench: 1257882

Co-Authored-By: Disservin <disservin.social@gmail.com>
Co-Authored-By: Stefan Geschwentner <locutus2@users.noreply.github.com>

diff --git a/src/movepick.cpp b/src/movepick.cpp
index d2a49706fc27e34a5b75d0179cb9f16f7cec8d72..444477cf78efb9c086742aac25ddf0142d48527f 100644 (file)
--- a/src/movepick.cpp
+++ b/src/movepick.cpp
@@ -89,12 +89,14 @@ MovePicker::MovePicker(const Position&              p,
                        const ButterflyHistory*      mh,
                        const CapturePieceToHistory* cph,
                        const PieceToHistory**       ch,
+                       const PawnHistory&           ph,
                        Move                         cm,
                        const Move*                  killers) :
     pos(p),
     mainHistory(mh),
     captureHistory(cph),
     continuationHistory(ch),
+    pawnHistory(ph),
     ttMove(ttm),
     refutations{{killers[0], 0}, {killers[1], 0}, {cm, 0}},
     depth(d) {
@@ -110,11 +112,13 @@ MovePicker::MovePicker(const Position&              p,
                        const ButterflyHistory*      mh,
                        const CapturePieceToHistory* cph,
                        const PieceToHistory**       ch,
+                       const PawnHistory&           ph,
                        Square                       rs) :
     pos(p),
     mainHistory(mh),
     captureHistory(cph),
     continuationHistory(ch),
+    pawnHistory(ph),
     ttMove(ttm),
     recaptureSquare(rs),
     depth(d) {
@@ -125,9 +129,11 @@ MovePicker::MovePicker(const Position&              p,
 
 // Constructor for ProbCut: we generate captures with SEE greater
 // than or equal to the given threshold.
-MovePicker::MovePicker(const Position& p, Move ttm, Value th, const CapturePieceToHistory* cph) :
+MovePicker::MovePicker(
+  const Position& p, Move ttm, Value th, const CapturePieceToHistory* cph, const PawnHistory& ph) :
     pos(p),
     captureHistory(cph),
+    pawnHistory(ph),
     ttMove(ttm),
     threshold(th) {
     assert(!pos.checkers());
@@ -203,6 +209,8 @@ void MovePicker::score() {
                           : pt != PAWN ? bool(to & threatenedByPawn) * 15000
                                        : 0)
                        : 0;
+
+            m.value += pawnHistory[pawn_structure(pos)][pc][to];
         }
 
         else  // Type == EVASIONS
@@ -212,7 +220,8 @@ void MovePicker::score() {
                         + (1 << 28);
             else
                 m.value = (*mainHistory)[pos.side_to_move()][from_to(m)]
-                        + (*continuationHistory[0])[pos.moved_piece(m)][to_sq(m)];
+                        + (*continuationHistory[0])[pos.moved_piece(m)][to_sq(m)]
+                        + pawnHistory[pawn_structure(pos)][pos.moved_piece(m)][to_sq(m)];
         }
 }
 

diff --git a/src/movepick.h b/src/movepick.h
index 65e93dda6fe3c1eb0d0b52ce7d66c1609e47c502..f210f5387fcb222bb8a0728e4a9e413a2a7b583b 100644 (file)
--- a/src/movepick.h
+++ b/src/movepick.h
@@ -28,9 +28,13 @@
 
 #include "movegen.h"
 #include "types.h"
+#include "position.h"
 
 namespace Stockfish {
-class Position;
+
+constexpr int PAWN_HISTORY_SIZE = 512;
+
+inline int pawn_structure(const Position& pos) { return pos.pawn_key() & (PAWN_HISTORY_SIZE - 1); }
 
 // StatsEntry stores the stat table value. It is usually a number but could
 // be a move or even a nested history. We use a class instead of a naked value
@@ -112,6 +116,8 @@ using PieceToHistory = Stats<int16_t, 29952, PIECE_NB, SQUARE_NB>;
 // (~63 elo)
 using ContinuationHistory = Stats<PieceToHistory, NOT_USED, PIECE_NB, SQUARE_NB>;
 
+// PawnStructureHistory is addressed by the pawn structure and a move's [piece][to]
+using PawnHistory = Stats<int16_t, 8192, PAWN_HISTORY_SIZE, PIECE_NB, SQUARE_NB>;
 
 // MovePicker class is used to pick one pseudo-legal move at a time from the
 // current position. The most important method is next_move(), which returns a
@@ -135,6 +141,7 @@ class MovePicker {
                const ButterflyHistory*,
                const CapturePieceToHistory*,
                const PieceToHistory**,
+               const PawnHistory&,
                Move,
                const Move*);
     MovePicker(const Position&,
@@ -143,8 +150,9 @@ class MovePicker {
                const ButterflyHistory*,
                const CapturePieceToHistory*,
                const PieceToHistory**,
+               const PawnHistory&,
                Square);
-    MovePicker(const Position&, Move, Value, const CapturePieceToHistory*);
+    MovePicker(const Position&, Move, Value, const CapturePieceToHistory*, const PawnHistory&);
     Move next_move(bool skipQuiets = false);
 
    private:
@@ -159,6 +167,7 @@ class MovePicker {
     const ButterflyHistory*      mainHistory;
     const CapturePieceToHistory* captureHistory;
     const PieceToHistory**       continuationHistory;
+    const PawnHistory&           pawnHistory;
     Move                         ttMove;
     ExtMove                      refutations[3], *cur, *endMoves, *endBadCaptures;
     int                          stage;

diff --git a/src/position.cpp b/src/position.cpp
index 37c586abbaa537771fdef27a195ee2945707acf0..2bb47871555a3279c082b5432798d040569b508e 100644 (file)
--- a/src/position.cpp
+++ b/src/position.cpp
@@ -49,7 +49,7 @@ namespace Zobrist {
 Key psq[PIECE_NB][SQUARE_NB];
 Key enpassant[FILE_NB];
 Key castling[CASTLING_RIGHT_NB];
-Key side;
+Key side, noPawns;
 }
 
 namespace {
@@ -128,7 +128,8 @@ void Position::init() {
     for (int cr = NO_CASTLING; cr <= ANY_CASTLING; ++cr)
         Zobrist::castling[cr] = rng.rand<Key>();
 
-    Zobrist::side = rng.rand<Key>();
+    Zobrist::side    = rng.rand<Key>();
+    Zobrist::noPawns = rng.rand<Key>();
 
     // Prepare the cuckoo tables
     std::memset(cuckoo, 0, sizeof(cuckoo));
@@ -337,6 +338,7 @@ void Position::set_check_info() const {
 void Position::set_state() const {
 
     st->key = st->materialKey  = 0;
+    st->pawnKey                = Zobrist::noPawns;
     st->nonPawnMaterial[WHITE] = st->nonPawnMaterial[BLACK] = VALUE_ZERO;
     st->checkersBB = attackers_to(square<KING>(sideToMove)) & pieces(~sideToMove);
 
@@ -348,7 +350,10 @@ void Position::set_state() const {
         Piece  pc = piece_on(s);
         st->key ^= Zobrist::psq[pc][s];
 
-        if (type_of(pc) != KING && type_of(pc) != PAWN)
+        if (type_of(pc) == PAWN)
+            st->pawnKey ^= Zobrist::psq[pc][s];
+
+        else if (type_of(pc) != KING)
             st->nonPawnMaterial[color_of(pc)] += PieceValue[pc];
     }
 
@@ -728,6 +733,8 @@ void Position::do_move(Move m, StateInfo& newSt, bool givesCheck) {
                 assert(piece_on(to) == NO_PIECE);
                 assert(piece_on(capsq) == make_piece(them, PAWN));
             }
+
+            st->pawnKey ^= Zobrist::psq[captured][capsq];
         }
         else
             st->nonPawnMaterial[them] -= PieceValue[captured];
@@ -806,6 +813,7 @@ void Position::do_move(Move m, StateInfo& newSt, bool givesCheck) {
 
             // Update hash keys
             k ^= Zobrist::psq[pc][to] ^ Zobrist::psq[promotion][to];
+            st->pawnKey ^= Zobrist::psq[pc][to];
             st->materialKey ^=
               Zobrist::psq[promotion][pieceCount[promotion] - 1] ^ Zobrist::psq[pc][pieceCount[pc]];
 
@@ -813,6 +821,9 @@ void Position::do_move(Move m, StateInfo& newSt, bool givesCheck) {
             st->nonPawnMaterial[us] += PieceValue[promotion];
         }
 
+        // Update pawn hash key
+        st->pawnKey ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to];
+
         // Reset rule 50 draw counter
         st->rule50 = 0;
     }

diff --git a/src/position.h b/src/position.h
index 2aeb8fcd575e8275a6348cc7fefa72b5695d7b84..ce03c34f3325de63102b910ff570b3456f0e8b31 100644 (file)
--- a/src/position.h
+++ b/src/position.h
@@ -39,6 +39,7 @@ struct StateInfo {
 
     // Copied when making a move
     Key    materialKey;
+    Key    pawnKey;
     Value  nonPawnMaterial[COLOR_NB];
     int    castlingRights;
     int    rule50;
@@ -146,6 +147,7 @@ class Position {
     Key key() const;
     Key key_after(Move m) const;
     Key material_key() const;
+    Key pawn_key() const;
 
     // Other properties of the position
     Color   side_to_move() const;
@@ -293,6 +295,8 @@ inline Key Position::adjust_key50(Key k) const {
     return st->rule50 < 14 - AfterMove ? k : k ^ make_key((st->rule50 - (14 - AfterMove)) / 8);
 }
 
+inline Key Position::pawn_key() const { return st->pawnKey; }
+
 inline Key Position::material_key() const { return st->materialKey; }
 
 inline Value Position::non_pawn_material(Color c) const { return st->nonPawnMaterial[c]; }

diff --git a/src/search.cpp b/src/search.cpp
index 24f0d9946f7ec598604ba8b60eb937437523847f..0ffca247853faa03b1272d884b3560dc25edfc86 100644 (file)
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -848,7 +848,8 @@ Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, boo
     {
         assert(probCutBeta < VALUE_INFINITE);
 
-        MovePicker mp(pos, ttMove, probCutBeta - ss->staticEval, &captureHistory);
+        MovePicker mp(pos, ttMove, probCutBeta - ss->staticEval, &captureHistory,
+                      thisThread->pawnHistory);
 
         while ((move = mp.next_move()) != MOVE_NONE)
             if (move != excludedMove && pos.legal(move))
@@ -904,7 +905,7 @@ moves_loop:  // When in check, search starts here
       prevSq != SQ_NONE ? thisThread->counterMoves[pos.piece_on(prevSq)][prevSq] : MOVE_NONE;
 
     MovePicker mp(pos, ttMove, depth, &thisThread->mainHistory, &captureHistory, contHist,
-                  countermove, ss->killers);
+                  thisThread->pawnHistory, countermove, ss->killers);
 
     value            = bestValue;
     moveCountPruning = singularQuietLMR = false;
@@ -988,7 +989,8 @@ moves_loop:  // When in check, search starts here
             {
                 int history = (*contHist[0])[movedPiece][to_sq(move)]
                             + (*contHist[1])[movedPiece][to_sq(move)]
-                            + (*contHist[3])[movedPiece][to_sq(move)];
+                            + (*contHist[3])[movedPiece][to_sq(move)]
+                            + thisThread->pawnHistory[pawn_structure(pos)][movedPiece][to_sq(move)];
 
                 // Continuation history based pruning (~2 Elo)
                 if (lmrDepth < 6 && history < -3498 * depth)
@@ -1463,7 +1465,7 @@ Value qsearch(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth) {
     // will be generated.
     Square     prevSq = is_ok((ss - 1)->currentMove) ? to_sq((ss - 1)->currentMove) : SQ_NONE;
     MovePicker mp(pos, ttMove, depth, &thisThread->mainHistory, &thisThread->captureHistory,
-                  contHist, prevSq);
+                  contHist, thisThread->pawnHistory, prevSq);
 
     int quietCheckEvasions = 0;
 
@@ -1671,10 +1673,15 @@ void update_all_stats(const Position& pos,
 
         // Increase stats for the best move in case it was a quiet move
         update_quiet_stats(pos, ss, bestMove, bestMoveBonus);
+        thisThread->pawnHistory[pawn_structure(pos)][moved_piece][to_sq(bestMove)]
+          << quietMoveBonus;
 
         // Decrease stats for all non-best quiet moves
         for (int i = 0; i < quietCount; ++i)
         {
+            thisThread->pawnHistory[pawn_structure(pos)][pos.moved_piece(quietsSearched[i])]
+                                   [to_sq(quietsSearched[i])]
+              << -bestMoveBonus;
             thisThread->mainHistory[us][from_to(quietsSearched[i])] << -bestMoveBonus;
             update_continuation_histories(ss, pos.moved_piece(quietsSearched[i]),
                                           to_sq(quietsSearched[i]), -bestMoveBonus);

diff --git a/src/thread.cpp b/src/thread.cpp
index fdf89095b5e79239883cd9d41d30a760f0c685c2..bc884dedf01ed5ef0a4a1c8ed101fe045e8c9571 100644 (file)
--- a/src/thread.cpp
+++ b/src/thread.cpp
@@ -68,6 +68,7 @@ void Thread::clear() {
     counterMoves.fill(MOVE_NONE);
     mainHistory.fill(0);
     captureHistory.fill(0);
+    pawnHistory.fill(0);
 
     for (bool inCheck : {false, true})
         for (StatsType c : {NoCaptures, Captures})

diff --git a/src/thread.h b/src/thread.h
index 5f33b7369d33cf7083b5c2fe75514c3a00023e45..37a4a6ca2bc6215448bab8634656d9d1f8a1d7ed 100644 (file)
--- a/src/thread.h
+++ b/src/thread.h
@@ -71,6 +71,7 @@ class Thread {
     ButterflyHistory      mainHistory;
     CapturePieceToHistory captureHistory;
     ContinuationHistory   continuationHistory[2][2];
+    PawnHistory           pawnHistory;
 };