50-moves rule improvement for transposition table
authorjoergoster <osterj165@googlemail.com>
Thu, 12 Dec 2019 11:53:47 +0000 (12:53 +0100)
committerStéphane Nicolet <cassio@free.fr>
Thu, 9 Jan 2020 18:48:47 +0000 (19:48 +0100)
commitbae019b53e5c2bfcf0d69b4ebfc52b4f4de762eb
tree0db7dd468712af4a2397df1c115bfe9eab2dcfc3
parent09bef14c76e119103cc1a9404cbde7e249205deb
50-moves rule improvement for transposition table

User "adentong" reported recently of a game where Stockfish blundered a game
in a tournament because during a search there was an hash-table issue for
positions inside the tree very close to the 50-moves draw rule. This is part
of a problem which is commonly referred to as the Graph History Interaction (GHI),
and is difficult to solve in computer chess because storing the 50-moves counter
in the hash-table loses Elo in general.

Links:
Issue 2451    : https://github.com/official-stockfish/Stockfish/issues/2451
About the GHI : https://www.chessprogramming.org/Graph_History_Interaction

This patch tries to address the issue in this particular game and similar
reported games: it prevents that values from the transposition table are
getting used when the 50-move counter is close to reaching 100 (). The idea
is that in such cases values from previous searches, with a much lower 50-move
count, become less and less reliable.

More precisely, the heuristic we use in this patch is that we don't take the
transposition table cutoff  when we have reached a 45-moves limit, but let the
search continue doing its job. There is a possible slowdown involved, but it will
also help to find either a draw when it thought to be losing, or a way to avoid
the draw by 50-move rule. This heuristics probably will not fix all possible cases,
but seems to be working reasonably well in practice while not losing too much Elo.

Passed non-regression tests:
STC:
LLR: 2.95 (-2.94,2.94) [-3.00,1.00]
Total: 274452 W: 59700 L: 60075 D: 154677
http://tests.stockfishchess.org/tests/view/5df546116932658fe9b451bf

LTC:
LLR: 2.95 (-2.94,2.94) [-3.00,1.00]
Total: 95235 W: 15297 L: 15292 D: 64646
http://tests.stockfishchess.org/tests/view/5df69c926932658fe9b4520e

Closes https://github.com/official-stockfish/Stockfish/pull/2453

Bench: 4586187
src/search.cpp