From: Marco Costalba Date: Tue, 4 Dec 2012 06:57:46 +0000 (+0100) Subject: Merge branch 'eval_cache' X-Git-Url: https://git.sesse.net/?p=stockfish;a=commitdiff_plain;h=6fa83f51889248b16f539db4ce0fe5b23f2a85d6;hp=ce248e7920912143e2930a31b0951515e6f63442 Merge branch 'eval_cache' Use an eval cache instead of TT to store node position evaluations. It is already an improvment and, because it frees two TT entry slots, paves the way to extend TT to store both upper and lower bounds. After 4855 games, single thread, 15"+0.05 Mod vs Orig 1165 -920 - 2770 ELO +18 bench: 5149248 --- diff --git a/src/evaluate.cpp b/src/evaluate.cpp index 40c98a98..f27c04ec 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, Value margins[]); + Score evaluate_king(const Position& pos, EvalInfo& ei, int16_t margins[]); template Score evaluate_threats(const Position& pos, EvalInfo& ei); @@ -364,12 +364,26 @@ Value do_evaluate(const Position& pos, Value& margin) { assert(!pos.in_check()); EvalInfo ei; - Value margins[COLOR_NB]; Score score, mobilityWhite, mobilityBlack; + Key key = pos.key(); + Eval::Entry* e = pos.this_thread()->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. - margins[WHITE] = margins[BLACK] = VALUE_ZERO; + e->margins[WHITE] = e->margins[BLACK] = VALUE_ZERO; // Initialize score by reading the incrementally updated scores included // in the position object (material + piece square tables) and adding @@ -385,7 +399,8 @@ Value do_evaluate(const Position& pos, Value& margin) { if (ei.mi->specialized_eval_exists()) { margin = VALUE_ZERO; - return ei.mi->evaluate(pos); + e->value = ei.mi->evaluate(pos); + return e->value; } // Probe the pawn hash table @@ -404,8 +419,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, margins) - - evaluate_king(pos, ei, margins); + score += evaluate_king(pos, ei, e->margins) + - evaluate_king(pos, ei, e->margins); // Evaluate tactical threats, we need full attack information including king score += evaluate_threats(pos, ei) @@ -451,7 +466,7 @@ Value do_evaluate(const Position& pos, Value& margin) { sf = ScaleFactor(50); } - margin = margins[pos.side_to_move()]; + margin = Value(e->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 @@ -468,8 +483,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(margins[WHITE]) - << ", Black: " << to_cp(margins[BLACK]) + TraceStream << "\nUncertainty margin: White: " << to_cp(Value(e->margins[WHITE])) + << ", Black: " << to_cp(Value(e->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) << "% * " @@ -477,7 +492,7 @@ Value do_evaluate(const Position& pos, Value& margin) { << "Total evaluation: " << to_cp(v); } - return pos.side_to_move() == WHITE ? v : -v; + return e->value = pos.side_to_move() == WHITE ? v : -v; } @@ -752,7 +767,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, Value margins[]) { + Score evaluate_king(const Position& pos, EvalInfo& ei, int16_t margins[]) { const Color Them = (Us == WHITE ? BLACK : WHITE); @@ -852,7 +867,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] += mg_value(KingDangerTable[Us == Search::RootColor][attackUnits]); + margins[Us] += int16_t(mg_value(KingDangerTable[Us == Search::RootColor][attackUnits])); } if (Trace) diff --git a/src/evaluate.h b/src/evaluate.h index a76d10d1..accb7d63 100644 --- a/src/evaluate.h +++ b/src/evaluate.h @@ -20,6 +20,7 @@ #if !defined(EVALUATE_H_INCLUDED) #define EVALUATE_H_INCLUDED +#include "misc.h" #include "types.h" class Position; @@ -30,6 +31,16 @@ 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 da20f15e..f6c2233b 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -574,31 +574,17 @@ namespace { // Step 5. Evaluate the position statically and update parent's gain statistics if (inCheck) ss->staticEval = ss->evalMargin = eval = VALUE_NONE; - - else if (tte) + else { - // 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); + eval = ss->staticEval = evaluate(pos, ss->evalMargin); // Can ttValue be used as a better position evaluation? - if (ttValue != VALUE_NONE) + if (tte && 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 @@ -1051,8 +1037,7 @@ 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, ss->staticEval, ss->evalMargin); + TT.store(posKey, value_to_tt(bestValue, ss->ply), BOUND_LOWER, depth, bestMove); if (!pos.is_capture_or_promotion(bestMove) && !inCheck) { @@ -1077,7 +1062,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, ss->staticEval, ss->evalMargin); + depth, bestMove); assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); @@ -1154,19 +1139,10 @@ split_point_start: // At split points actual search starts from here { if (fromNull) { + // Approximated score. Real one is slightly higher due to tempo 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); @@ -1174,8 +1150,7 @@ 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, ss->staticEval, ss->evalMargin); + TT.store(pos.key(), value_to_tt(bestValue, ss->ply), BOUND_LOWER, DEPTH_NONE, MOVE_NONE); return bestValue; } @@ -1204,8 +1179,8 @@ split_point_start: // At split points actual search starts from here // Futility pruning if ( !PvNode && !InCheck - && !givesCheck && !fromNull + && !givesCheck && move != ttMove && enoughMaterial && type_of(move) != PROMOTION @@ -1284,9 +1259,7 @@ 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, ss->staticEval, ss->evalMargin); - + TT.store(posKey, value_to_tt(value, ss->ply), BOUND_LOWER, ttDepth, move); return value; } } @@ -1300,7 +1273,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, ss->staticEval, ss->evalMargin); + ttDepth, bestMove); assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); @@ -1591,20 +1564,12 @@ void RootMove::insert_pv_in_tt(Position& pos) { StateInfo state[MAX_PLY_PLUS_2], *st = state; TTEntry* tte; int ply = 0; - Value v, m; do { tte = TT.probe(pos.key()); if (!tte || tte->move() != pv[ply]) // Don't overwrite correct entries - { - if (pos.in_check()) - v = m = VALUE_NONE; - else - v = evaluate(pos, m); - - TT.store(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, pv[ply], v, m); - } + TT.store(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, pv[ply]); assert(pos.move_is_legal(pv[ply])); pos.do_move(pv[ply++], *st++); diff --git a/src/thread.h b/src/thread.h index 4b0a5026..6c3c18af 100644 --- a/src/thread.h +++ b/src/thread.h @@ -22,6 +22,7 @@ #include +#include "evaluate.h" #include "material.h" #include "movepick.h" #include "pawns.h" @@ -108,6 +109,7 @@ public: void wait_for_stop_or_ponderhit(); SplitPoint splitPoints[MAX_SPLITPOINTS_PER_THREAD]; + Eval::Table evalTable; MaterialTable materialTable; PawnTable pawnTable; size_t idx; diff --git a/src/tt.cpp b/src/tt.cpp index 9dbfcb5a..40dca0d3 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, Value statV, Value kingD) { +void TranspositionTable::store(const Key posKey, Value v, Bound t, Depth d, Move m) { 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, statV, kingD); + tte->save(posKey32, v, t, d, m, generation); 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, statV, kingD); + replace->save(posKey32, v, t, d, m, generation); } diff --git a/src/tt.h b/src/tt.h index 3edd5e8a..719f178d 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, Value statV, Value statM) { + void save(uint32_t k, Value v, Bound b, Depth d, Move m, int g) { key32 = (uint32_t)k; move16 = (uint16_t)m; @@ -52,8 +52,6 @@ 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; } @@ -63,14 +61,12 @@ 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, staticValue, staticMargin; + int16_t value16, depth16; }; @@ -100,7 +96,7 @@ public: ~TranspositionTable(); void set_size(size_t mbSize); void clear(); - void store(const Key posKey, Value v, Bound type, Depth d, Move m, Value statV, Value kingD); + void store(const Key posKey, Value v, Bound type, Depth d, Move m); TTEntry* probe(const Key posKey) const; void new_search(); TTEntry* first_entry(const Key posKey) const;