From: Marco Costalba Date: Sun, 9 Dec 2012 10:08:37 +0000 (+0100) Subject: Store distinct upper and lower bound scores X-Git-Url: https://git.sesse.net/?p=stockfish;a=commitdiff_plain;h=feeafb0a50556654e345a09d16529a5eb7715dc0 Store distinct upper and lower bound scores This is more complex than what I'd like but I was unable to split in small chunks. Here we add 2 slots to TTEntry (valueUpper and depthUpper) so that sizeof(TTEntry) returns to the original 16 bytes and we can pack exactly 4 entries in a 64 bytes cache line. Now we save an upper bound score alongside a lower (exact) score. The idea is to increase TT cut-offs rates becuase there is now an higher probability for a node to use TT info. This patch is highly experimental and probably needs further steps as is hinted by an unrealistic bench number: bench: 2022385 --- diff --git a/src/search.cpp b/src/search.cpp index f6c2233b..07405d42 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -482,7 +482,7 @@ namespace { Key posKey; Move ttMove, move, excludedMove, bestMove, threatMove; Depth ext, newDepth; - Value bestValue, value, ttValue; + Value bestValue, value, ttValue, ttValueUpper; Value eval, nullValue, futilityValue; bool inCheck, givesCheck, pvMove, singularExtensionNode; bool captureOrPromotion, dangerous, doFullDepthSearch; @@ -544,31 +544,43 @@ namespace { tte = TT.probe(posKey); ttMove = RootNode ? RootMoves[PVIdx].pv[0] : tte ? tte->move() : MOVE_NONE; ttValue = tte ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE; + ttValueUpper = tte ? value_from_tt(tte->value_upper(), ss->ply) : VALUE_NONE; // At PV nodes we check for exact scores, while at non-PV nodes we check for // a fail high/low. Biggest advantage at probing at PV nodes is to have a // smooth experience in analysis mode. We don't probe at Root nodes otherwise // we should also update RootMoveList to avoid bogus output. - if ( !RootNode - && tte - && tte->depth() >= depth - && ttValue != VALUE_NONE // Only in case of TT access race - && ( PvNode ? tte->type() == BOUND_EXACT - : ttValue >= beta ? (tte->type() & BOUND_LOWER) - : (tte->type() & BOUND_UPPER))) + if (!RootNode && tte) { - TT.refresh(tte); - ss->currentMove = ttMove; // Can be MOVE_NONE + // Fail High + if ( (tte->type() & BOUND_LOWER) + && ttValue >= beta + && tte->depth() >= depth + && ttValue != VALUE_NONE) // Only in case of TT access race + { + // Update killers, we assume ttMove caused a cut-off + if ( ttMove + && !pos.is_capture_or_promotion(ttMove) + && ttMove != ss->killers[0]) + { + ss->killers[1] = ss->killers[0]; + ss->killers[0] = ttMove; + } + TT.refresh(tte); + ss->currentMove = ttMove; // Can be MOVE_NONE + return ttValue; + } - if ( ttValue >= beta - && ttMove - && !pos.is_capture_or_promotion(ttMove) - && ttMove != ss->killers[0]) + // Fail Low + if ( (tte->type() & BOUND_UPPER) + && ttValueUpper < beta + && tte->depth_upper() >= depth + && ttValueUpper != VALUE_NONE) // Only in case of TT access race { - ss->killers[1] = ss->killers[0]; - ss->killers[0] = ttMove; + TT.refresh(tte); + ss->currentMove = ttMove; // Can be MOVE_NONE + return ttValueUpper; } - return ttValue; } // Step 5. Evaluate the position statically and update parent's gain statistics @@ -1089,7 +1101,7 @@ split_point_start: // At split points actual search starts from here const TTEntry* tte; Key posKey; Move ttMove, move, bestMove; - Value bestValue, value, ttValue, futilityValue, futilityBase, oldAlpha; + Value bestValue, value, ttValue, ttValueUpper, futilityValue, futilityBase, oldAlpha; bool givesCheck, enoughMaterial, evasionPrunable, fromNull; Depth ttDepth; @@ -1111,21 +1123,34 @@ split_point_start: // At split points actual search starts from here tte = TT.probe(posKey); ttMove = tte ? tte->move() : MOVE_NONE; ttValue = tte ? value_from_tt(tte->value(),ss->ply) : VALUE_NONE; + ttValueUpper = tte ? value_from_tt(tte->value_upper(),ss->ply) : VALUE_NONE; // Decide whether or not to include checks, this fixes also the type of // TT entry depth that we are going to use. Note that in qsearch we use // only two types of depth in TT: DEPTH_QS_CHECKS or DEPTH_QS_NO_CHECKS. ttDepth = InCheck || depth >= DEPTH_QS_CHECKS ? DEPTH_QS_CHECKS : DEPTH_QS_NO_CHECKS; - if ( tte - && tte->depth() >= ttDepth - && ttValue != VALUE_NONE // Only in case of TT access race - && ( PvNode ? tte->type() == BOUND_EXACT - : ttValue >= beta ? (tte->type() & BOUND_LOWER) - : (tte->type() & BOUND_UPPER))) + if (tte) { - ss->currentMove = ttMove; // Can be MOVE_NONE - return ttValue; + // Fail High + if ( (tte->type() & BOUND_LOWER) + && ttValue >= beta + && tte->depth() >= ttDepth + && ttValue != VALUE_NONE) // Only in case of TT access race + { + ss->currentMove = ttMove; // Can be MOVE_NONE + return ttValue; + } + + // Fail Low + if ( (tte->type() & BOUND_UPPER) + && ttValueUpper < beta + && tte->depth_upper() >= ttDepth + && ttValueUpper != VALUE_NONE) // Only in case of TT access race + { + ss->currentMove = ttMove; // Can be MOVE_NONE + return ttValueUpper; + } } // Evaluate the position statically diff --git a/src/tt.cpp b/src/tt.cpp index 40dca0d3..8a66812a 100644 --- a/src/tt.cpp +++ b/src/tt.cpp @@ -82,7 +82,7 @@ void TranspositionTable::clear() { /// more valuable than a TTEntry t2 if t1 is from the current search and t2 is from /// a previous search, or if the depth of t1 is bigger than the depth of t2. -void TranspositionTable::store(const Key posKey, Value v, Bound t, Depth d, Move m) { +void TranspositionTable::store(const Key posKey, Value v, Bound b, Depth d, Move m) { int c1, c2, c3; TTEntry *tte, *replace; @@ -92,13 +92,16 @@ void TranspositionTable::store(const Key posKey, Value v, Bound t, Depth d, Move for (int i = 0; i < ClusterSize; i++, tte++) { - if (!tte->key() || tte->key() == posKey32) // Empty or overwrite old + if (!tte->key()) + tte->save(posKey32, v, b, d, m, generation); + + if (tte->key() == posKey32) { // Preserve any existing ttMove if (m == MOVE_NONE) m = tte->move(); - tte->save(posKey32, v, t, d, m, generation); + tte->update(v, b, d, m, generation); return; } @@ -110,7 +113,7 @@ void TranspositionTable::store(const Key posKey, Value v, Bound t, Depth d, Move if (c1 + c2 + c3 > 0) replace = tte; } - replace->save(posKey32, v, t, d, m, generation); + replace->save(posKey32, v, b, d, m, generation); } diff --git a/src/tt.h b/src/tt.h index 719f178d..6c7caf75 100644 --- a/src/tt.h +++ b/src/tt.h @@ -46,19 +46,43 @@ class TTEntry { public: void save(uint32_t k, Value v, Bound b, Depth d, Move m, int g) { - key32 = (uint32_t)k; - move16 = (uint16_t)m; - bound = (uint8_t)b; - generation8 = (uint8_t)g; - value16 = (int16_t)v; - depth16 = (int16_t)d; + key32 = (uint32_t)k; + move16 = (uint16_t)m; + bound = (uint8_t)b; + generation8 = (uint8_t)g; + valueUpper = (int16_t)(b & BOUND_UPPER ? v : VALUE_NONE); + depthUpper = (int16_t)(b & BOUND_UPPER ? d : DEPTH_NONE); + valueLower = (int16_t)(b & BOUND_LOWER ? v : VALUE_NONE); + depthLower = (int16_t)(b & BOUND_LOWER ? d : DEPTH_NONE); } + + void update(Value v, Bound b, Depth d, Move m, int g) { + + move16 = (uint16_t)m; + bound |= (uint8_t)b; + generation8 = (uint8_t)g; + + if (b & BOUND_UPPER) + { + valueUpper = (int16_t)v; + depthUpper = (int16_t)d; + } + + if (b & BOUND_LOWER) + { + valueLower = (int16_t)v; + depthLower = (int16_t)d; + } + } + void set_generation(int g) { generation8 = (uint8_t)g; } uint32_t key() const { return key32; } - Depth depth() const { return (Depth)depth16; } + Depth depth() const { return (Depth)depthLower; } + Depth depth_upper() const { return (Depth)depthUpper; } Move move() const { return (Move)move16; } - Value value() const { return (Value)value16; } + Value value() const { return (Value)valueLower; } + Value value_upper() const { return (Value)valueUpper; } Bound type() const { return (Bound)bound; } int generation() const { return (int)generation8; } @@ -66,7 +90,7 @@ private: uint32_t key32; uint16_t move16; uint8_t bound, generation8; - int16_t value16, depth16; + int16_t valueLower, depthLower, valueUpper, depthUpper; }; @@ -96,7 +120,7 @@ public: ~TranspositionTable(); void set_size(size_t mbSize); void clear(); - void store(const Key posKey, Value v, Bound type, Depth d, Move m); + void store(const Key posKey, Value v, Bound b, Depth d, Move m); TTEntry* probe(const Key posKey) const; void new_search(); TTEntry* first_entry(const Key posKey) const; diff --git a/src/types.h b/src/types.h index 9b36fd89..2219b40b 100644 --- a/src/types.h +++ b/src/types.h @@ -163,7 +163,7 @@ enum Bound { BOUND_NONE = 0, BOUND_UPPER = 1, BOUND_LOWER = 2, - BOUND_EXACT = BOUND_UPPER | BOUND_LOWER + BOUND_EXACT = BOUND_UPPER | BOUND_LOWER | 4 }; enum Value {