From 3cf6471738dc704ddf553d5f8d2dc9875c2ccbe7 Mon Sep 17 00:00:00 2001 From: Marco Costalba Date: Thu, 27 Dec 2012 12:13:31 +0100 Subject: [PATCH 1/1] Revert evaluation cache And return on using TT as backing store for position evaluations. Tests (even on single thread) show eval cache was a regression. In multi thread result should be even worst because eval cache is a per-thread struct, while TT is shared. After 4957 games at 15"+0.05 (single thread) eval cache vs master 969 - 1093 - 2895 -9 ELO So previous reported result of +18 ELO was probably due to an issue in the testing framework (a bug in cutechess-cli) that has been fixed in the meanwhile. bench: 5386711 --- src/evaluate.cpp | 39 ++++++++++++------------------------- src/evaluate.h | 11 ----------- src/search.cpp | 50 +++++++++++++++++++++++++++++++++++++----------- src/thread.h | 2 -- src/tt.cpp | 6 +++--- src/tt.h | 10 +++++++--- 6 files changed, 61 insertions(+), 57 deletions(-) diff --git a/src/evaluate.cpp b/src/evaluate.cpp index 1f396f75..9756add8 100644 --- a/src/evaluate.cpp +++ b/src/evaluate.cpp @@ -244,7 +244,7 @@ namespace { Score evaluate_pieces_of_color(const Position& pos, EvalInfo& ei, Score& mobility); template - Score evaluate_king(const Position& pos, EvalInfo& ei, int16_t margins[]); + Score evaluate_king(const Position& pos, EvalInfo& ei, Value margins[]); template Score evaluate_threats(const Position& pos, EvalInfo& ei); @@ -364,27 +364,13 @@ Value do_evaluate(const Position& pos, Value& margin) { assert(!pos.checkers()); EvalInfo ei; + Value margins[COLOR_NB]; Score score, mobilityWhite, mobilityBlack; - - Key key = pos.key(); Thread* th = pos.this_thread(); - Eval::Entry* e = th->evalTable[key]; - - // If e->key matches the position's hash key, it means that we have analysed - // this node before, and we can simply return the information we found the last - // time instead of recomputing it. - if (e->key == key) - { - margin = Value(e->margins[pos.side_to_move()]); - return e->value; - } - - // Otherwise we overwrite current content with this node info. - e->key = key; // margins[] store the uncertainty estimation of position's evaluation // that typically is used by the search for pruning decisions. - e->margins[WHITE] = e->margins[BLACK] = VALUE_ZERO; + margins[WHITE] = margins[BLACK] = VALUE_ZERO; // Initialize score by reading the incrementally updated scores included // in the position object (material + piece square tables) and adding @@ -400,8 +386,7 @@ Value do_evaluate(const Position& pos, Value& margin) { if (ei.mi->specialized_eval_exists()) { margin = VALUE_ZERO; - e->value = ei.mi->evaluate(pos); - return e->value; + return ei.mi->evaluate(pos); } // Probe the pawn hash table @@ -420,8 +405,8 @@ Value do_evaluate(const Position& pos, Value& margin) { // Evaluate kings after all other pieces because we need complete attack // information when computing the king safety evaluation. - score += evaluate_king(pos, ei, e->margins) - - evaluate_king(pos, ei, e->margins); + score += evaluate_king(pos, ei, margins) + - evaluate_king(pos, ei, margins); // Evaluate tactical threats, we need full attack information including king score += evaluate_threats(pos, ei) @@ -467,7 +452,7 @@ Value do_evaluate(const Position& pos, Value& margin) { sf = ScaleFactor(50); } - margin = Value(e->margins[pos.side_to_move()]); + margin = margins[pos.side_to_move()]; Value v = interpolate(score, ei.mi->game_phase(), sf); // In case of tracing add all single evaluation contributions for both white and black @@ -484,8 +469,8 @@ Value do_evaluate(const Position& pos, Value& margin) { Score b = make_score(ei.mi->space_weight() * evaluate_space(pos, ei), 0); trace_add(SPACE, apply_weight(w, Weights[Space]), apply_weight(b, Weights[Space])); trace_add(TOTAL, score); - TraceStream << "\nUncertainty margin: White: " << to_cp(Value(e->margins[WHITE])) - << ", Black: " << to_cp(Value(e->margins[BLACK])) + TraceStream << "\nUncertainty margin: White: " << to_cp(margins[WHITE]) + << ", Black: " << to_cp(margins[BLACK]) << "\nScaling: " << std::noshowpos << std::setw(6) << 100.0 * ei.mi->game_phase() / 128.0 << "% MG, " << std::setw(6) << 100.0 * (1.0 - ei.mi->game_phase() / 128.0) << "% * " @@ -493,7 +478,7 @@ Value do_evaluate(const Position& pos, Value& margin) { << "Total evaluation: " << to_cp(v); } - return e->value = pos.side_to_move() == WHITE ? v : -v; + return pos.side_to_move() == WHITE ? v : -v; } @@ -768,7 +753,7 @@ Value do_evaluate(const Position& pos, Value& margin) { // evaluate_king<>() assigns bonuses and penalties to a king of a given color template - Score evaluate_king(const Position& pos, EvalInfo& ei, int16_t margins[]) { + Score evaluate_king(const Position& pos, EvalInfo& ei, Value margins[]) { const Color Them = (Us == WHITE ? BLACK : WHITE); @@ -868,7 +853,7 @@ Value do_evaluate(const Position& pos, Value& margin) { // be very big, and so capturing a single attacking piece can therefore // result in a score change far bigger than the value of the captured piece. score -= KingDangerTable[Us == Search::RootColor][attackUnits]; - margins[Us] += int16_t(mg_value(KingDangerTable[Us == Search::RootColor][attackUnits])); + margins[Us] += mg_value(KingDangerTable[Us == Search::RootColor][attackUnits]); } if (Trace) diff --git a/src/evaluate.h b/src/evaluate.h index accb7d63..a76d10d1 100644 --- a/src/evaluate.h +++ b/src/evaluate.h @@ -20,7 +20,6 @@ #if !defined(EVALUATE_H_INCLUDED) #define EVALUATE_H_INCLUDED -#include "misc.h" #include "types.h" class Position; @@ -31,16 +30,6 @@ extern void init(); extern Value evaluate(const Position& pos, Value& margin); extern std::string trace(const Position& pos); -const int TableSize = 262144; - -struct Entry { - Key key; - Value value; - int16_t margins[2]; -}; - -struct Table : HashTable {}; - } #endif // !defined(EVALUATE_H_INCLUDED) diff --git a/src/search.cpp b/src/search.cpp index 46636787..3ba0dbc9 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -575,17 +575,31 @@ namespace { // Step 5. Evaluate the position statically and update parent's gain statistics if (inCheck) ss->staticEval = ss->evalMargin = eval = VALUE_NONE; - else + + else if (tte) { - eval = ss->staticEval = evaluate(pos, ss->evalMargin); + // Following asserts are valid only in single thread condition because + // TT access is always racy and its contents cannot be trusted. + assert(tte->static_value() != VALUE_NONE || Threads.size() > 1); + assert(ttValue != VALUE_NONE || tte->type() == BOUND_NONE || Threads.size() > 1); + + ss->staticEval = eval = tte->static_value(); + ss->evalMargin = tte->static_value_margin(); + + if (eval == VALUE_NONE || ss->evalMargin == VALUE_NONE) // Due to a race + eval = ss->staticEval = evaluate(pos, ss->evalMargin); // Can ttValue be used as a better position evaluation? - if (tte && ttValue != VALUE_NONE) - { + if (ttValue != VALUE_NONE) if ( ((tte->type() & BOUND_LOWER) && ttValue > eval) || ((tte->type() & BOUND_UPPER) && ttValue < eval)) eval = ttValue; - } + } + else + { + eval = ss->staticEval = evaluate(pos, ss->evalMargin); + TT.store(posKey, VALUE_NONE, BOUND_NONE, DEPTH_NONE, MOVE_NONE, + ss->staticEval, ss->evalMargin); } // Update gain for the parent non-capture move given the static position @@ -1041,7 +1055,8 @@ split_point_start: // At split points actual search starts from here if (bestValue >= beta) // Failed high { - TT.store(posKey, value_to_tt(bestValue, ss->ply), BOUND_LOWER, depth, bestMove); + TT.store(posKey, value_to_tt(bestValue, ss->ply), BOUND_LOWER, depth, + bestMove, ss->staticEval, ss->evalMargin); if (!pos.is_capture_or_promotion(bestMove) && !inCheck) { @@ -1066,7 +1081,7 @@ split_point_start: // At split points actual search starts from here else // Failed low or PV search TT.store(posKey, value_to_tt(bestValue, ss->ply), PvNode && bestMove != MOVE_NONE ? BOUND_EXACT : BOUND_UPPER, - depth, bestMove); + depth, bestMove, ss->staticEval, ss->evalMargin); assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); @@ -1147,6 +1162,16 @@ split_point_start: // At split points actual search starts from here ss->staticEval = bestValue = -(ss-1)->staticEval; ss->evalMargin = VALUE_ZERO; } + else if (tte) + { + assert(tte->static_value() != VALUE_NONE || Threads.size() > 1); + + ss->staticEval = bestValue = tte->static_value(); + ss->evalMargin = tte->static_value_margin(); + + if (ss->staticEval == VALUE_NONE || ss->evalMargin == VALUE_NONE) // Due to a race + ss->staticEval = bestValue = evaluate(pos, ss->evalMargin); + } else ss->staticEval = bestValue = evaluate(pos, ss->evalMargin); @@ -1154,7 +1179,8 @@ split_point_start: // At split points actual search starts from here if (bestValue >= beta) { if (!tte) - TT.store(pos.key(), value_to_tt(bestValue, ss->ply), BOUND_LOWER, DEPTH_NONE, MOVE_NONE); + TT.store(pos.key(), value_to_tt(bestValue, ss->ply), BOUND_LOWER, + DEPTH_NONE, MOVE_NONE, ss->staticEval, ss->evalMargin); return bestValue; } @@ -1263,7 +1289,9 @@ split_point_start: // At split points actual search starts from here } else // Fail high { - TT.store(posKey, value_to_tt(value, ss->ply), BOUND_LOWER, ttDepth, move); + TT.store(posKey, value_to_tt(value, ss->ply), BOUND_LOWER, + ttDepth, move, ss->staticEval, ss->evalMargin); + return value; } } @@ -1277,7 +1305,7 @@ split_point_start: // At split points actual search starts from here TT.store(posKey, value_to_tt(bestValue, ss->ply), PvNode && bestValue > oldAlpha ? BOUND_EXACT : BOUND_UPPER, - ttDepth, bestMove); + ttDepth, bestMove, ss->staticEval, ss->evalMargin); assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); @@ -1574,7 +1602,7 @@ void RootMove::insert_pv_in_tt(Position& pos) { tte = TT.probe(pos.key()); if (!tte || tte->move() != pv[ply]) // Don't overwrite correct entries - TT.store(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, pv[ply]); + TT.store(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, pv[ply], VALUE_NONE, VALUE_NONE); assert(MoveList(pos).contains(pv[ply])); diff --git a/src/thread.h b/src/thread.h index c6dc8316..2d8a675b 100644 --- a/src/thread.h +++ b/src/thread.h @@ -22,7 +22,6 @@ #include -#include "evaluate.h" #include "material.h" #include "movepick.h" #include "pawns.h" @@ -109,7 +108,6 @@ public: void wait_for_stop_or_ponderhit(); SplitPoint splitPoints[MAX_SPLITPOINTS_PER_THREAD]; - Eval::Table evalTable; Material::Table materialTable; Endgames endgames; Pawns::Table pawnsTable; diff --git a/src/tt.cpp b/src/tt.cpp index 40dca0d3..9dbfcb5a 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 t, Depth d, Move m, Value statV, Value kingD) { int c1, c2, c3; TTEntry *tte, *replace; @@ -98,7 +98,7 @@ void TranspositionTable::store(const Key posKey, Value v, Bound t, Depth d, Move if (m == MOVE_NONE) m = tte->move(); - tte->save(posKey32, v, t, d, m, generation); + tte->save(posKey32, v, t, d, m, generation, statV, kingD); return; } @@ -110,7 +110,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, t, d, m, generation, statV, kingD); } diff --git a/src/tt.h b/src/tt.h index 719f178d..3edd5e8a 100644 --- a/src/tt.h +++ b/src/tt.h @@ -44,7 +44,7 @@ class TTEntry { public: - void save(uint32_t k, Value v, Bound b, Depth d, Move m, int g) { + void save(uint32_t k, Value v, Bound b, Depth d, Move m, int g, Value statV, Value statM) { key32 = (uint32_t)k; move16 = (uint16_t)m; @@ -52,6 +52,8 @@ public: generation8 = (uint8_t)g; value16 = (int16_t)v; depth16 = (int16_t)d; + staticValue = (int16_t)statV; + staticMargin = (int16_t)statM; } void set_generation(int g) { generation8 = (uint8_t)g; } @@ -61,12 +63,14 @@ public: Value value() const { return (Value)value16; } Bound type() const { return (Bound)bound; } int generation() const { return (int)generation8; } + Value static_value() const { return (Value)staticValue; } + Value static_value_margin() const { return (Value)staticMargin; } private: uint32_t key32; uint16_t move16; uint8_t bound, generation8; - int16_t value16, depth16; + int16_t value16, depth16, staticValue, staticMargin; }; @@ -96,7 +100,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 type, Depth d, Move m, Value statV, Value kingD); TTEntry* probe(const Key posKey) const; void new_search(); TTEntry* first_entry(const Key posKey) const; -- 2.39.2