From: Michael Chaly <26898827+Vizvezdenec@users.noreply.github.com> Date: Fri, 27 Oct 2023 15:19:31 +0000 (+0200) Subject: Introduce pawn structure based history X-Git-Url: https://git.sesse.net/?p=stockfish;a=commitdiff_plain;h=b0658f09b93185e2b43d4b2d6f0daa30c36ebcc2 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 Co-Authored-By: Stefan Geschwentner --- diff --git a/src/movepick.cpp b/src/movepick.cpp index d2a49706..444477cf 100644 --- 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 65e93dda..f210f538 100644 --- 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; // (~63 elo) using ContinuationHistory = Stats; +// PawnStructureHistory is addressed by the pawn structure and a move's [piece][to] +using PawnHistory = Stats; // 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 37c586ab..2bb47871 100644 --- 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(); - Zobrist::side = rng.rand(); + Zobrist::side = rng.rand(); + Zobrist::noPawns = rng.rand(); // 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(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 2aeb8fcd..ce03c34f 100644 --- 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 24f0d994..0ffca247 100644 --- 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 fdf89095..bc884ded 100644 --- 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 5f33b736..37a4a6ca 100644 --- a/src/thread.h +++ b/src/thread.h @@ -71,6 +71,7 @@ class Thread { ButterflyHistory mainHistory; CapturePieceToHistory captureHistory; ContinuationHistory continuationHistory[2][2]; + PawnHistory pawnHistory; };