From: Stefan Geschwentner Date: Fri, 3 Nov 2017 11:37:11 +0000 (+0100) Subject: Introduce capture history table for capture move sorting X-Git-Url: https://git.sesse.net/?p=stockfish;a=commitdiff_plain;h=4bc11984fc5a148ee8f1b55d6ac47c4a397cc8b8 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 1c0de699..06935b0d 100644 --- 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, - 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); @@ -80,8 +80,8 @@ MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const ButterflyHist } /// 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); @@ -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::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()); @@ -132,7 +132,7 @@ void MovePicker::score() { 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)] diff --git a/src/movepick.h b/src/movepick.h index 66fc1bdb..db9439f7 100644 --- a/src/movepick.h +++ b/src/movepick.h @@ -22,6 +22,7 @@ #define MOVEPICK_H_INCLUDED #include +#include #include "movegen.h" #include "position.h" @@ -39,7 +40,7 @@ struct StatBoards : public std::array, Size1> { 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::max)()); // Ensure we don't overflow entry += bonus * 32 - entry * abs(bonus) / D; @@ -47,6 +48,26 @@ struct StatBoards : public std::array, Size1> { } }; +/// StatCubes is a generic 3-dimensional array used to store various statistics +template +struct StatCubes : public std::array, 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::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 ButterflyBoards; @@ -54,6 +75,9 @@ typedef StatBoards ButterflyBoards; /// PieceToBoards are addressed by a move's [piece][to] information typedef StatBoards PieceToBoards; +/// CapturePieceToBoards are addressed by a move's [piece][to][captured piece type] information +typedef StatCubes 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. @@ -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 CounterMoveHistory; @@ -93,9 +125,9 @@ class MovePicker { 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: @@ -105,6 +137,7 @@ private: const Position& pos; const ButterflyHistory* mainHistory; + const CapturePieceToHistory* captureHistory; const PieceToHistory** contHistory; Move ttMove, countermove, killers[2]; ExtMove *cur, *endMoves, *endBadCaptures; diff --git a/src/search.cpp b/src/search.cpp index 34a478c5..79451704 100644 --- 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_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 @@ -500,7 +501,7 @@ namespace { 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; @@ -510,12 +511,12 @@ namespace { 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(); - moveCount = quietCount = ss->moveCount = 0; + moveCount = captureCount = quietCount = ss->moveCount = 0; 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)); + 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()) @@ -729,7 +732,7 @@ namespace { 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)) @@ -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]; - 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 */ @@ -1054,6 +1057,8 @@ moves_loop: // When in check search starts from here 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 @@ -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)); + 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()) @@ -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. - 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) @@ -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, diff --git a/src/thread.cpp b/src/thread.cpp index eb360869..3f3f26cd 100644 --- a/src/thread.cpp +++ b/src/thread.cpp @@ -58,6 +58,7 @@ void Thread::clear() { counterMoves.fill(MOVE_NONE); mainHistory.fill(0); + captureHistory.fill(0); for (auto& to : contHistory) for (auto& h : to) diff --git a/src/thread.h b/src/thread.h index 3e9d9244..1780abe1 100644 --- a/src/thread.h +++ b/src/thread.h @@ -69,6 +69,7 @@ public: Depth rootDepth, completedDepth; CounterMoveHistory counterMoves; ButterflyHistory mainHistory; + CapturePieceToHistory captureHistory; ContinuationHistory contHistory; };