X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=272634d14a8154590065feb5028347564dafa362;hp=7cf4a8a3b583054b651d17b7c422564e859a7296;hb=413b24380993cfdb7578ebe10b6a71b51bd8fb5b;hpb=158864270a055fe20dca4a87f4b7a8aa9cedfeb9 diff --git a/src/search.cpp b/src/search.cpp index 7cf4a8a3..272634d1 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -25,9 +25,9 @@ #include #include "evaluate.h" +#include "misc.h" #include "movegen.h" #include "movepick.h" -#include "misc.h" #include "search.h" #include "timeman.h" #include "thread.h" @@ -457,13 +457,13 @@ namespace { Move pv[MAX_PLY+1], quietsSearched[64]; StateInfo st; - const TTEntry *tte; + TTEntry* tte; SplitPoint* splitPoint; Key posKey; Move ttMove, move, excludedMove, bestMove; Depth extension, newDepth, predictedDepth; Value bestValue, value, ttValue, eval, nullValue, futilityValue; - bool inCheck, givesCheck, singularExtensionNode, improving; + bool ttHit, inCheck, givesCheck, singularExtensionNode, improving; bool captureOrPromotion, dangerous, doFullDepthSearch; int moveCount, quietCount; @@ -477,6 +477,7 @@ namespace { bestMove = splitPoint->bestMove; bestValue = splitPoint->bestValue; tte = NULL; + ttHit = false; ttMove = excludedMove = MOVE_NONE; ttValue = VALUE_NONE; @@ -514,7 +515,7 @@ namespace { assert(0 <= ss->ply && ss->ply < MAX_PLY); ss->currentMove = ss->ttMove = (ss+1)->excludedMove = bestMove = MOVE_NONE; - (ss+1)->skipNullMove = false; (ss+1)->reduction = DEPTH_ZERO; + (ss+1)->skipEarlyPruning = false; (ss+1)->reduction = DEPTH_ZERO; (ss+2)->killers[0] = (ss+2)->killers[1] = MOVE_NONE; // Step 4. Transposition table lookup @@ -522,13 +523,13 @@ namespace { // TT value, so we use a different position key in case of an excluded move. excludedMove = ss->excludedMove; posKey = excludedMove ? pos.exclusion_key() : pos.key(); - tte = TT.probe(posKey); - ss->ttMove = ttMove = RootNode ? RootMoves[PVIdx].pv[0] : tte ? tte->move() : MOVE_NONE; - ttValue = tte ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE; + tte = TT.probe(posKey, ttHit); + ss->ttMove = ttMove = RootNode ? RootMoves[PVIdx].pv[0] : ttHit ? tte->move() : MOVE_NONE; + ttValue = ttHit ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE; // At non-PV nodes we check for a fail high/low. We don't probe at PV nodes if ( !PvNode - && tte + && ttHit && tte->depth() >= depth && ttValue != VALUE_NONE // Only in case of TT access race && (ttValue >= beta ? (tte->bound() & BOUND_LOWER) @@ -564,9 +565,9 @@ namespace { : v > drawScore ? VALUE_MATE - MAX_PLY - ss->ply : VALUE_DRAW + 2 * v * drawScore; - TT.store(posKey, value_to_tt(value, ss->ply), BOUND_EXACT, - std::min(DEPTH_MAX - ONE_PLY, depth + 6 * ONE_PLY), - MOVE_NONE, VALUE_NONE); + tte->save(posKey, value_to_tt(value, ss->ply), BOUND_EXACT, + std::min(DEPTH_MAX - ONE_PLY, depth + 6 * ONE_PLY), + MOVE_NONE, VALUE_NONE, TT.generation()); return value; } @@ -580,7 +581,7 @@ namespace { goto moves_loop; } - else if (tte) + else if (ttHit) { // Never assume anything on values stored in TT if ((ss->staticEval = eval = tte->eval_value()) == VALUE_NONE) @@ -596,9 +597,12 @@ namespace { eval = ss->staticEval = (ss-1)->currentMove != MOVE_NULL ? evaluate(pos) : -(ss-1)->staticEval + 2 * Eval::Tempo; - TT.store(posKey, VALUE_NONE, BOUND_NONE, DEPTH_NONE, MOVE_NONE, ss->staticEval); + tte->save(posKey, VALUE_NONE, BOUND_NONE, DEPTH_NONE, MOVE_NONE, ss->staticEval, TT.generation()); } + if (ss->skipEarlyPruning) + goto moves_loop; + if ( !pos.captured_piece_type() && ss->staticEval != VALUE_NONE && (ss-1)->staticEval != VALUE_NONE @@ -629,7 +633,6 @@ namespace { // Step 7. Futility pruning: child node (skipped when in check) if ( !PvNode - && !ss->skipNullMove && depth < 7 * ONE_PLY && eval - futility_margin(depth) >= beta && eval < VALUE_KNOWN_WIN // Do not return unproven wins @@ -638,7 +641,6 @@ namespace { // Step 8. Null move search with verification search (is omitted in PV nodes) if ( !PvNode - && !ss->skipNullMove && depth >= 2 * ONE_PLY && eval >= beta && pos.non_pawn_material(pos.side_to_move())) @@ -651,10 +653,10 @@ namespace { Depth R = (3 + depth / 4 + std::min((eval - beta) / PawnValueMg, 3)) * ONE_PLY; pos.do_null_move(st); - (ss+1)->skipNullMove = true; + (ss+1)->skipEarlyPruning = true; nullValue = depth-R < ONE_PLY ? -qsearch(pos, ss+1, -beta, -beta+1, DEPTH_ZERO) : - search(pos, ss+1, -beta, -beta+1, depth-R, !cutNode); - (ss+1)->skipNullMove = false; + (ss+1)->skipEarlyPruning = false; pos.undo_null_move(); if (nullValue >= beta) @@ -667,10 +669,10 @@ namespace { return nullValue; // Do verification search at high depths - ss->skipNullMove = true; + ss->skipEarlyPruning = true; Value v = depth-R < ONE_PLY ? qsearch(pos, ss, beta-1, beta, DEPTH_ZERO) : search(pos, ss, beta-1, beta, depth-R, false); - ss->skipNullMove = false; + ss->skipEarlyPruning = false; if (v >= beta) return nullValue; @@ -683,7 +685,6 @@ namespace { // prune the previous move. if ( !PvNode && depth >= 5 * ONE_PLY - && !ss->skipNullMove && abs(beta) < VALUE_MATE_IN_MAX_PLY) { Value rbeta = std::min(beta + 200, VALUE_INFINITE); @@ -714,12 +715,12 @@ namespace { && (PvNode || ss->staticEval + 256 >= beta)) { Depth d = 2 * (depth - 2 * ONE_PLY) - (PvNode ? DEPTH_ZERO : depth / 2); - ss->skipNullMove = true; + ss->skipEarlyPruning = true; search(pos, ss, alpha, beta, d / 2, true); - ss->skipNullMove = false; + ss->skipEarlyPruning = false; - tte = TT.probe(posKey); - ttMove = tte ? tte->move() : MOVE_NONE; + tte = TT.probe(posKey, ttHit); + ttMove = ttHit ? tte->move() : MOVE_NONE; } moves_loop: // When in check and at SpNode search starts from here @@ -816,9 +817,9 @@ moves_loop: // When in check and at SpNode search starts from here { Value rBeta = ttValue - 2 * depth / ONE_PLY; ss->excludedMove = move; - ss->skipNullMove = true; + ss->skipEarlyPruning = true; value = search(pos, ss, rBeta - 1, rBeta, depth / 2, cutNode); - ss->skipNullMove = false; + ss->skipEarlyPruning = false; ss->excludedMove = MOVE_NONE; if (value < rBeta) @@ -1079,10 +1080,10 @@ moves_loop: // When in check and at SpNode search starts from here else if (bestValue >= beta && !pos.capture_or_promotion(bestMove) && !inCheck) update_stats(pos, ss, bestMove, depth, quietsSearched, quietCount - 1); - TT.store(posKey, value_to_tt(bestValue, ss->ply), - bestValue >= beta ? BOUND_LOWER : - PvNode && bestMove ? BOUND_EXACT : BOUND_UPPER, - depth, bestMove, ss->staticEval); + tte->save(posKey, value_to_tt(bestValue, ss->ply), + bestValue >= beta ? BOUND_LOWER : + PvNode && bestMove ? BOUND_EXACT : BOUND_UPPER, + depth, bestMove, ss->staticEval, TT.generation()); assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); @@ -1107,11 +1108,11 @@ moves_loop: // When in check and at SpNode search starts from here Move pv[MAX_PLY+1]; StateInfo st; - const TTEntry* tte; + TTEntry* tte; Key posKey; Move ttMove, move, bestMove; Value bestValue, value, ttValue, futilityValue, futilityBase, oldAlpha; - bool givesCheck, evasionPrunable; + bool ttHit, givesCheck, evasionPrunable; Depth ttDepth; if (PvNode) @@ -1138,12 +1139,12 @@ moves_loop: // When in check and at SpNode search starts from here // Transposition table lookup posKey = pos.key(); - tte = TT.probe(posKey); - ttMove = tte ? tte->move() : MOVE_NONE; - ttValue = tte ? value_from_tt(tte->value(),ss->ply) : VALUE_NONE; + tte = TT.probe(posKey, ttHit); + ttMove = ttHit ? tte->move() : MOVE_NONE; + ttValue = ttHit ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE; if ( !PvNode - && tte + && ttHit && tte->depth() >= ttDepth && ttValue != VALUE_NONE // Only in case of TT access race && (ttValue >= beta ? (tte->bound() & BOUND_LOWER) @@ -1161,7 +1162,7 @@ moves_loop: // When in check and at SpNode search starts from here } else { - if (tte) + if (ttHit) { // Never assume anything on values stored in TT if ((ss->staticEval = bestValue = tte->eval_value()) == VALUE_NONE) @@ -1179,9 +1180,9 @@ moves_loop: // When in check and at SpNode search starts from here // 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); + if (!ttHit) + tte->save(pos.key(), value_to_tt(bestValue, ss->ply), BOUND_LOWER, + DEPTH_NONE, MOVE_NONE, ss->staticEval, TT.generation()); return bestValue; } @@ -1279,8 +1280,8 @@ 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); + tte->save(posKey, value_to_tt(value, ss->ply), BOUND_LOWER, + ttDepth, move, ss->staticEval, TT.generation()); return value; } @@ -1293,9 +1294,9 @@ moves_loop: // When in check and at SpNode search starts from here if (InCheck && bestValue == -VALUE_INFINITE) return mated_in(ss->ply); // Plies to mate from the root - TT.store(posKey, value_to_tt(bestValue, ss->ply), - PvNode && bestValue > oldAlpha ? BOUND_EXACT : BOUND_UPPER, - ttDepth, bestMove, ss->staticEval); + tte->save(posKey, value_to_tt(bestValue, ss->ply), + PvNode && bestValue > oldAlpha ? BOUND_EXACT : BOUND_UPPER, + ttDepth, bestMove, ss->staticEval, TT.generation()); assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); @@ -1469,15 +1470,15 @@ moves_loop: // When in check and at SpNode search starts from here void RootMove::insert_pv_in_tt(Position& pos) { StateInfo state[MAX_PLY], *st = state; - const TTEntry* tte; size_t idx = 0; for ( ; idx < pv.size(); ++idx) { - tte = TT.probe(pos.key()); + bool ttHit; + TTEntry* tte = TT.probe(pos.key(), ttHit); - if (!tte || tte->move() != pv[idx]) // Don't overwrite correct entries - TT.store(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, pv[idx], VALUE_NONE); + if (!ttHit || tte->move() != pv[idx]) // Don't overwrite correct entries + tte->save(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, pv[idx], VALUE_NONE, TT.generation()); assert(MoveList(pos).contains(pv[idx]));