From f7b3f0e8426bbf7414d139ed9d1cfa7a98d7314d Mon Sep 17 00:00:00 2001 From: Sami Kiminki Date: Fri, 21 Aug 2020 12:12:39 +0300 Subject: [PATCH] Allow TT entries with key16==0 to be fetched Fix the issue where a TT entry with key16==0 would always be reported as a miss. Instead, we'll use depth8 to detect whether the TT entry is occupied. In order to do that, we'll change DEPTH_OFFSET to -7 (depth8==0) to distinguish between an unoccupied entry and the otherwise lowest possible depth, i.e., DEPTH_NONE (depth8==1). To prevent a performance regression, we'll reorder the TT entry fields by the access order of TranspositionTable::probe(). Memory in general works fastest when accessed in sequential order. We'll also match the store order in TTEntry::save() with the entry field order, and re-order the 'if-or' expressions in TTEntry::save() from the cheapest to the most expensive. Finally, as we now have a proper TT entry occupancy test, we'll fix a minor corner case with hashfull reporting. To reproduce: - Use a big hash - Either: a. Start 31 very quick searches (this wraparounds generation to 0); or b. Force generation of the first search to 0. - go depth infinite Before the fix, hashfull would incorrectly report nearly full hash immediately after the search start, since TranspositionTable::hashfull() used to consider only the entry generation and not whether the entry was actually occupied. STC: LLR: 2.95 (-2.94,2.94) {-0.25,1.25} Total: 36848 W: 4091 L: 3898 D: 28859 Ptnml(0-2): 158, 2996, 11972, 3091, 207 https://tests.stockfishchess.org/tests/view/5f3f98d5dc02a01a0c2881f7 LTC: LLR: 2.95 (-2.94,2.94) {0.25,1.25} Total: 32280 W: 1828 L: 1653 D: 28799 Ptnml(0-2): 34, 1428, 13051, 1583, 44 https://tests.stockfishchess.org/tests/view/5f3fe77a87a5c3c63d8f5332 closes https://github.com/official-stockfish/Stockfish/pull/3048 Bench: 3760677 --- src/tt.cpp | 21 +++++++++++---------- src/tt.h | 12 ++++++------ src/types.h | 3 ++- 3 files changed, 19 insertions(+), 17 deletions(-) diff --git a/src/tt.cpp b/src/tt.cpp index d494c27d..60a3a5f1 100644 --- a/src/tt.cpp +++ b/src/tt.cpp @@ -37,18 +37,19 @@ void TTEntry::save(Key k, Value v, bool pv, Bound b, Depth d, Move m, Value ev) if (m || (uint16_t)k != key16) move16 = (uint16_t)m; - // Overwrite less valuable entries - if ((uint16_t)k != key16 - || d - DEPTH_OFFSET > depth8 - 4 - || b == BOUND_EXACT) + // Overwrite less valuable entries (cheapest checks first) + if (b == BOUND_EXACT + || (uint16_t)k != key16 + || d - DEPTH_OFFSET > depth8 - 4) { - assert(d >= DEPTH_OFFSET); + assert(d > DEPTH_OFFSET); + assert(d < 256 + DEPTH_OFFSET); key16 = (uint16_t)k; + depth8 = (uint8_t)(d - DEPTH_OFFSET); + genBound8 = (uint8_t)(TT.generation8 | uint8_t(pv) << 2 | b); value16 = (int16_t)v; eval16 = (int16_t)ev; - genBound8 = (uint8_t)(TT.generation8 | uint8_t(pv) << 2 | b); - depth8 = (uint8_t)(d - DEPTH_OFFSET); } } @@ -119,11 +120,11 @@ TTEntry* TranspositionTable::probe(const Key key, bool& found) const { const uint16_t key16 = (uint16_t)key; // Use the low 16 bits as key inside the cluster for (int i = 0; i < ClusterSize; ++i) - if (!tte[i].key16 || tte[i].key16 == key16) + if (tte[i].key16 == key16 || !tte[i].depth8) { tte[i].genBound8 = uint8_t(generation8 | (tte[i].genBound8 & 0x7)); // Refresh - return found = (bool)tte[i].key16, &tte[i]; + return found = (bool)tte[i].depth8, &tte[i]; } // Find an entry to be replaced according to the replacement strategy @@ -149,7 +150,7 @@ int TranspositionTable::hashfull() const { int cnt = 0; for (int i = 0; i < 1000; ++i) for (int j = 0; j < ClusterSize; ++j) - cnt += (table[i].entry[j].genBound8 & 0xF8) == generation8; + cnt += table[i].entry[j].depth8 && (table[i].entry[j].genBound8 & 0xF8) == generation8; return cnt / ClusterSize; } diff --git a/src/tt.h b/src/tt.h index c177ca52..fdfd6769 100644 --- a/src/tt.h +++ b/src/tt.h @@ -25,13 +25,13 @@ /// TTEntry struct is the 10 bytes transposition table entry, defined as below: /// /// key 16 bit -/// move 16 bit -/// value 16 bit -/// eval value 16 bit +/// depth 8 bit /// generation 5 bit /// pv node 1 bit /// bound type 2 bit -/// depth 8 bit +/// move 16 bit +/// value 16 bit +/// eval value 16 bit struct TTEntry { @@ -47,11 +47,11 @@ private: friend class TranspositionTable; uint16_t key16; + uint8_t depth8; + uint8_t genBound8; uint16_t move16; int16_t value16; int16_t eval16; - uint8_t genBound8; - uint8_t depth8; }; diff --git a/src/types.h b/src/types.h index 73da41e2..1cd711b6 100644 --- a/src/types.h +++ b/src/types.h @@ -232,7 +232,8 @@ enum : int { DEPTH_QS_RECAPTURES = -5, DEPTH_NONE = -6, - DEPTH_OFFSET = DEPTH_NONE + + DEPTH_OFFSET = -7 // value used only for TT entry occupancy check }; enum Square : int { -- 2.39.2