From 91a76331ca27b40d63f0031fbd7b9e41ead354d4 Mon Sep 17 00:00:00 2001 From: Tom Truscott Date: Wed, 16 May 2018 22:47:41 +0200 Subject: [PATCH] Use cycle detection to bound search value MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit A position which has a move which draws by repetition, or which could have been reached from an earlier position in the game tree, is considered to be at least a draw for the side to move. Cycle detection algorithm by Marcel van Kervink: https://marcelk.net/2013-04-06/paper/upcoming-rep-v2.pdf ---------------------------- How does the algorithm work in practice? The algorithm is an efficient method to detect if the side to move has a drawing move, without doing any move generation, thus possibly giving a cheap cutoffThe most interesting conditions are both on line 1195: ``` if ( originalKey == (progressKey ^ stp->key) || progressKey == Zobrist::side) ``` This uses the position keys as a sort-of Bloom filter, to avoid the expensive checks which follow. For "upcoming repetition" consider the opening Nf3 Nf6 Ng1. The XOR of this position's key with the starting position gives their difference, which can be used to look up black's repeating move (Ng8). But that look-up is expensive, so line 1195 checks that the white pieces are on their original squares. This is the subtlest part of the algorithm, but the basic idea in the above game is there are 4 positions (starting position and the one after each move). An XOR of the first pair (startpos and after Nf3) gives a key matching Nf3. An XOR of the second pair (after Nf6 and after Ng1) gives a key matching the move Ng1. But since the difference in each pair is the location of the white knight those keys are "identical" (not quite because while there are 4 keys the the side to move changed 3 times, so the keys differ by Zobrist::side). The loop containing line 1195 does this pair-wise XOR-ing. Continuing the example, after line 1195 determines that the white pieces are back where they started we still need to make sure the changes in the black pieces represents a legal move. This is done by looking up the "moveKey" to see if it corresponds to possible move, and that there are no pieces blocking its way. There is the additional complication that, to match the behavior of is_draw(), if the repetition is not inside the search tree then there must be an additional repetition in the game history. Since a position can have more than one upcoming repetition a simple count does not suffice. So there is a search loop ending on line 1215. On the other hand, the "no-progress' is the same thing but offset by 1 ply. I like the concept but think it currently has minimal or negative benefit, and I'd be happy to remove it if that would get the patch accepted. This will not, however, save many lines of code. ----------------------------- STC: LLR: 2.95 (-2.94,2.94) [0.00,5.00] Total: 36430 W: 7446 L: 7150 D: 21834 http://tests.stockfishchess.org/tests/view/5afc123f0ebc591fdf408dfc LTC: LLR: 2.96 (-2.94,2.94) [0.00,5.00] Total: 12998 W: 2045 L: 1876 D: 9077 http://tests.stockfishchess.org/tests/view/5afc2c630ebc591fdf408e0c How could we continue after the patch: • The code in search() that checks for cycles has numerous possible variants. Perhaps the check need could be done in qsearch() too. • The biggest improvement would be to get "no progress" to be of actual benefit, and it would be helpful understand why it (probably) isn't. Perhaps there is an interaction with the transposition table or the (fantastically complex) tree search. Perhaps this would be hard to fix, but there may be a simple oversight. Closes https://github.com/official-stockfish/Stockfish/pull/1575 Bench: 4550412 --- src/position.cpp | 88 ++++++++++++++++++++++++++++++++++++++++++++++++ src/position.h | 1 + src/search.cpp | 11 ++++++ 3 files changed, 100 insertions(+) diff --git a/src/position.cpp b/src/position.cpp index 0be309ee..c07e6964 100644 --- a/src/position.cpp +++ b/src/position.cpp @@ -130,6 +130,19 @@ std::ostream& operator<<(std::ostream& os, const Position& pos) { } +// Marcel van Kervink's cuckoo algorithm for fast detection of "upcoming repetition"/ +// "no progress" situations. Description of the algorithm in the following paper: +// https://marcelk.net/2013-04-06/paper/upcoming-rep-v2.pdf + +// First and second hash functions for indexing the cuckoo tables +inline Key H1(Key h) { return h & 0x1fff; } +inline Key H2(Key h) { return (h >> 16) & 0x1fff; } + +// Cuckoo tables with Zobrist hashes of valid reversible moves, and the moves themselves +Key cuckoo[8192]; +Move cuckooMove[8192]; + + /// Position::init() initializes at startup the various arrays used to compute /// hash keys. @@ -157,6 +170,28 @@ void Position::init() { Zobrist::side = rng.rand(); Zobrist::noPawns = rng.rand(); + + // Prepare the cuckoo tables + int count = 0; + for (Piece pc : Pieces) + for (Square s1 = SQ_A1; s1 <= SQ_H8; ++s1) + for (Square s2 = Square(s1 + 1); s2 <= SQ_H8; ++s2) + if (PseudoAttacks[type_of(pc)][s1] & s2) + { + Move move = make_move(s1, s2); + Key key = Zobrist::psq[pc][s1] ^ Zobrist::psq[pc][s2] ^ Zobrist::side; + unsigned int i = H1(key); + while (true) + { + std::swap(cuckoo[i], key); + std::swap(cuckooMove[i], move); + if (move == 0) // Arrived at empty slot ? + break; + i = (i == H1(key)) ? H2(key) : H1(key); // Push victim to alternative slot + } + count++; + } + assert(count == 3668); } @@ -1134,6 +1169,59 @@ bool Position::has_repeated() const { } +/// Position::has_game_cycle() tests if the position has a move which draws by repetition, +/// or an earlier position has a move that directly reaches the current position. + +bool Position::has_game_cycle(int ply) const { + + unsigned int j; + + int end = std::min(st->rule50, st->pliesFromNull); + + if (end < 3) + return false; + + Key originalKey = st->key; + StateInfo* stp = st->previous; + Key progressKey = stp->key ^ Zobrist::side; + + for (int i = 3; i <= end; i += 2) + { + stp = stp->previous; + progressKey ^= stp->key ^ Zobrist::side; + stp = stp->previous; + + // "originalKey == " detects upcoming repetition, "progressKey == " detects no-progress + if ( originalKey == (progressKey ^ stp->key) + || progressKey == Zobrist::side) + { + Key moveKey = originalKey ^ stp->key; + if ( (j = H1(moveKey), cuckoo[j] == moveKey) + || (j = H2(moveKey), cuckoo[j] == moveKey)) + { + Move m = Move(cuckooMove[j]); + if (!(between_bb(from_sq(m), to_sq(m)) & pieces())) + { + if (ply > i) + return true; + + // For repetitions before or at the root, require one more + StateInfo* next_stp = stp; + for (int k = i + 2; k <= end; k += 2) + { + next_stp = next_stp->previous->previous; + if (next_stp->key == stp->key) + return true; + } + } + } + } + progressKey ^= stp->key; + } + return false; +} + + /// 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 0c8f7972..06000e0f 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_game_cycle(int ply) const; bool has_repeated() const; int rule50_count() const; Score psq_score() const; diff --git a/src/search.cpp b/src/search.cpp index 1a4f654d..025c1141 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -577,6 +577,17 @@ namespace { beta = std::min(mate_in(ss->ply+1), beta); if (alpha >= beta) return alpha; + + // Check if there exists a move which draws by repetition, or an alternative + // earlier move to this position. + if ( pos.rule50_count() >= 3 + && alpha < VALUE_DRAW + && pos.has_game_cycle(ss->ply)) + { + alpha = VALUE_DRAW; + if (alpha >= beta) + return alpha; + } } assert(0 <= ss->ply && ss->ply < MAX_PLY); -- 2.39.2