From 108f0da4d7f993732aa2e854b8f3fa8ca6d3b46c Mon Sep 17 00:00:00 2001 From: syzygy1 <3028851+syzygy1@users.noreply.github.com> Date: Wed, 18 Apr 2018 18:38:38 +0200 Subject: [PATCH] Tablebases root ranking This patch corrects both MultiPV behaviour and "go searchmoves" behaviour for tablebases. We change the logic of table base probing at root positions from filtering to ranking. The ranking code is much more straightforward than the current filtering code (this is a simplification), and also more versatile. If the root is a TB position, each root move is probed and assigned a TB score and a TB rank. The TB score is the Value to be displayed to the user for that move (unless the search finds a mate score), while the TB rank determines which moves should appear higher in a multi-pv search. In game play, the engine will always pick a move with the highest rank. Ranks run from -1000 to +1000: 901 to 1000 : TB win 900 : normally a TB win, in rare cases this could be a draw 1 to 899 : cursed TB wins 0 : draw -1 to -899 : blessed TB losses -900 : normally a TB loss, in rare cases this could be a draw -901 to -1000 : TB loss Normally all winning moves get rank 1000 (to let the search pick the best among them). The exception is if there has been a first repetition. In that case, moves are ranked strictly by DTZ so that the engine will play a move that lowers DTZ (and therefore cannot repeat the position a second time). Losing moves get rank -1000 unless they have relatively high DTZ, meaning they have some drawing chances. Those get ranks towards -901 (when they cross -900 the draw is certain). Closes https://github.com/official-stockfish/Stockfish/pull/1467 No functional change (without tablebases). --- src/position.cpp | 29 +++++ src/position.h | 1 + src/search.cpp | 78 ++++++++------ src/search.h | 2 + src/syzygy/tbprobe.cpp | 235 ++++++++++++----------------------------- src/syzygy/tbprobe.h | 6 +- src/thread.cpp | 2 +- src/thread.h | 2 +- 8 files changed, 147 insertions(+), 208 deletions(-) diff --git a/src/position.cpp b/src/position.cpp index c0e2232c..0be309ee 100644 --- a/src/position.cpp +++ b/src/position.cpp @@ -1105,6 +1105,35 @@ bool Position::is_draw(int ply) const { } +// Position::has_repeated() tests whether there has been at least one repetition +// of positions since the last capture or pawn move. + +bool Position::has_repeated() const { + + StateInfo* stc = st; + while (true) + { + int i = 4, e = std::min(stc->rule50, stc->pliesFromNull); + + if (e < i) + return false; + + StateInfo* stp = st->previous->previous; + + do { + stp = stp->previous->previous; + + if (stp->key == stc->key) + return true; + + i += 2; + } while (i <= e); + + stc = stc->previous; + } +} + + /// Position::flip() flips position with the white and black sides reversed. This /// is only useful for debugging e.g. for finding evaluation symmetry bugs. diff --git a/src/position.h b/src/position.h index bbdab011..0c8f7972 100644 --- a/src/position.h +++ b/src/position.h @@ -152,6 +152,7 @@ public: bool is_chess960() const; Thread* this_thread() const; bool is_draw(int ply) const; + bool has_repeated() const; int rule50_count() const; Score psq_score() const; Value non_pawn_material(Color c) const; diff --git a/src/search.cpp b/src/search.cpp index ad54a726..25383aae 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -48,7 +48,6 @@ namespace Tablebases { bool RootInTB; bool UseRule50; Depth ProbeDepth; - Value Score; } namespace TB = Tablebases; @@ -354,9 +353,20 @@ void Thread::search() { for (RootMove& rm : rootMoves) rm.previousScore = rm.score; + size_t PVFirst = 0; + PVLast = 0; + // MultiPV loop. We perform a full root search for each PV line for (PVIdx = 0; PVIdx < multiPV && !Threads.stop; ++PVIdx) { + if (PVIdx == PVLast) + { + PVFirst = PVLast; + for (PVLast++; PVLast < rootMoves.size(); PVLast++) + if (rootMoves[PVLast].TBRank != rootMoves[PVFirst].TBRank) + break; + } + // Reset UCI info selDepth for each depth and each PV line selDepth = 0; @@ -388,7 +398,7 @@ void Thread::search() { // and we want to keep the same order for all the moves except the // new PV that goes to the front. Note that in case of MultiPV // search the already searched PV lines are preserved. - std::stable_sort(rootMoves.begin() + PVIdx, rootMoves.end()); + std::stable_sort(rootMoves.begin() + PVIdx, rootMoves.begin() + PVLast); // If search has been stopped, we break immediately. Sorting is // safe because RootMoves is still valid, although it refers to @@ -428,7 +438,7 @@ void Thread::search() { } // Sort the PV lines searched so far and update the GUI - std::stable_sort(rootMoves.begin(), rootMoves.begin() + PVIdx + 1); + std::stable_sort(rootMoves.begin() + PVFirst, rootMoves.begin() + PVIdx + 1); if ( mainThread && (Threads.stop || PVIdx + 1 == multiPV || Time.elapsed() > 3000)) @@ -843,9 +853,10 @@ moves_loop: // When in check, search starts from here // At root obey the "searchmoves" option and skip moves not listed in Root // Move List. As a consequence any illegal move is also skipped. In MultiPV - // mode we also skip PV moves which have been already searched. + // mode we also skip PV moves which have been already searched and those + // of lower "TB rank" if we are in a TB root position. if (rootNode && !std::count(thisThread->rootMoves.begin() + thisThread->PVIdx, - thisThread->rootMoves.end(), move)) + thisThread->rootMoves.begin() + thisThread->PVLast, move)) continue; ss->moveCount = ++moveCount; @@ -1557,7 +1568,7 @@ string UCI::pv(const Position& pos, Depth depth, Value alpha, Value beta) { Value v = updated ? rootMoves[i].score : rootMoves[i].previousScore; bool tb = TB::RootInTB && abs(v) < VALUE_MATE - MAX_PLY; - v = tb ? TB::Score : v; + v = tb ? rootMoves[i].TBScore : v; if (ss.rdbuf()->in_avail()) // Not at first line ss << "\n"; @@ -1618,52 +1629,49 @@ bool RootMove::extract_ponder_from_tt(Position& pos) { return pv.size() > 1; } - -void Tablebases::filter_root_moves(Position& pos, Search::RootMoves& rootMoves) { +void Tablebases::rank_root_moves(Position& pos, Search::RootMoves& rootMoves) { RootInTB = false; UseRule50 = Options["Syzygy50MoveRule"]; ProbeDepth = Options["SyzygyProbeDepth"] * ONE_PLY; Cardinality = Options["SyzygyProbeLimit"]; + bool dtz_available = true; - // Skip TB probing when no TB found: !TBLargest -> !TB::Cardinality + // Tables with fewer pieces than SyzygyProbeLimit are searched with + // ProbeDepth == DEPTH_ZERO if (Cardinality > MaxCardinality) { Cardinality = MaxCardinality; ProbeDepth = DEPTH_ZERO; } - if (Cardinality < popcount(pos.pieces()) || pos.can_castle(ANY_CASTLING)) - return; - - // Don't filter any moves if the user requested analysis on multiple - if (Options["MultiPV"] != 1) - return; + if (Cardinality >= popcount(pos.pieces()) && !pos.can_castle(ANY_CASTLING)) + { + // Rank moves using DTZ tables + RootInTB = root_probe(pos, rootMoves); - // If the current root position is in the tablebases, then RootMoves - // contains only moves that preserve the draw or the win. - RootInTB = root_probe(pos, rootMoves, TB::Score); + if (!RootInTB) + { + // DTZ tables are missing; try to rank moves using WDL tables + dtz_available = false; + RootInTB = root_probe_wdl(pos, rootMoves); + } + } if (RootInTB) - Cardinality = 0; // Do not probe tablebases during the search - - else // If DTZ tables are missing, use WDL tables as a fallback { - // Filter out moves that do not preserve the draw or the win. - RootInTB = root_probe_wdl(pos, rootMoves, TB::Score); + // Sort moves according to TB rank + std::sort(rootMoves.begin(), rootMoves.end(), + [](const RootMove &a, const RootMove &b) { return a.TBRank > b.TBRank; } ); - // Only probe during search if winning - if (RootInTB && TB::Score <= VALUE_DRAW) + // Probe during search only if DTZ is not available and we are winning + if (dtz_available || rootMoves[0].TBScore <= VALUE_DRAW) Cardinality = 0; } - - if (RootInTB && !UseRule50) - TB::Score = TB::Score > VALUE_DRAW ? VALUE_MATE - MAX_PLY - 1 - : TB::Score < VALUE_DRAW ? -VALUE_MATE + MAX_PLY + 1 - : VALUE_DRAW; - - // Since root_probe() and root_probe_wdl() dirty the root move scores, - // we reset them to -VALUE_INFINITE - for (RootMove& rm : rootMoves) - rm.score = -VALUE_INFINITE; + else + { + // Assign the same rank to all moves + for (auto& m : rootMoves) + m.TBRank = 0; + } } diff --git a/src/search.h b/src/search.h index 8638a927..2ef53b4c 100644 --- a/src/search.h +++ b/src/search.h @@ -69,6 +69,8 @@ struct RootMove { Value score = -VALUE_INFINITE; Value previousScore = -VALUE_INFINITE; int selDepth = 0; + int TBRank; + Value TBScore; std::vector pv; }; diff --git a/src/syzygy/tbprobe.cpp b/src/syzygy/tbprobe.cpp index cc69b643..fbd5c6dd 100644 --- a/src/syzygy/tbprobe.cpp +++ b/src/syzygy/tbprobe.cpp @@ -34,6 +34,7 @@ #include "../search.h" #include "../thread_win32.h" #include "../types.h" +#include "../uci.h" #include "tbprobe.h" @@ -1437,209 +1438,107 @@ int Tablebases::probe_dtz(Position& pos, ProbeState* result) { return minDTZ == 0xFFFF ? -1 : minDTZ; } -// Check whether there has been at least one repetition of positions -// since the last capture or pawn move. -static int has_repeated(StateInfo *st) -{ - while (1) { - int i = 4, e = std::min(st->rule50, st->pliesFromNull); - - if (e < i) - return 0; - - StateInfo *stp = st->previous->previous; - do { - stp = stp->previous->previous; - - if (stp->key == st->key) - return 1; - - i += 2; - } while (i <= e); - - st = st->previous; - } -} - -// Use the DTZ tables to filter out moves that don't preserve the win or draw. -// If the position is lost, but DTZ is fairly high, only keep moves that -// maximise DTZ. +// Use the DTZ tables to rank root moves. // -// A return value false indicates that not all probes were successful and that -// no moves were filtered out. -bool Tablebases::root_probe(Position& pos, Search::RootMoves& rootMoves, Value& score) -{ - assert(rootMoves.size()); +// A return value false indicates that not all probes were successful. +bool Tablebases::root_probe(Position& pos, Search::RootMoves& rootMoves) { ProbeState result; - int dtz = probe_dtz(pos, &result); - - if (result == FAIL) - return false; - StateInfo st; - // Probe each move - for (size_t i = 0; i < rootMoves.size(); ++i) { - Move move = rootMoves[i].pv[0]; - pos.do_move(move, st); - int v = 0; - - if (pos.checkers() && dtz > 0) { - ExtMove s[MAX_MOVES]; - - if (generate(pos, s) == s) - v = 1; - } - - if (!v) { - if (st.rule50 != 0) { - v = -probe_dtz(pos, &result); - - if (v > 0) - ++v; - else if (v < 0) - --v; - } else { - v = -probe_wdl(pos, &result); - v = dtz_before_zeroing(WDLScore(v)); - } - } - - pos.undo_move(move); - - if (result == FAIL) - return false; - - rootMoves[i].score = (Value)v; - } - - // Obtain 50-move counter for the root position. - // In Stockfish there seems to be no clean way, so we do it like this: - int cnt50 = st.previous ? st.previous->rule50 : 0; - - // Use 50-move counter to determine whether the root position is - // won, lost or drawn. - WDLScore wdl = WDLDraw; - - if (dtz > 0) - wdl = (dtz + cnt50 <= 100) ? WDLWin : WDLCursedWin; - else if (dtz < 0) - wdl = (-dtz + cnt50 <= 100) ? WDLLoss : WDLBlessedLoss; + // Obtain 50-move counter for the root position + int cnt50 = pos.rule50_count(); - // Determine the score to report to the user. - score = WDL_to_value[wdl + 2]; + // Check whether a position was repeated since the last zeroing move. + bool rep = pos.has_repeated(); - // If the position is winning or losing, but too few moves left, adjust the - // score to show how close it is to winning or losing. - // NOTE: int(PawnValueEg) is used as scaling factor in score_to_uci(). - if (wdl == WDLCursedWin && dtz <= 100) - score = (Value)(((200 - dtz - cnt50) * int(PawnValueEg)) / 200); - else if (wdl == WDLBlessedLoss && dtz >= -100) - score = -(Value)(((200 + dtz - cnt50) * int(PawnValueEg)) / 200); + int dtz, bound = Options["Syzygy50MoveRule"] ? 900 : 1; - // Now be a bit smart about filtering out moves. - size_t j = 0; - - if (dtz > 0) { // winning (or 50-move rule draw) - int best = 0xffff; - - for (size_t i = 0; i < rootMoves.size(); ++i) { - int v = rootMoves[i].score; + // Probe and rank each move + for (auto& m : rootMoves) + { + pos.do_move(m.pv[0], st); - if (v > 0 && v < best) - best = v; + // Calculate dtz for the current move counting from the root position + if (pos.rule50_count() == 0) + { + // In case of a zeroing move, dtz is one of -101/-1/0/1/101 + WDLScore wdl = -probe_wdl(pos, &result); + dtz = dtz_before_zeroing(wdl); } - - int max = best; - - // If the current phase has not seen repetitions, then try all moves - // that stay safely within the 50-move budget, if there are any. - if (!has_repeated(st.previous) && best + cnt50 <= 99) - max = 99 - cnt50; - - for (size_t i = 0; i < rootMoves.size(); ++i) { - int v = rootMoves[i].score; - - if (v > 0 && v <= max) - rootMoves[j++] = rootMoves[i]; + else + { + // Otherwise, take dtz for the new position and correct by 1 ply + dtz = -probe_dtz(pos, &result); + dtz = dtz > 0 ? dtz + 1 + : dtz < 0 ? dtz - 1 : dtz; } - } else if (dtz < 0) { // losing (or 50-move rule draw) - int best = 0; - for (size_t i = 0; i < rootMoves.size(); ++i) { - int v = rootMoves[i].score; + // Make sure that a mating move is assigned a dtz value of 1 + if ( pos.checkers() + && dtz == 2 + && MoveList(pos).size() == 0) + dtz = 1; - if (v < best) - best = v; - } + pos.undo_move(m.pv[0]); - // Try all moves, unless we approach or have a 50-move rule draw. - if (-best * 2 + cnt50 < 100) - return true; + if (result == FAIL) + return false; - for (size_t i = 0; i < rootMoves.size(); ++i) { - if (rootMoves[i].score == best) - rootMoves[j++] = rootMoves[i]; - } - } else { // drawing - // Try all moves that preserve the draw. - for (size_t i = 0; i < rootMoves.size(); ++i) { - if (rootMoves[i].score == 0) - rootMoves[j++] = rootMoves[i]; - } + // Better moves are ranked higher. Certain wins are ranked equally. + // Losing moves are ranked equally unless a 50-move draw is in sight. + int r = dtz > 0 ? (dtz + cnt50 <= 99 && !rep ? 1000 : 1000 - (dtz + cnt50)) + : dtz < 0 ? (-dtz * 2 + cnt50 < 100 ? -1000 : -1000 + (-dtz + cnt50)) + : 0; + m.TBRank = r; + + // Determine the score to be displayed for this move. Assign at least + // 1 cp to cursed wins and let it grow to 49 cp as the positions gets + // closer to a real win. + m.TBScore = r >= bound ? VALUE_MATE - MAX_PLY - 1 + : r > 0 ? Value((std::max( 3, r - 800) * int(PawnValueEg)) / 200) + : r == 0 ? VALUE_DRAW + : r > -bound ? Value((std::min(-3, r + 800) * int(PawnValueEg)) / 200) + : -VALUE_MATE + MAX_PLY + 1; } - rootMoves.resize(j, Search::RootMove(MOVE_NONE)); - return true; } -// Use the WDL tables to filter out moves that don't preserve the win or draw. + +// Use the WDL tables to rank root moves. // This is a fallback for the case that some or all DTZ tables are missing. // -// A return value false indicates that not all probes were successful and that -// no moves were filtered out. -bool Tablebases::root_probe_wdl(Position& pos, Search::RootMoves& rootMoves, Value& score) -{ - ProbeState result; +// A return value false indicates that not all probes were successful. +bool Tablebases::root_probe_wdl(Position& pos, Search::RootMoves& rootMoves) { - WDLScore wdl = Tablebases::probe_wdl(pos, &result); + static const int WDL_to_rank[] = { -1000, -899, 0, 899, 1000 }; - if (result == FAIL) - return false; + ProbeState result; + StateInfo st; - score = WDL_to_value[wdl + 2]; + bool rule50 = Options["Syzygy50MoveRule"]; - StateInfo st; + // Probe and rank each move + for (auto& m : rootMoves) + { + pos.do_move(m.pv[0], st); - int best = WDLLoss; + WDLScore wdl = -probe_wdl(pos, &result); - // Probe each move - for (size_t i = 0; i < rootMoves.size(); ++i) { - Move move = rootMoves[i].pv[0]; - pos.do_move(move, st); - WDLScore v = -Tablebases::probe_wdl(pos, &result); - pos.undo_move(move); + pos.undo_move(m.pv[0]); if (result == FAIL) return false; - rootMoves[i].score = (Value)v; + m.TBRank = WDL_to_rank[wdl + 2]; - if (v > best) - best = v; + if (!rule50) + wdl = wdl > WDLDraw ? WDLWin + : wdl < WDLDraw ? WDLLoss : WDLDraw; + m.TBScore = WDL_to_value[wdl + 2]; } - size_t j = 0; - - for (size_t i = 0; i < rootMoves.size(); ++i) { - if (rootMoves[i].score == best) - rootMoves[j++] = rootMoves[i]; - } - - rootMoves.resize(j, Search::RootMove(MOVE_NONE)); - return true; } diff --git a/src/syzygy/tbprobe.h b/src/syzygy/tbprobe.h index 287b6172..572265b5 100644 --- a/src/syzygy/tbprobe.h +++ b/src/syzygy/tbprobe.h @@ -49,9 +49,9 @@ extern int MaxCardinality; void init(const std::string& paths); WDLScore probe_wdl(Position& pos, ProbeState* result); int probe_dtz(Position& pos, ProbeState* result); -bool root_probe(Position& pos, Search::RootMoves& rootMoves, Value& score); -bool root_probe_wdl(Position& pos, Search::RootMoves& rootMoves, Value& score); -void filter_root_moves(Position& pos, Search::RootMoves& rootMoves); +bool root_probe(Position& pos, Search::RootMoves& rootMoves); +bool root_probe_wdl(Position& pos, Search::RootMoves& rootMoves); +void rank_root_moves(Position& pos, Search::RootMoves& rootMoves); inline std::ostream& operator<<(std::ostream& os, const WDLScore v) { diff --git a/src/thread.cpp b/src/thread.cpp index ec62c3ff..948b71c8 100644 --- a/src/thread.cpp +++ b/src/thread.cpp @@ -169,7 +169,7 @@ void ThreadPool::start_thinking(Position& pos, StateListPtr& states, rootMoves.emplace_back(m); if (!rootMoves.empty()) - Tablebases::filter_root_moves(pos, rootMoves); + Tablebases::rank_root_moves(pos, rootMoves); // After ownership transfer 'states' becomes empty, so if we stop the search // and call 'go' again without setting a new position states.get() == NULL. diff --git a/src/thread.h b/src/thread.h index 0d507739..602e1f3b 100644 --- a/src/thread.h +++ b/src/thread.h @@ -60,7 +60,7 @@ public: Pawns::Table pawnsTable; Material::Table materialTable; Endgames endgames; - size_t PVIdx; + size_t PVIdx, PVLast; int selDepth, nmp_ply, nmp_odd; std::atomic nodes, tbHits; -- 2.39.2