From 53ab32ef0b6e47d8d962f8c1fccd32d3c22f138c Mon Sep 17 00:00:00 2001 From: Stefan Geschwentner Date: Sun, 12 Jan 2014 22:42:16 +0100 Subject: [PATCH] Introduce 'follow up' moves When we have a fail-high of a quiet move, store it in a Followupmoves table indexed by the previous move of the same color (instead of immediate previous move as is in countermoves case). Then use this table for quiet moves ordering in the same way we are already doing with countermoves. These followup moves will be tried just after countermoves and before remaining quiet moves. Passed both short TC LLR: 2.95 (-2.94,2.94) [-1.50,4.50] Total: 10350 W: 1998 L: 1866 D: 6486 And long TC LLR: 2.95 (-2.94,2.94) [0.00,6.00] Total: 14066 W: 2303 L: 2137 D: 9626 bench: 7205153 --- src/movepick.cpp | 22 +++++++++++++++++++--- src/movepick.h | 7 ++++--- src/search.cpp | 25 ++++++++++++++++++------- src/search.h | 1 + 4 files changed, 42 insertions(+), 13 deletions(-) diff --git a/src/movepick.cpp b/src/movepick.cpp index ba30a2bc..2a57605e 100644 --- a/src/movepick.cpp +++ b/src/movepick.cpp @@ -71,13 +71,14 @@ namespace { /// ordering is at the current node. MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const HistoryStats& h, - Move* cm, Search::Stack* s) : pos(p), history(h), depth(d) { + Move* cm, Move* fm, Search::Stack* s) : pos(p), history(h), depth(d) { assert(d > DEPTH_ZERO); cur = end = moves; endBadCaptures = moves + MAX_MOVES - 1; countermoves = cm; + followupmoves = fm; ss = s; if (p.checkers()) @@ -230,15 +231,28 @@ void MovePicker::generate_next() { killers[0].move = ss->killers[0]; killers[1].move = ss->killers[1]; killers[2].move = killers[3].move = MOVE_NONE; + killers[4].move = killers[5].move = MOVE_NONE; // Be sure countermoves are different from killers for (int i = 0; i < 2; ++i) - if (countermoves[i] != cur->move && countermoves[i] != (cur+1)->move) + if ( countermoves[i] != (cur+0)->move + && countermoves[i] != (cur+1)->move) (end++)->move = countermoves[i]; if (countermoves[1] && countermoves[1] == countermoves[0]) // Due to SMP races killers[3].move = MOVE_NONE; + // Be sure followupmoves are different from killers and countermoves + for (int i = 0; i < 2; ++i) + if ( followupmoves[i] != (cur+0)->move + && followupmoves[i] != (cur+1)->move + && followupmoves[i] != (cur+2)->move + && followupmoves[i] != (cur+3)->move) + (end++)->move = followupmoves[i]; + + if (followupmoves[1] && followupmoves[1] == followupmoves[0]) // Due to SMP races + (--end)->move = MOVE_NONE; + return; case QUIETS_1_S1: @@ -330,7 +344,9 @@ Move MovePicker::next_move() { && move != killers[0].move && move != killers[1].move && move != killers[2].move - && move != killers[3].move) + && move != killers[3].move + && move != killers[4].move + && move != killers[5].move) return move; break; diff --git a/src/movepick.h b/src/movepick.h index 96986c84..21ea9ab3 100644 --- a/src/movepick.h +++ b/src/movepick.h @@ -69,7 +69,7 @@ private: typedef Stats< true, Value> GainsStats; typedef Stats HistoryStats; -typedef Stats > CountermovesStats; +typedef Stats > MovesStats; /// MovePicker class is used to pick one pseudo legal move at a time from the @@ -86,7 +86,7 @@ class MovePicker { public: MovePicker(const Position&, Move, Depth, const HistoryStats&, Square); MovePicker(const Position&, Move, const HistoryStats&, PieceType); - MovePicker(const Position&, Move, Depth, const HistoryStats&, Move*, Search::Stack*); + MovePicker(const Position&, Move, Depth, const HistoryStats&, Move*, Move*, Search::Stack*); template Move next_move(); @@ -98,9 +98,10 @@ private: const HistoryStats& history; Search::Stack* ss; Move* countermoves; + Move* followupmoves; Depth depth; Move ttMove; - ExtMove killers[4]; + ExtMove killers[6]; Square recaptureSquare; int captureThreshold, stage; ExtMove *cur, *end, *endQuiets, *endBadCaptures; diff --git a/src/search.cpp b/src/search.cpp index a08256d7..d59fc521 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -83,7 +83,7 @@ namespace { Value DrawValue[COLOR_NB]; HistoryStats History; GainsStats Gains; - CountermovesStats Countermoves; + MovesStats Countermoves, Followupmoves; template Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode); @@ -304,6 +304,7 @@ namespace { History.clear(); Gains.clear(); Countermoves.clear(); + Followupmoves.clear(); PVSize = Options["MultiPV"]; Skill skill(Options["Skill Level"]); @@ -499,7 +500,7 @@ namespace { moveCount = quietCount = 0; bestValue = -VALUE_INFINITE; - ss->currentMove = (ss+1)->excludedMove = bestMove = MOVE_NONE; + ss->currentMove = ss->ttMove = (ss+1)->excludedMove = bestMove = MOVE_NONE; ss->ply = (ss-1)->ply + 1; (ss+1)->skipNullMove = false; (ss+1)->reduction = DEPTH_ZERO; (ss+2)->killers[0] = (ss+2)->killers[1] = MOVE_NONE; @@ -532,7 +533,7 @@ namespace { excludedMove = ss->excludedMove; posKey = excludedMove ? pos.exclusion_key() : pos.key(); tte = TT.probe(posKey); - ttMove = RootNode ? RootMoves[PVIdx].pv[0] : tte ? tte->move() : MOVE_NONE; + ss->ttMove = ttMove = RootNode ? RootMoves[PVIdx].pv[0] : tte ? tte->move() : MOVE_NONE; ttValue = tte ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE; // At PV nodes we check for exact scores, whilst at non-PV nodes we check for @@ -550,7 +551,7 @@ namespace { TT.refresh(tte); ss->currentMove = ttMove; // Can be MOVE_NONE - // If ttMove is quiet, update killers, history, and counter move on TT hit + // If ttMove is quiet, update killers, history, counter move and followup move on TT hit if (ttValue >= beta && ttMove && !pos.capture_or_promotion(ttMove) && !inCheck) update_stats(pos, ss, ttMove, depth, NULL, 0); @@ -712,7 +713,11 @@ moves_loop: // When in check and at SpNode search starts from here Move countermoves[] = { Countermoves[pos.piece_on(prevMoveSq)][prevMoveSq].first, Countermoves[pos.piece_on(prevMoveSq)][prevMoveSq].second }; - MovePicker mp(pos, ttMove, depth, History, countermoves, ss); + Square prevOwnMoveSq = to_sq((ss-2)->currentMove); + Move followupmoves[] = { Followupmoves[pos.piece_on(prevOwnMoveSq)][prevOwnMoveSq].first, + Followupmoves[pos.piece_on(prevOwnMoveSq)][prevOwnMoveSq].second }; + + MovePicker mp(pos, ttMove, depth, History, countermoves, followupmoves, ss); CheckInfo ci(pos); value = bestValue; // Workaround a bogus 'uninitialized' warning under gcc improving = ss->staticEval >= (ss-2)->staticEval @@ -1029,7 +1034,7 @@ moves_loop: // When in check and at SpNode search starts from here PvNode && bestMove ? BOUND_EXACT : BOUND_UPPER, depth, bestMove, ss->staticEval); - // Quiet best move: update killers, history and countermoves + // Quiet best move: update killers, history, countermoves and followupmoves if (bestValue >= beta && !pos.capture_or_promotion(bestMove) && !inCheck) update_stats(pos, ss, bestMove, depth, quietsSearched, quietCount - 1); @@ -1264,7 +1269,7 @@ moves_loop: // When in check and at SpNode search starts from here } - // update_stats() updates killers, history and countermoves stats after a fail-high + // update_stats() updates killers, history, countermoves and followupmoves stats after a fail-high // of a quiet move. void update_stats(Position& pos, Stack* ss, Move move, Depth depth, Move* quiets, int quietsCnt) { @@ -1290,6 +1295,12 @@ moves_loop: // When in check and at SpNode search starts from here Square prevMoveSq = to_sq((ss-1)->currentMove); Countermoves.update(pos.piece_on(prevMoveSq), prevMoveSq, move); } + + if (is_ok((ss-2)->currentMove) && (ss-1)->currentMove == (ss-1)->ttMove) + { + Square prevOwnMoveSq = to_sq((ss-2)->currentMove); + Followupmoves.update(pos.piece_on(prevOwnMoveSq), prevOwnMoveSq, move); + } } diff --git a/src/search.h b/src/search.h index ab1076cd..25e71a84 100644 --- a/src/search.h +++ b/src/search.h @@ -41,6 +41,7 @@ struct Stack { SplitPoint* splitPoint; int ply; Move currentMove; + Move ttMove; Move excludedMove; Move killers[2]; Depth reduction; -- 2.39.2