From 881a9dfb0a8fec3b1472791e2d98415e4a9a182a Mon Sep 17 00:00:00 2001 From: Sergei Antonov Date: Mon, 12 Dec 2016 16:04:16 +0100 Subject: [PATCH] Threefold repetition detection Implement a threefold repetition detection. Below are the examples of problems fixed by this change. Loosing move in a drawn position. position fen 8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - - 0 1 moves a1a2 a7a8 a2a1 The old code suggested a loosing move "bestmove a8a7", the new code suggests "bestmove a8b7" leading to a draw. Incorrect evaluation (happened in a real game in TCEC Season 9). position fen 4rbkr/1q3pp1/b3pn2/7p/1pN5/1P1BBP1P/P1R2QP1/3R2K1 w - - 5 31 moves e3d4 h8h6 d4e3 The old code evaluated it as "cp 0", the new code evaluation is around "cp -50" which is adequate. Brings 0.5-1 ELO gain. Passes [-3.00,1.00]. STC: http://tests.stockfishchess.org/tests/view/584ece040ebc5903140c5aea LLR: 2.96 (-2.94,2.94) [-3.00,1.00] Total: 47744 W: 8537 L: 8461 D: 30746 LTC: http://tests.stockfishchess.org/tests/view/584f134d0ebc5903140c5b37 LLR: 2.96 (-2.94,2.94) [-3.00,1.00] Total: 36775 W: 4739 L: 4639 D: 27397 Patch has been rewritten into current form for simplification and logic slightly changed so that return a draw score if the position repeats once earlier but after or at the root, or repeats twice strictly before the root. In its original form, repetition at root was not returned as an immediate draw. After retestimng testing both version with SPRT[-3, 1], both passed succesfully, but this version was chosen becuase more natural. There is an argument about MultiPV in which an extended draw at root may be sensible. See discussion here: https://github.com/official-stockfish/Stockfish/pull/925 For documentation, current version passed both at STC and LTC: STC LLR: 2.96 (-2.94,2.94) [-3.00,1.00] Total: 51562 W: 9314 L: 9245 D: 33003 LTC LLR: 2.96 (-2.94,2.94) [-3.00,1.00] Total: 115663 W: 14904 L: 14906 D: 85853 bench: 5468995 --- src/position.cpp | 21 +++++++++++++-------- src/position.h | 2 +- src/search.cpp | 4 ++-- 3 files changed, 16 insertions(+), 11 deletions(-) diff --git a/src/position.cpp b/src/position.cpp index 1b82b6c0..6a393ebb 100644 --- a/src/position.cpp +++ b/src/position.cpp @@ -1079,25 +1079,30 @@ bool Position::see_ge(Move m, Value v) const { /// Position::is_draw() tests whether the position is drawn by 50-move rule /// or by repetition. It does not detect stalemates. -bool Position::is_draw() const { +bool Position::is_draw(int ply) const { if (st->rule50 > 99 && (!checkers() || MoveList(*this).size())) return true; - int e = std::min(st->rule50, st->pliesFromNull); + int end = std::min(st->rule50, st->pliesFromNull); - if (e < 4) + if (end < 4) return false; StateInfo* stp = st->previous->previous; + int cnt = 0; - do { + for (int i = 4; i <= end; i += 2) + { stp = stp->previous->previous; - if (stp->key == st->key) - return true; // Draw at first repetition - - } while ((e -= 2) >= 4); + // At root position ply is 1, so return a draw score if a position + // repeats once earlier but after or at the root, or repeats twice + // strictly before the root. + if ( stp->key == st->key + && ++cnt + (ply - i > 0) == 2) + return true; + } return false; } diff --git a/src/position.h b/src/position.h index 69bf40b1..1ee247e9 100644 --- a/src/position.h +++ b/src/position.h @@ -150,7 +150,7 @@ public: bool is_chess960() const; Thread* this_thread() const; uint64_t nodes_searched() const; - bool is_draw() const; + bool is_draw(int ply) 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 8089130e..75d388b9 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -597,7 +597,7 @@ namespace { if (!rootNode) { // Step 2. Check for aborted search and immediate draw - if (Signals.stop.load(std::memory_order_relaxed) || pos.is_draw() || ss->ply >= MAX_PLY) + if (Signals.stop.load(std::memory_order_relaxed) || pos.is_draw(ss->ply) || ss->ply >= MAX_PLY) return ss->ply >= MAX_PLY && !inCheck ? evaluate(pos) : DrawValue[pos.side_to_move()]; @@ -1180,7 +1180,7 @@ moves_loop: // When in check search starts from here ss->ply = (ss-1)->ply + 1; // Check for an instant draw or if the maximum ply has been reached - if (pos.is_draw() || ss->ply >= MAX_PLY) + if (pos.is_draw(ss->ply) || ss->ply >= MAX_PLY) return ss->ply >= MAX_PLY && !InCheck ? evaluate(pos) : DrawValue[pos.side_to_move()]; -- 2.39.2