From: Günther Demetz Date: Fri, 21 Feb 2020 13:01:59 +0000 (+0100) Subject: Improve move order near the root X-Git-Url: https://git.sesse.net/?p=stockfish;a=commitdiff_plain;h=b8c00efa2767ebf74545d2ba4bd344ef7c963319 Improve move order near the root Current move histories are known to work well near the leaves, whilst at higher depths they aren't very helpful. To address this problem this patch introduces a table dedicated for what's happening at plies 0-3. It's structured like mainHistory with ply index instead of color. It get cleared with each new search and is filled during iterative deepening at higher depths when recording successful quiet moves near the root or traversing nodes which were in the principal variation (ttPv). Medium TC (20+0.2): https://tests.stockfishchess.org/tests/view/5e4d358790a0a02810d096dc LLR: 2.94 (-2.94,2.94) {-0.50,1.50} Total: 100910 W: 16682 L: 16376 D: 67852 Ptnml(0-2): 1177, 10983, 25883, 11181, 1231 LTC: https://tests.stockfishchess.org/tests/view/5e4e2cb790a0a02810d09714 LLR: 2.95 (-2.94,2.94) {0.25,1.75} Total: 80444 W: 10495 L: 10095 D: 59854 Ptnml(0-2): 551, 7479, 23803, 7797, 592 closes https://github.com/official-stockfish/Stockfish/pull/2557 Bench: 4705960 --- diff --git a/src/movepick.cpp b/src/movepick.cpp index 025f5b82..575c9022 100644 --- a/src/movepick.cpp +++ b/src/movepick.cpp @@ -56,10 +56,10 @@ namespace { /// ordering is at the current node. /// MovePicker constructor for the main search -MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const ButterflyHistory* mh, - const CapturePieceToHistory* cph, const PieceToHistory** ch, Move cm, Move* killers) - : pos(p), mainHistory(mh), captureHistory(cph), continuationHistory(ch), - refutations{{killers[0], 0}, {killers[1], 0}, {cm, 0}}, depth(d) { +MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const ButterflyHistory* mh, const LowPlyHistory* lp, + const CapturePieceToHistory* cph, const PieceToHistory** ch, Move cm, Move* killers, int pl) + : pos(p), mainHistory(mh), lowPlyHistory(lp), captureHistory(cph), continuationHistory(ch), + refutations{{killers[0], 0}, {killers[1], 0}, {cm, 0}}, depth(d) , ply(pl) { assert(d > 0); @@ -115,7 +115,8 @@ void MovePicker::score() { + 2 * (*continuationHistory[0])[pos.moved_piece(m)][to_sq(m)] + 2 * (*continuationHistory[1])[pos.moved_piece(m)][to_sq(m)] + 2 * (*continuationHistory[3])[pos.moved_piece(m)][to_sq(m)] - + (*continuationHistory[5])[pos.moved_piece(m)][to_sq(m)]; + + (*continuationHistory[5])[pos.moved_piece(m)][to_sq(m)] + + (ply < MAX_LPH ? 4 * (*lowPlyHistory)[ply][from_to(m)] : 0); else // Type == EVASIONS { diff --git a/src/movepick.h b/src/movepick.h index cdedc9b6..33c4b086 100644 --- a/src/movepick.h +++ b/src/movepick.h @@ -88,6 +88,12 @@ enum StatsType { NoCaptures, Captures }; /// the move's from and to squares, see www.chessprogramming.org/Butterfly_Boards typedef Stats ButterflyHistory; +/// LowPlyHistory at higher depths records successful quiet moves on plies 0 to 3 +/// and quiet moves which are/were in the PV (ttPv) +/// It get cleared with each new search and get filled during iterative deepening +constexpr int MAX_LPH = 4; +typedef Stats LowPlyHistory; + /// CounterMoveHistory stores counter moves indexed by [piece][to] of the previous /// move, see www.chessprogramming.org/Countermove_Heuristic typedef Stats CounterMoveHistory; @@ -123,10 +129,12 @@ public: const PieceToHistory**, Square); MovePicker(const Position&, Move, Depth, const ButterflyHistory*, + const LowPlyHistory*, const CapturePieceToHistory*, const PieceToHistory**, Move, - Move*); + Move*, + int); Move next_move(bool skipQuiets = false); private: @@ -137,6 +145,7 @@ private: const Position& pos; const ButterflyHistory* mainHistory; + const LowPlyHistory* lowPlyHistory; const CapturePieceToHistory* captureHistory; const PieceToHistory** continuationHistory; Move ttMove; @@ -145,6 +154,7 @@ private: Square recaptureSquare; Value threshold; Depth depth; + int ply; ExtMove moves[MAX_MOVES]; }; diff --git a/src/search.cpp b/src/search.cpp index c3ebf9ab..3f860ac5 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -156,7 +156,7 @@ namespace { Value value_from_tt(Value v, int ply, int r50c); void update_pv(Move* pv, Move move, Move* childPv); void update_continuation_histories(Stack* ss, Piece pc, Square to, int bonus); - void update_quiet_stats(const Position& pos, Stack* ss, Move move, int bonus); + void update_quiet_stats(const Position& pos, Stack* ss, Move move, int bonus, int depth); void update_all_stats(const Position& pos, Stack* ss, Move bestMove, Value bestValue, Value beta, Square prevSq, Move* quietsSearched, int quietCount, Move* capturesSearched, int captureCount, Depth depth); @@ -695,6 +695,10 @@ namespace { ttMove = rootNode ? thisThread->rootMoves[thisThread->pvIdx].pv[0] : ttHit ? tte->move() : MOVE_NONE; ttPv = PvNode || (ttHit && tte->is_pv()); + + if (ttPv && depth > 12 && ss->ply - 1 < MAX_LPH && !pos.captured_piece() && is_ok((ss-1)->currentMove)) + thisThread->lowPlyHistory[ss->ply - 1][from_to((ss-1)->currentMove)] << stat_bonus(depth - 5); + // thisThread->ttHitAverage can be used to approximate the running average of ttHit thisThread->ttHitAverage = (ttHitAverageWindow - 1) * thisThread->ttHitAverage / ttHitAverageWindow + ttHitAverageResolution * ttHit; @@ -713,7 +717,7 @@ namespace { if (ttValue >= beta) { if (!pos.capture_or_promotion(ttMove)) - update_quiet_stats(pos, ss, ttMove, stat_bonus(depth)); + update_quiet_stats(pos, ss, ttMove, stat_bonus(depth), depth); // Extra penalty for early quiet moves of the previous ply if ((ss-1)->moveCount <= 2 && !priorCapture) @@ -948,10 +952,12 @@ moves_loop: // When in check, search starts from here Move countermove = thisThread->counterMoves[pos.piece_on(prevSq)][prevSq]; MovePicker mp(pos, ttMove, depth, &thisThread->mainHistory, + &thisThread->lowPlyHistory, &thisThread->captureHistory, contHist, countermove, - ss->killers); + ss->killers, + depth > 12 && ttPv ? ss->ply : MAX_PLY); value = bestValue; singularLMR = moveCountPruning = false; @@ -1633,7 +1639,7 @@ moves_loop: // When in check, search starts from here if (!pos.capture_or_promotion(bestMove)) { - update_quiet_stats(pos, ss, bestMove, bonus2); + update_quiet_stats(pos, ss, bestMove, bonus2, depth); // Decrease all the non-best quiet moves for (int i = 0; i < quietCount; ++i) @@ -1673,7 +1679,7 @@ moves_loop: // When in check, search starts from here // update_quiet_stats() updates move sorting heuristics - void update_quiet_stats(const Position& pos, Stack* ss, Move move, int bonus) { + void update_quiet_stats(const Position& pos, Stack* ss, Move move, int bonus, int depth) { if (ss->killers[0] != move) { @@ -1694,6 +1700,9 @@ moves_loop: // When in check, search starts from here Square prevSq = to_sq((ss-1)->currentMove); thisThread->counterMoves[pos.piece_on(prevSq)][prevSq] = move; } + + if (depth > 12 && ss->ply < MAX_LPH) + thisThread->lowPlyHistory[ss->ply][from_to(move)] << stat_bonus(depth - 7); } // When playing with strength handicap, choose best move among a set of RootMoves diff --git a/src/thread.cpp b/src/thread.cpp index 10ec96dd..b5cb87d9 100644 --- a/src/thread.cpp +++ b/src/thread.cpp @@ -68,6 +68,7 @@ void Thread::clear() { counterMoves.fill(MOVE_NONE); mainHistory.fill(0); + lowPlyHistory.fill(0); captureHistory.fill(0); for (bool inCheck : { false, true }) @@ -211,6 +212,7 @@ void ThreadPool::start_thinking(Position& pos, StateListPtr& states, th->rootDepth = th->completedDepth = 0; th->rootMoves = rootMoves; th->rootPos.set(pos.fen(), pos.is_chess960(), &setupStates->back(), th); + th->lowPlyHistory.fill(0); } setupStates->back() = tmp; diff --git a/src/thread.h b/src/thread.h index 63629e33..41d2b8f6 100644 --- a/src/thread.h +++ b/src/thread.h @@ -71,6 +71,7 @@ public: Depth rootDepth, completedDepth; CounterMoveHistory counterMoves; ButterflyHistory mainHistory; + LowPlyHistory lowPlyHistory; CapturePieceToHistory captureHistory; ContinuationHistory continuationHistory[2][2]; Score contempt;