X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=20dbd23f796763c199f4e6d0fb027dd03254f00d;hp=07700c6c2dd6cbdd27dd0a48cf985e0f4ddf74aa;hb=2e6839c9a0bd5d071f8f03f224ed59c1c665ead8;hpb=54f1c383d36f461a740eeaa93856b408e8d3faa3 diff --git a/src/search.cpp b/src/search.cpp index 07700c6c..20dbd23f 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -79,7 +79,7 @@ namespace { void idle_loop(int threadID, SplitPoint* sp); template - void split(Position& pos, SearchStack* ss, int ply, Value* alpha, const Value beta, Value* bestValue, + void split(Position& pos, SearchStack* ss, Value* alpha, const Value beta, Value* bestValue, Depth depth, Move threatMove, int moveCount, MovePicker* mp, bool pvNode); private: @@ -216,7 +216,7 @@ namespace { int8_t ReductionMatrix[2][64][64]; // [pv][depth][moveNumber] template - inline Depth reduction(Depth d, int mn) { return (Depth) ReductionMatrix[PV][Min(d / 2, 63)][Min(mn, 63)]; } + inline Depth reduction(Depth d, int mn) { return (Depth) ReductionMatrix[PV][Min(d / ONE_PLY, 63)][Min(mn, 63)]; } // Easy move margin. An easy move candidate must be at least this much // better than the second best move. @@ -267,16 +267,16 @@ namespace { Move id_loop(Position& pos, Move searchMoves[], Move* ponderMove); template - Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply); + Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth); template - Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply); + Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth); template - inline Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) { + inline Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth) { - return depth < ONE_PLY ? qsearch(pos, ss, alpha, beta, DEPTH_ZERO, ply) - : search(pos, ss, alpha, beta, depth, ply); + return depth < ONE_PLY ? qsearch(pos, ss, alpha, beta, DEPTH_ZERO) + : search(pos, ss, alpha, beta, depth); } template @@ -596,7 +596,7 @@ namespace { SearchStack ss[PLY_MAX_PLUS_2]; Value bestValues[PLY_MAX_PLUS_2]; int bestMoveChanges[PLY_MAX_PLUS_2]; - int depth, aspirationDelta, skillSamplingDepth; + int depth, aspirationDelta; Value value, alpha, beta; Move bestMove, easyMove, skillBest, skillPonder; @@ -605,7 +605,7 @@ namespace { TT.new_search(); H.clear(); *ponderMove = bestMove = easyMove = skillBest = skillPonder = MOVE_NONE; - depth = aspirationDelta = skillSamplingDepth = 0; + depth = aspirationDelta = 0; alpha = -VALUE_INFINITE, beta = VALUE_INFINITE; ss->currentMove = MOVE_NULL; // Hack to skip update_gains() @@ -622,11 +622,6 @@ namespace { return MOVE_NONE; } - // Choose a random sampling depth according to SkillLevel so that at low - // skills there is an higher risk to pick up a blunder. - if (SkillLevelEnabled) - skillSamplingDepth = 4 + SkillLevel + (RK.rand() % 4); - // Iterative deepening loop while (++depth <= PLY_MAX && (!MaxDepth || depth <= MaxDepth) && !StopRequest) { @@ -650,7 +645,7 @@ namespace { // research with bigger window until not failing high/low anymore. do { // Search starting from ss+1 to allow calling update_gains() - value = search(pos, ss+1, alpha, beta, depth * ONE_PLY, 0); + value = search(pos, ss+1, alpha, beta, depth * ONE_PLY); // Write PV back to transposition table in case the relevant entries // have been overwritten during the search. @@ -690,7 +685,7 @@ namespace { bestMoveChanges[depth] = Rml.bestMoveChanges; // Do we need to pick now the best and the ponder moves ? - if (SkillLevelEnabled && depth == skillSamplingDepth) + if (SkillLevelEnabled && depth == 1 + SkillLevel) do_skill_level(&skillBest, &skillPonder); // Send PV line to GUI and to log file @@ -771,12 +766,11 @@ namespace { // here: This is taken care of after we return from the split point. template - Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) { + Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth) { assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE); assert(beta > alpha && beta <= VALUE_INFINITE); assert(PvNode || alpha == beta - 1); - assert((Root || ply > 0) && ply < PLY_MAX); assert(pos.thread() >= 0 && pos.thread() < ThreadsMgr.active_threads()); Move movesSearched[MOVES_MAX]; @@ -797,6 +791,7 @@ namespace { refinedValue = bestValue = value = -VALUE_INFINITE; oldAlpha = alpha; isCheck = pos.is_check(); + ss->ply = (ss-1)->ply + 1; if (SpNode) { @@ -824,12 +819,12 @@ namespace { if (( StopRequest || ThreadsMgr.cutoff_at_splitpoint(threadID) || pos.is_draw() - || ply >= PLY_MAX - 1) && !Root) + || ss->ply > PLY_MAX) && !Root) return VALUE_DRAW; // Step 3. Mate distance pruning - alpha = Max(value_mated_in(ply), alpha); - beta = Min(value_mate_in(ply+1), beta); + alpha = Max(value_mated_in(ss->ply), alpha); + beta = Min(value_mate_in(ss->ply+1), beta); if (alpha >= beta) return alpha; @@ -848,11 +843,11 @@ namespace { if ( !Root && tte && (PvNode ? tte->depth() >= depth && tte->type() == VALUE_TYPE_EXACT - : ok_to_use_TT(tte, depth, beta, ply))) + : ok_to_use_TT(tte, depth, beta, ss->ply))) { TT.refresh(tte); ss->bestMove = ttMove; // Can be MOVE_NONE - return value_from_tt(tte->value(), ply); + return value_from_tt(tte->value(), ss->ply); } // Step 5. Evaluate the position statically and update parent's gain statistics @@ -864,7 +859,7 @@ namespace { ss->eval = tte->static_value(); ss->evalMargin = tte->static_value_margin(); - refinedValue = refine_eval(tte, ss->eval, ply); + refinedValue = refine_eval(tte, ss->eval, ss->ply); } else { @@ -885,7 +880,7 @@ namespace { && !pos.has_pawn_on_7th(pos.side_to_move())) { Value rbeta = beta - razor_margin(depth); - Value v = qsearch(pos, ss, rbeta-1, rbeta, DEPTH_ZERO, ply); + Value v = qsearch(pos, ss, rbeta-1, rbeta, DEPTH_ZERO); if (v < rbeta) // Logically we should return (v + razor_margin(depth)), but // surprisingly this did slightly weaker in tests. @@ -924,7 +919,7 @@ namespace { pos.do_null_move(st); (ss+1)->skipNullMove = true; - nullValue = -search(pos, ss+1, -beta, -alpha, depth-R*ONE_PLY, ply+1); + nullValue = -search(pos, ss+1, -beta, -alpha, depth-R*ONE_PLY); (ss+1)->skipNullMove = false; pos.undo_null_move(); @@ -939,7 +934,7 @@ namespace { // Do verification search at high depths ss->skipNullMove = true; - Value v = search(pos, ss, alpha, beta, depth-R*ONE_PLY, ply); + Value v = search(pos, ss, alpha, beta, depth-R*ONE_PLY); ss->skipNullMove = false; if (v >= beta) @@ -971,7 +966,7 @@ namespace { Depth d = (PvNode ? depth - 2 * ONE_PLY : depth / 2); ss->skipNullMove = true; - search(pos, ss, alpha, beta, d, ply); + search(pos, ss, alpha, beta, d); ss->skipNullMove = false; ttMove = ss->bestMove; @@ -1055,14 +1050,14 @@ split_point_start: // At split points actual search starts from here && move == tte->move() && ext < ONE_PLY) { - Value ttValue = value_from_tt(tte->value(), ply); + Value ttValue = value_from_tt(tte->value(), ss->ply); if (abs(ttValue) < VALUE_KNOWN_WIN) { Value rBeta = ttValue - int(depth); ss->excludedMove = move; ss->skipNullMove = true; - Value v = search(pos, ss, rBeta - 1, rBeta, depth / 2, ply); + Value v = search(pos, ss, rBeta - 1, rBeta, depth / 2); ss->skipNullMove = false; ss->excludedMove = MOVE_NONE; ss->bestMove = MOVE_NONE; @@ -1151,7 +1146,7 @@ split_point_start: // At split points actual search starts from here if (Root && MultiPV > 1) alpha = -VALUE_INFINITE; - value = -search(pos, ss+1, -beta, -alpha, newDepth, ply+1); + value = -search(pos, ss+1, -beta, -alpha, newDepth); } else { @@ -1172,7 +1167,7 @@ split_point_start: // At split points actual search starts from here { alpha = SpNode ? sp->alpha : alpha; Depth d = newDepth - ss->reduction; - value = -search(pos, ss+1, -(alpha+1), -alpha, d, ply+1); + value = -search(pos, ss+1, -(alpha+1), -alpha, d); doFullDepthSearch = (value > alpha); } @@ -1186,7 +1181,7 @@ split_point_start: // At split points actual search starts from here ss->reduction = 3 * ONE_PLY; Value rAlpha = alpha - 300; Depth d = newDepth - ss->reduction; - value = -search(pos, ss+1, -(rAlpha+1), -rAlpha, d, ply+1); + value = -search(pos, ss+1, -(rAlpha+1), -rAlpha, d); doFullDepthSearch = (value > rAlpha); ss->reduction = DEPTH_ZERO; // Restore original reduction } @@ -1195,13 +1190,13 @@ split_point_start: // At split points actual search starts from here if (doFullDepthSearch) { alpha = SpNode ? sp->alpha : alpha; - value = -search(pos, ss+1, -(alpha+1), -alpha, newDepth, ply+1); + value = -search(pos, ss+1, -(alpha+1), -alpha, newDepth); // Step extra. pv search (only in PV nodes) // Search only for possible new PV nodes, if instead value >= beta then // parent node fails low with value <= alpha and tries another move. if (PvNode && value > alpha && (Root || value < beta)) - value = -search(pos, ss+1, -beta, -alpha, newDepth, ply+1); + value = -search(pos, ss+1, -beta, -alpha, newDepth); } } @@ -1237,7 +1232,7 @@ split_point_start: // At split points actual search starts from here else if (SpNode) sp->betaCutoff = true; - if (value == value_mate_in(ply + 1)) + if (value == value_mate_in(ss->ply + 1)) ss->mateKiller = move; ss->bestMove = move; @@ -1297,7 +1292,7 @@ split_point_start: // At split points actual search starts from here && ThreadsMgr.available_thread_exists(threadID) && !StopRequest && !ThreadsMgr.cutoff_at_splitpoint(threadID)) - ThreadsMgr.split(pos, ss, ply, &alpha, beta, &bestValue, depth, + ThreadsMgr.split(pos, ss, &alpha, beta, &bestValue, depth, threatMove, moveCount, &mp, PvNode); } @@ -1306,7 +1301,7 @@ split_point_start: // At split points actual search starts from here // no legal moves, it must be mate or stalemate. // If one move was excluded return fail low score. if (!SpNode && !moveCount) - return excludedMove ? oldAlpha : isCheck ? value_mated_in(ply) : VALUE_DRAW; + return excludedMove ? oldAlpha : isCheck ? value_mated_in(ss->ply) : VALUE_DRAW; // Step 20. Update tables // If the search is not aborted, update the transposition table, @@ -1317,7 +1312,7 @@ split_point_start: // At split points actual search starts from here vt = bestValue <= oldAlpha ? VALUE_TYPE_UPPER : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT; - TT.store(posKey, value_to_tt(bestValue, ply), vt, depth, move, ss->eval, ss->evalMargin); + TT.store(posKey, value_to_tt(bestValue, ss->ply), vt, depth, move, ss->eval, ss->evalMargin); // Update killers and history only for non capture moves that fails high if ( bestValue >= beta @@ -1350,13 +1345,12 @@ split_point_start: // At split points actual search starts from here // less than ONE_PLY). template - Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply) { + Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth) { assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE); assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE); assert(PvNode || alpha == beta - 1); assert(depth <= 0); - assert(ply > 0 && ply < PLY_MAX); assert(pos.thread() >= 0 && pos.thread() < ThreadsMgr.active_threads()); StateInfo st; @@ -1368,9 +1362,10 @@ split_point_start: // At split points actual search starts from here Value oldAlpha = alpha; ss->bestMove = ss->currentMove = MOVE_NONE; + ss->ply = (ss-1)->ply + 1; // Check for an instant draw or maximum ply reached - if (pos.is_draw() || ply >= PLY_MAX - 1) + if (ss->ply > PLY_MAX || pos.is_draw()) return VALUE_DRAW; // Decide whether or not to include checks, this fixes also the type of @@ -1384,10 +1379,10 @@ split_point_start: // At split points actual search starts from here tte = TT.retrieve(pos.get_key()); ttMove = (tte ? tte->move() : MOVE_NONE); - if (!PvNode && tte && ok_to_use_TT(tte, ttDepth, beta, ply)) + if (!PvNode && tte && ok_to_use_TT(tte, ttDepth, beta, ss->ply)) { ss->bestMove = ttMove; // Can be MOVE_NONE - return value_from_tt(tte->value(), ply); + return value_from_tt(tte->value(), ss->ply); } // Evaluate the position statically @@ -1415,7 +1410,7 @@ split_point_start: // At split points actual search starts from here if (bestValue >= beta) { if (!tte) - TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, DEPTH_NONE, MOVE_NONE, ss->eval, evalMargin); + TT.store(pos.get_key(), value_to_tt(bestValue, ss->ply), VALUE_TYPE_LOWER, DEPTH_NONE, MOVE_NONE, ss->eval, evalMargin); return bestValue; } @@ -1504,7 +1499,7 @@ split_point_start: // At split points actual search starts from here // Make and search the move pos.do_move(move, st, ci, moveIsCheck); - value = -qsearch(pos, ss+1, -beta, -alpha, depth-ONE_PLY, ply+1); + value = -qsearch(pos, ss+1, -beta, -alpha, depth-ONE_PLY); pos.undo_move(move); assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); @@ -1524,11 +1519,11 @@ split_point_start: // At split points actual search starts from here // All legal moves have been searched. A special case: If we're in check // and no legal moves were found, it is checkmate. if (isCheck && bestValue == -VALUE_INFINITE) - return value_mated_in(ply); + return value_mated_in(ss->ply); // Update transposition table ValueType vt = (bestValue <= oldAlpha ? VALUE_TYPE_UPPER : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT); - TT.store(pos.get_key(), value_to_tt(bestValue, ply), vt, ttDepth, ss->bestMove, ss->eval, evalMargin); + TT.store(pos.get_key(), value_to_tt(bestValue, ss->ply), vt, ttDepth, ss->bestMove, ss->eval, evalMargin); assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); @@ -1933,11 +1928,8 @@ split_point_start: // At split points actual search starts from here { lastInfoTime = t; - if (dbg_show_mean) - dbg_print_mean(); - - if (dbg_show_hit_rate) - dbg_print_hit_rate(); + dbg_print_mean(); + dbg_print_hit_rate(); // Send info on searched nodes as soon as we return to root SendSearchedNodes = true; @@ -2091,9 +2083,9 @@ split_point_start: // At split points actual search starts from here (ss+1)->sp = tsp; if (tsp->pvNode) - search(pos, ss+1, tsp->alpha, tsp->beta, tsp->depth, tsp->ply); + search(pos, ss+1, tsp->alpha, tsp->beta, tsp->depth); else - search(pos, ss+1, tsp->alpha, tsp->beta, tsp->depth, tsp->ply); + search(pos, ss+1, tsp->alpha, tsp->beta, tsp->depth); assert(threads[threadID].state == THREAD_SEARCHING); @@ -2292,11 +2284,10 @@ split_point_start: // At split points actual search starts from here // call search().When all threads have returned from search() then split() returns. template - void ThreadsManager::split(Position& pos, SearchStack* ss, int ply, Value* alpha, - const Value beta, Value* bestValue, Depth depth, Move threatMove, + void ThreadsManager::split(Position& pos, SearchStack* ss, Value* alpha, const Value beta, + Value* bestValue, Depth depth, Move threatMove, int moveCount, MovePicker* mp, bool pvNode) { assert(pos.is_ok()); - assert(ply > 0 && ply < PLY_MAX); assert(*bestValue >= -VALUE_INFINITE); assert(*bestValue <= *alpha); assert(*alpha < beta); @@ -2326,7 +2317,6 @@ split_point_start: // At split points actual search starts from here splitPoint.parent = masterThread.splitPoint; splitPoint.master = master; splitPoint.betaCutoff = false; - splitPoint.ply = ply; splitPoint.depth = depth; splitPoint.threatMove = threatMove; splitPoint.alpha = *alpha;