Dev Builds » 20180516-2051

Use this dev build

NCM plays each Stockfish dev build 20,000 times against Stockfish 14. This yields an approximate Elo difference and establishes confidence in the strength of the dev builds.

Summary

Host Duration Avg Base NPS Games WLD Standard Elo Ptnml(0-2) Gamepair Elo

Test Detail

ID Host Base NPS Games WLD Standard Elo Ptnml(0-2) Gamepair Elo CLI PGN

Commit

Commit ID 91a76331ca27b40d63f0031fbd7b9e41ead354d4
Author Tom Truscott
Date 2018-05-16 20:51:43 UTC
Use cycle detection to bound search value 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
Copyright 2011–2024 Next Chess Move LLC