From: Marco Costalba Date: Mon, 10 Dec 2012 08:22:13 +0000 (+0100) Subject: Merge branch 'eval_cache' X-Git-Url: https://git.sesse.net/?p=stockfish;a=commitdiff_plain;h=9edc7d6958fd616daecb0ab9ae2aa92042b3d34a;hp=22c557ca7ce957cfb164c56dd149f22e2f11c7f9 Merge branch 'eval_cache' Unusually good result. Defenitly needs further verifications. After 2160 games at 15"+0.05 Mod vs Orig 486 - 367 - 1307 ELO +19 bench: 6261882 --- diff --git a/src/search.cpp b/src/search.cpp index f6c2233b..98f3e3fd 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 <= alpha + && 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 <= alpha + && 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..c41f231e 100644 --- a/src/tt.h +++ b/src/tt.h @@ -46,19 +46,61 @@ 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; + generation8 = (uint8_t)g; + + if (bound == BOUND_EXACT) + bound = BOUND_UPPER | BOUND_LOWER; // Drop 'EXACT' flag + + if (b & BOUND_UPPER) + { + valueUpper = (int16_t)v; + depthUpper = (int16_t)d; + + if ((bound & BOUND_LOWER) && v < valueLower) + { + bound ^= BOUND_LOWER; + valueLower = VALUE_NONE; + depthLower = DEPTH_NONE; + } + } + + if (b & BOUND_LOWER) + { + valueLower = (int16_t)v; + depthLower = (int16_t)d; + + if ((bound & BOUND_UPPER) && v > valueUpper) + { + bound ^= BOUND_UPPER; + valueUpper = VALUE_NONE; + depthUpper = DEPTH_NONE; + } + } + + bound |= (uint8_t)b; + } + 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 +108,7 @@ private: uint32_t key32; uint16_t move16; uint8_t bound, generation8; - int16_t value16, depth16; + int16_t valueLower, depthLower, valueUpper, depthUpper; }; @@ -96,7 +138,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 99567bd7..785d9898 100644 --- a/src/types.h +++ b/src/types.h @@ -164,7 +164,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 {