From ecd07e51d0f03ccd3e41e5634518b299989254dd Mon Sep 17 00:00:00 2001 From: Lucas Braesch Date: Wed, 30 Oct 2013 11:22:42 +0800 Subject: [PATCH 1/1] Retire eval margin and gains 1/ eval margin and gains removed: - gains removed by Value(128): search() and qsearch() now behave consistently! 2/ futility_margin() - testing showed that there is no added value in this weird (log(depth), movecount) formula, and a much simpler linear formula is just as good. In fact, it is most likely better, as it is not yet optimally tuned. - the new simplified formula also means we get rid of FutilityMargins[], its initialization code, and more importantly ss->futilityMoveCount, and the hacky code that updates it throughout the search(). - the current formula gives negative futility margins, and there is a hidden interaction between the move coutn pruning formula and the futility margin one: what happens is that MCP is supposed to be triggered before we use the non-sensical negative futility margins. 3/ unify pre & post futility pruning - pre futility pruning (what SF calls value based pruning) used depth < 7 plies, while post futility pruning (what SF calls static null move pruning) used depth < 4 plies. - also the condition depth < 7 in pre futility pruning was not obvious, and it seemd to be depth < 16 (futility_margin() returns an infinite value when depth >= 7). Tested with fixed number of games both at short TC: ELO: 0.82 +-2.1 (95%) LOS: 77.3% Total: 40000 W: 7939 L: 7845 D: 24216 And long TC ELO: 0.59 +-2.0 (95%) LOS: 71.9% Total: 40000 W: 6876 L: 6808 D: 26316 bench: 10206576 --- src/evaluate.cpp | 38 ++++++--------------- src/evaluate.h | 2 +- src/movepick.h | 17 ++++----- src/search.cpp | 89 +++++++++++++----------------------------------- src/search.h | 1 - src/tt.cpp | 4 +-- src/tt.h | 8 ++--- 7 files changed, 47 insertions(+), 112 deletions(-) diff --git a/src/evaluate.cpp b/src/evaluate.cpp index 1ff2dea7..5b1f4f40 100644 --- a/src/evaluate.cpp +++ b/src/evaluate.cpp @@ -227,7 +227,7 @@ namespace { // Function prototypes template - Value do_evaluate(const Position& pos, Value& margin); + Value do_evaluate(const Position& pos); template void init_eval_info(const Position& pos, EvalInfo& ei); @@ -236,7 +236,7 @@ namespace { Score evaluate_pieces_of_color(const Position& pos, EvalInfo& ei, Score* mobility); template - Score evaluate_king(const Position& pos, const EvalInfo& ei, Value margins[]); + Score evaluate_king(const Position& pos, const EvalInfo& ei); template Score evaluate_threats(const Position& pos, const EvalInfo& ei); @@ -262,8 +262,8 @@ namespace Eval { /// values, an endgame score and a middle game score, and interpolates /// between them based on the remaining material. - Value evaluate(const Position& pos, Value& margin) { - return do_evaluate(pos, margin); + Value evaluate(const Position& pos) { + return do_evaluate(pos); } @@ -305,19 +305,14 @@ namespace Eval { namespace { template -Value do_evaluate(const Position& pos, Value& margin) { +Value do_evaluate(const Position& pos) { assert(!pos.checkers()); EvalInfo ei; - Value margins[COLOR_NB]; Score score, mobility[2] = { SCORE_ZERO, SCORE_ZERO }; Thread* th = pos.this_thread(); - // 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; - // Initialize score by reading the incrementally updated scores included // in the position object (material + piece square tables) and adding // Tempo bonus. Score is computed from the point of view of white. @@ -330,10 +325,7 @@ Value do_evaluate(const Position& pos, Value& margin) { // If we have a specialized evaluation function for the current material // configuration, call it and return. if (ei.mi->specialized_eval_exists()) - { - margin = VALUE_ZERO; return ei.mi->evaluate(pos); - } // Probe the pawn hash table ei.pi = Pawns::probe(pos, th->pawnsTable); @@ -351,8 +343,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) + - evaluate_king(pos, ei); // Evaluate tactical threats, we need full attack information including king score += evaluate_threats(pos, ei) @@ -399,7 +391,6 @@ Value do_evaluate(const Position& pos, Value& margin) { sf = ScaleFactor(50); } - 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 @@ -412,9 +403,7 @@ Value do_evaluate(const Position& pos, Value& margin) { Score b = ei.mi->space_weight() * evaluate_space(pos, ei); Tracing::add(SPACE, apply_weight(w, Weights[Space]), apply_weight(b, Weights[Space])); Tracing::add(TOTAL, score); - Tracing::stream << "\nUncertainty margin: White: " << to_cp(margins[WHITE]) - << ", Black: " << to_cp(margins[BLACK]) - << "\nScaling: " << std::noshowpos + Tracing::stream << "\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) << "% * " << std::setw(6) << (100.0 * sf) / SCALE_FACTOR_NORMAL << "% EG.\n" @@ -633,7 +622,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, const EvalInfo& ei, Value margins[]) { + Score evaluate_king(const Position& pos, const EvalInfo& ei) { const Color Them = (Us == WHITE ? BLACK : WHITE); @@ -728,12 +717,8 @@ Value do_evaluate(const Position& pos, Value& margin) { attackUnits = std::min(99, std::max(0, attackUnits)); // Finally, extract the king danger score from the KingDanger[] - // array and subtract the score from evaluation. Set also margins[] - // value that will be used for pruning because this value can sometimes - // 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. + // array and subtract the score from evaluation. score -= KingDanger[Us == Search::RootColor][attackUnits]; - margins[Us] += mg_value(KingDanger[Us == Search::RootColor][attackUnits]); } if (Trace) @@ -1017,8 +1002,7 @@ Value do_evaluate(const Position& pos, Value& margin) { stream << std::showpoint << std::showpos << std::fixed << std::setprecision(2); std::memset(scores, 0, 2 * (TOTAL + 1) * sizeof(Score)); - Value margin; - do_evaluate(pos, margin); + do_evaluate(pos); std::string totals = stream.str(); stream.str(""); diff --git a/src/evaluate.h b/src/evaluate.h index 2234a4a0..ae9b6e79 100644 --- a/src/evaluate.h +++ b/src/evaluate.h @@ -27,7 +27,7 @@ class Position; namespace Eval { extern void init(); -extern Value evaluate(const Position& pos, Value& margin); +extern Value evaluate(const Position& pos); extern std::string trace(const Position& pos); } diff --git a/src/movepick.h b/src/movepick.h index c444615f..93061ee6 100644 --- a/src/movepick.h +++ b/src/movepick.h @@ -30,14 +30,13 @@ /// The Stats struct stores moves statistics. According to the template parameter -/// the class can store History, Gains and Countermoves. History records how often +/// the class can store History and Countermoves. History records how often /// different moves have been successful or unsuccessful during the current search -/// and is used for reduction and move ordering decisions. Gains records the move's -/// best evaluation gain from one ply to the next and is used for pruning decisions. +/// and is used for reduction and move ordering decisions. /// Countermoves store the move that refute a previous one. Entries are stored /// according only to moving piece and destination square, hence two moves with /// different origin but same destination and piece will be considered identical. -template +template struct Stats { static const Value Max = Value(2000); @@ -56,10 +55,7 @@ struct Stats { void update(Piece p, Square to, Value v) { - if (Gain) - table[p][to] = std::max(v, table[p][to] - 1); - - else if (abs(table[p][to] + v) < Max) + if (abs(table[p][to] + v) < Max) table[p][to] += v; } @@ -67,9 +63,8 @@ private: T table[PIECE_NB][SQUARE_NB]; }; -typedef Stats< true, Value> GainsStats; -typedef Stats HistoryStats; -typedef Stats > CountermovesStats; +typedef Stats HistoryStats; +typedef Stats > CountermovesStats; /// MovePicker class is used to pick one pseudo legal move at a time from the diff --git a/src/search.cpp b/src/search.cpp index c0a98236..21756824 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -63,13 +63,12 @@ namespace { inline Value razor_margin(Depth d) { return Value(512 + 16 * int(d)); } // Futility lookup tables (initialized at startup) and their access functions - Value FutilityMargins[16][64]; // [depth][moveNumber] + Value FutilityMargins[14][64]; // [depth][moveNumber] int FutilityMoveCounts[2][32]; // [improving][depth] inline Value futility_margin(Depth d, int mn) { - - return d < 7 * ONE_PLY ? FutilityMargins[std::max(int(d), 1)][std::min(mn, 63)] - : 2 * VALUE_INFINITE; + assert(DEPTH_ZERO <= d && d < 7 * ONE_PLY); + return FutilityMargins[d][std::min(mn, 63)]; } // Reduction lookup tables (initialized at startup) and their access function @@ -85,7 +84,6 @@ namespace { double BestMoveChanges; Value DrawValue[COLOR_NB]; HistoryStats History; - GainsStats Gains; CountermovesStats Countermoves; template @@ -147,8 +145,8 @@ void Search::init() { } // Init futility margins array - for (d = 1; d < 16; ++d) for (mc = 0; mc < 64; ++mc) - FutilityMargins[d][mc] = Value(112 * int(2.9 * log(double(d))) - 8 * mc + 45); + for (d = 0; d < 14; ++d) for (mc = 0; mc < 64; ++mc) + FutilityMargins[d][mc] = Value(112 * int(2.9 * log(d >= 1 ? double(d) : 1.0)) - 8 * mc + 45); // Init futility move count array for (d = 0; d < 32; ++d) @@ -301,7 +299,6 @@ namespace { Value bestValue, alpha, beta, delta; std::memset(ss-2, 0, 5 * sizeof(Stack)); - (ss-1)->currentMove = MOVE_NULL; // Hack to skip update gains depth = 0; BestMoveChanges = 0; @@ -310,7 +307,6 @@ namespace { TT.new_search(); History.clear(); - Gains.clear(); Countermoves.clear(); PVSize = Options["MultiPV"]; @@ -499,7 +495,7 @@ namespace { Move ttMove, move, excludedMove, bestMove, threatMove; Depth ext, newDepth; Value bestValue, value, ttValue; - Value eval, nullValue, futilityValue; + Value eval, nullValue; bool inCheck, givesCheck, pvMove, singularExtensionNode, improving; bool captureOrPromotion, dangerous, doFullDepthSearch; int moveCount, quietCount; @@ -591,16 +587,15 @@ namespace { // Step 5. Evaluate the position statically and update parent's gain statistics if (inCheck) { - ss->staticEval = ss->evalMargin = eval = VALUE_NONE; + ss->staticEval = eval = VALUE_NONE; goto moves_loop; } else if (tte) { // Never assume anything on values stored in TT - if ( (ss->staticEval = eval = tte->eval_value()) == VALUE_NONE - ||(ss->evalMargin = tte->eval_margin()) == VALUE_NONE) - eval = ss->staticEval = evaluate(pos, ss->evalMargin); + if ((ss->staticEval = eval = tte->eval_value()) == VALUE_NONE) + eval = ss->staticEval = evaluate(pos); // Can ttValue be used as a better position evaluation? if (ttValue != VALUE_NONE) @@ -609,21 +604,8 @@ namespace { } 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 - // evaluation before and after the move. - if ( !pos.captured_piece_type() - && ss->staticEval != VALUE_NONE - && (ss-1)->staticEval != VALUE_NONE - && (move = (ss-1)->currentMove) != MOVE_NULL - && type_of(move) == NORMAL) - { - Square to = to_sq(move); - Gains.update(pos.piece_on(to), to, -(ss-1)->staticEval - ss->staticEval); + eval = ss->staticEval = evaluate(pos); + TT.store(posKey, VALUE_NONE, BOUND_NONE, DEPTH_NONE, MOVE_NONE, ss->staticEval); } // Step 6. Razoring (skipped when in check) @@ -642,12 +624,10 @@ namespace { return v; } - // Step 7. Static null move pruning (skipped when in check) - // We're betting that the opponent doesn't have a move that will reduce - // the score by more than futility_margin(depth) if we do a null move. + // Step 7. post-Futility pruning (skipped when in check) if ( !PvNode && !ss->skipNullMove - && depth < 4 * ONE_PLY + && depth < 7 * ONE_PLY && eval - futility_margin(depth, (ss-1)->futilityMoveCount) >= beta && abs(beta) < VALUE_MATE_IN_MAX_PLY && abs(eval) < VALUE_KNOWN_WIN @@ -854,13 +834,13 @@ moves_loop: // When in check and at SpNode search starts from here // Update current move (this must be done after singular extension search) newDepth = depth - ONE_PLY + ext; + Depth predictedDepth = newDepth - reduction(improving, depth, moveCount); // Step 13. Futility pruning (is omitted in PV nodes) if ( !PvNode && !captureOrPromotion && !inCheck && !dangerous - /* && move != ttMove Already implicit in the next condition */ && bestValue > VALUE_MATED_IN_MAX_PLY) { // Move count based pruning @@ -874,26 +854,6 @@ moves_loop: // When in check and at SpNode search starts from here continue; } - // Value based pruning - // We illogically ignore reduction condition depth >= 3*ONE_PLY for predicted depth, - // but fixing this made program slightly weaker. - Depth predictedDepth = newDepth - reduction(improving, depth, moveCount); - futilityValue = ss->staticEval + ss->evalMargin + futility_margin(predictedDepth, moveCount) - + Gains[pos.moved_piece(move)][to_sq(move)]; - - if (futilityValue < beta) - { - bestValue = std::max(bestValue, futilityValue); - - if (SpNode) - { - splitPoint->mutex.lock(); - if (bestValue > splitPoint->bestValue) - splitPoint->bestValue = bestValue; - } - continue; - } - // Prune moves with negative SEE at low depths if ( predictedDepth < 4 * ONE_PLY && pos.see_sign(move) < 0) @@ -1079,7 +1039,7 @@ moves_loop: // When in check and at SpNode search starts from here TT.store(posKey, value_to_tt(bestValue, ss->ply), bestValue >= beta ? BOUND_LOWER : PvNode && bestMove ? BOUND_EXACT : BOUND_UPPER, - depth, bestMove, ss->staticEval, ss->evalMargin); + depth, bestMove, ss->staticEval); // Quiet best move: update killers, history and countermoves if ( bestValue >= beta @@ -1172,7 +1132,7 @@ moves_loop: // When in check and at SpNode search starts from here // Evaluate the position statically if (InCheck) { - ss->staticEval = ss->evalMargin = VALUE_NONE; + ss->staticEval = VALUE_NONE; bestValue = futilityBase = -VALUE_INFINITE; } else @@ -1180,9 +1140,8 @@ moves_loop: // When in check and at SpNode search starts from here if (tte) { // Never assume anything on values stored in TT - if ( (ss->staticEval = bestValue = tte->eval_value()) == VALUE_NONE - ||(ss->evalMargin = tte->eval_margin()) == VALUE_NONE) - ss->staticEval = bestValue = evaluate(pos, ss->evalMargin); + if ((ss->staticEval = bestValue = tte->eval_value()) == VALUE_NONE) + ss->staticEval = bestValue = evaluate(pos); // Can ttValue be used as a better position evaluation? if (ttValue != VALUE_NONE) @@ -1190,14 +1149,14 @@ moves_loop: // When in check and at SpNode search starts from here bestValue = ttValue; } else - ss->staticEval = bestValue = evaluate(pos, ss->evalMargin); + ss->staticEval = bestValue = evaluate(pos); // Stand pat. Return immediately if static value is at least beta 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); + DEPTH_NONE, MOVE_NONE, ss->staticEval); return bestValue; } @@ -1205,7 +1164,7 @@ moves_loop: // When in check and at SpNode search starts from here if (PvNode && bestValue > alpha) alpha = bestValue; - futilityBase = bestValue + ss->evalMargin + Value(128); + futilityBase = bestValue + Value(128); } // Initialize a MovePicker object for the current position, and prepare @@ -1294,7 +1253,7 @@ moves_loop: // When in check and at SpNode search starts from here else // Fail high { TT.store(posKey, value_to_tt(value, ss->ply), BOUND_LOWER, - ttDepth, move, ss->staticEval, ss->evalMargin); + ttDepth, move, ss->staticEval); return value; } @@ -1309,7 +1268,7 @@ moves_loop: // When in check and at SpNode 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, ss->staticEval); assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); @@ -1572,7 +1531,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], VALUE_NONE, VALUE_NONE); + TT.store(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, pv[ply], VALUE_NONE); assert(MoveList(pos).contains(pv[ply])); diff --git a/src/search.h b/src/search.h index e2a13606..bc841923 100644 --- a/src/search.h +++ b/src/search.h @@ -45,7 +45,6 @@ struct Stack { Move killers[2]; Depth reduction; Value staticEval; - Value evalMargin; int skipNullMove; int futilityMoveCount; }; diff --git a/src/tt.cpp b/src/tt.cpp index d2ff8704..26436806 100644 --- a/src/tt.cpp +++ b/src/tt.cpp @@ -89,7 +89,7 @@ const TTEntry* TranspositionTable::probe(const Key key) const { /// 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 key, Value v, Bound b, Depth d, Move m, Value statV, Value evalM) { +void TranspositionTable::store(const Key key, Value v, Bound b, Depth d, Move m, Value statV) { int c1, c2, c3; TTEntry *tte, *replace; @@ -117,5 +117,5 @@ void TranspositionTable::store(const Key key, Value v, Bound b, Depth d, Move m, replace = tte; } - replace->save(key32, v, b, d, m, generation, statV, evalM); + replace->save(key32, v, b, d, m, generation, statV); } diff --git a/src/tt.h b/src/tt.h index 3953d1c9..fb50ddfc 100644 --- a/src/tt.h +++ b/src/tt.h @@ -36,7 +36,7 @@ struct TTEntry { - void save(uint32_t k, Value v, Bound b, Depth d, Move m, int g, Value ev, Value em) { + void save(uint32_t k, Value v, Bound b, Depth d, Move m, int g, Value ev) { key32 = (uint32_t)k; move16 = (uint16_t)m; @@ -45,7 +45,6 @@ struct TTEntry { value16 = (int16_t)v; depth16 = (int16_t)d; evalValue = (int16_t)ev; - evalMargin = (int16_t)em; } void set_generation(uint8_t g) { generation8 = g; } @@ -56,13 +55,12 @@ struct TTEntry { Bound bound() const { return (Bound)bound8; } int generation() const { return (int)generation8; } Value eval_value() const { return (Value)evalValue; } - Value eval_margin() const { return (Value)evalMargin; } private: uint32_t key32; uint16_t move16; uint8_t bound8, generation8; - int16_t value16, depth16, evalValue, evalMargin; + int16_t value16, depth16, evalValue; }; @@ -85,7 +83,7 @@ public: void refresh(const TTEntry* tte) const; void set_size(size_t mbSize); void clear(); - void store(const Key key, Value v, Bound type, Depth d, Move m, Value statV, Value kingD); + void store(const Key key, Value v, Bound type, Depth d, Move m, Value statV); private: uint32_t hashMask; -- 2.39.2