From: MJZ1977 <37274752+MJZ1977@users.noreply.github.com> Date: Wed, 9 Jan 2019 14:05:28 +0000 (+0100) Subject: Flag critical search tree in hash table X-Git-Url: https://git.sesse.net/?p=stockfish;a=commitdiff_plain;h=70880b8e247c94d0a16a2fb50b41827726e00742 Flag critical search tree in hash table Introducing new concept, saving principal lines into the transposition table to generate a "critical search tree" which we can reuse later for intelligent pruning/extension decisions. For instance in this patch we just reduce reduction for these lines. But a lot of other ideas are possible. To go further : tune some parameters, how to add or remove lines from the critical search tree, how to use these lines in search choices, etc. STC : LLR: 2.94 (-2.94,2.94) [0.50,4.50] Total: 59761 W: 13321 L: 12863 D: 33577 +2.23 ELO http://tests.stockfishchess.org/tests/view/5c34da5d0ebc596a450c53d3 LTC : LLR: 2.96 (-2.94,2.94) [0.00,3.50] Total: 26826 W: 4439 L: 4191 D: 18196 +2.9 ELO http://tests.stockfishchess.org/tests/view/5c35ceb00ebc596a450c65b2 Special thanks to Miguel Lahoz for his help in transposition table in/out. Bench: 3399866 --- diff --git a/src/search.cpp b/src/search.cpp index c8e6c8b6..b7e04fad 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -577,7 +577,7 @@ namespace { Move ttMove, move, excludedMove, bestMove; Depth extension, newDepth; Value bestValue, value, ttValue, eval, maxValue, pureStaticEval; - bool ttHit, inCheck, givesCheck, improving; + bool ttHit, pvHit, inCheck, givesCheck, improving; bool captureOrPromotion, doFullDepthSearch, moveCountPruning, skipQuiets, ttCapture, pvExact; Piece movedPiece; int moveCount, captureCount, quietCount; @@ -643,6 +643,7 @@ namespace { ttValue = ttHit ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE; ttMove = rootNode ? thisThread->rootMoves[thisThread->pvIdx].pv[0] : ttHit ? tte->move() : MOVE_NONE; + pvHit = ttHit ? tte->pv_hit() : false; // At non-PV nodes we check for an early TT cutoff if ( !PvNode @@ -676,6 +677,11 @@ namespace { return ttValue; } + if ( depth > 6 * ONE_PLY + && !excludedMove + && PvNode) + pvHit = true; + // Step 5. Tablebases probe if (!rootNode && TB::Cardinality) { @@ -709,7 +715,7 @@ namespace { if ( b == BOUND_EXACT || (b == BOUND_LOWER ? value >= beta : value <= alpha)) { - tte->save(posKey, value_to_tt(value, ss->ply), b, + tte->save(posKey, value_to_tt(value, ss->ply), pvHit, b, std::min(DEPTH_MAX - ONE_PLY, depth + 6 * ONE_PLY), MOVE_NONE, VALUE_NONE); @@ -760,7 +766,7 @@ namespace { else ss->staticEval = eval = pureStaticEval = -(ss-1)->staticEval + 2 * Eval::Tempo; - tte->save(posKey, VALUE_NONE, BOUND_NONE, DEPTH_NONE, MOVE_NONE, pureStaticEval); + tte->save(posKey, VALUE_NONE, pvHit, BOUND_NONE, DEPTH_NONE, MOVE_NONE, pureStaticEval); } // Step 7. Razoring (~2 Elo) @@ -875,6 +881,7 @@ namespace { tte = TT.probe(posKey, ttHit); ttValue = ttHit ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE; ttMove = ttHit ? tte->move() : MOVE_NONE; + pvHit = ttHit ? tte->pv_hit() : false; } moves_loop: // When in check, search starts from here @@ -1035,6 +1042,10 @@ moves_loop: // When in check, search starts from here { Depth r = reduction(improving, depth, moveCount); + // Decrease reduction if position is or has been on the PV + if (pvHit && !PvNode) + r -= ONE_PLY; + // Decrease reduction if opponent's move count is high (~10 Elo) if ((ss-1)->moveCount > 15) r -= ONE_PLY; @@ -1217,7 +1228,7 @@ moves_loop: // When in check, search starts from here bestValue = std::min(bestValue, maxValue); if (!excludedMove) - tte->save(posKey, value_to_tt(bestValue, ss->ply), + tte->save(posKey, value_to_tt(bestValue, ss->ply), pvHit, bestValue >= beta ? BOUND_LOWER : PvNode && bestMove ? BOUND_EXACT : BOUND_UPPER, depth, bestMove, pureStaticEval); @@ -1247,7 +1258,7 @@ moves_loop: // When in check, search starts from here Move ttMove, move, bestMove; Depth ttDepth; Value bestValue, value, ttValue, futilityValue, futilityBase, oldAlpha; - bool ttHit, inCheck, givesCheck, evasionPrunable; + bool ttHit, pvHit, inCheck, givesCheck, evasionPrunable; int moveCount; if (PvNode) @@ -1281,6 +1292,7 @@ moves_loop: // When in check, search starts from here tte = TT.probe(posKey, ttHit); ttValue = ttHit ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE; ttMove = ttHit ? tte->move() : MOVE_NONE; + pvHit = ttHit ? tte->pv_hit() : false; if ( !PvNode && ttHit @@ -1318,7 +1330,7 @@ moves_loop: // When in check, search starts from here if (bestValue >= beta) { if (!ttHit) - tte->save(posKey, value_to_tt(bestValue, ss->ply), BOUND_LOWER, + tte->save(posKey, value_to_tt(bestValue, ss->ply), pvHit, BOUND_LOWER, DEPTH_NONE, MOVE_NONE, ss->staticEval); return bestValue; @@ -1429,7 +1441,7 @@ moves_loop: // When in check, search starts from here if (inCheck && bestValue == -VALUE_INFINITE) return mated_in(ss->ply); // Plies to mate from the root - tte->save(posKey, value_to_tt(bestValue, ss->ply), + tte->save(posKey, value_to_tt(bestValue, ss->ply), pvHit, bestValue >= beta ? BOUND_LOWER : PvNode && bestValue > oldAlpha ? BOUND_EXACT : BOUND_UPPER, ttDepth, bestMove, ss->staticEval); diff --git a/src/tt.cpp b/src/tt.cpp index 653d081f..d05de916 100644 --- a/src/tt.cpp +++ b/src/tt.cpp @@ -31,7 +31,7 @@ TranspositionTable TT; // Our global transposition table /// TTEntry::save saves a TTEntry -void TTEntry::save(Key k, Value v, Bound b, Depth d, Move m, Value ev) { +void TTEntry::save(Key k, Value v, bool PvNode, Bound b, Depth d, Move m, Value ev) { assert(d / ONE_PLY * ONE_PLY == d); @@ -47,7 +47,7 @@ void TTEntry::save(Key k, Value v, Bound b, Depth d, Move m, Value ev) { key16 = (uint16_t)(k >> 48); value16 = (int16_t)v; eval16 = (int16_t)ev; - genBound8 = (uint8_t)(TT.generation8 | b); + genBound8 = (uint8_t)(TT.generation8 | PvNode << 2 | b); depth8 = (int8_t)(d / ONE_PLY); } } @@ -122,7 +122,7 @@ TTEntry* TranspositionTable::probe(const Key key, bool& found) const { for (int i = 0; i < ClusterSize; ++i) if (!tte[i].key16 || tte[i].key16 == key16) { - tte[i].genBound8 = uint8_t(generation8 | tte[i].bound()); // Refresh + tte[i].genBound8 = uint8_t(generation8 | tte[i].pv_hit() << 2 | tte[i].bound()); // Refresh return found = (bool)tte[i].key16, &tte[i]; } @@ -131,11 +131,11 @@ TTEntry* TranspositionTable::probe(const Key key, bool& found) const { TTEntry* replace = tte; for (int i = 1; i < ClusterSize; ++i) // Due to our packed storage format for generation and its cyclic - // nature we add 259 (256 is the modulus plus 3 to keep the lowest + // nature we add 263 (263 is the modulus plus 7 to keep the lowest // two bound bits from affecting the result) to calculate the entry // age correctly even after generation8 overflows into the next cycle. - if ( replace->depth8 - ((259 + generation8 - replace->genBound8) & 0xFC) * 2 - > tte[i].depth8 - ((259 + generation8 - tte[i].genBound8) & 0xFC) * 2) + if ( replace->depth8 - ((263 + generation8 - replace->genBound8) & 0xF8) + > tte[i].depth8 - ((263 + generation8 - tte[i].genBound8) & 0xF8)) replace = &tte[i]; return found = false, replace; diff --git a/src/tt.h b/src/tt.h index 2cf82f58..8b98dbd5 100644 --- a/src/tt.h +++ b/src/tt.h @@ -30,7 +30,8 @@ /// move 16 bit /// value 16 bit /// eval value 16 bit -/// generation 6 bit +/// generation 5 bit +/// PvNode 1 bit /// bound type 2 bit /// depth 8 bit @@ -40,8 +41,9 @@ struct TTEntry { Value value() const { return (Value)value16; } Value eval() const { return (Value)eval16; } Depth depth() const { return (Depth)(depth8 * int(ONE_PLY)); } + bool pv_hit() const { return (bool)(genBound8 & 0x4); } Bound bound() const { return (Bound)(genBound8 & 0x3); } - void save(Key k, Value v, Bound b, Depth d, Move m, Value ev); + void save(Key k, Value v, bool PvNode, Bound b, Depth d, Move m, Value ev); private: friend class TranspositionTable; @@ -76,7 +78,7 @@ class TranspositionTable { public: ~TranspositionTable() { free(mem); } - void new_search() { generation8 += 4; } // Lower 2 bits are used by Bound + void new_search() { generation8 += 8; } // Lower 3 bits are used by PV flag and Bound TTEntry* probe(const Key key, bool& found) const; int hashfull() const; void resize(size_t mbSize); diff --git a/tests/instrumented.sh b/tests/instrumented.sh index 137d0e4a..eb70466f 100755 --- a/tests/instrumented.sh +++ b/tests/instrumented.sh @@ -45,6 +45,7 @@ race:TTEntry::bound race:TTEntry::save race:TTEntry::value race:TTEntry::eval +race:TTEntry::pv_hit race:TranspositionTable::probe race:TranspositionTable::hashfull