X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=516f2d051cc503f058d2f541a7d46ef9fcb8800e;hp=27a67a639401e3d18e48a3416a1ea4592ce1f072;hb=076b62310ee874adb38d2c9610aad163db65e2e8;hpb=927f1b0bd30a5b2cfdcdf163f26f528738509064 diff --git a/src/search.cpp b/src/search.cpp index 27a67a63..516f2d05 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -79,8 +79,8 @@ namespace { void idle_loop(int threadID, SplitPoint* sp); template - void split(Position& pos, SearchStack* ss, int ply, Value* alpha, const Value beta, Value* bestValue, - Depth depth, Move threatMove, bool mateThreat, int moveCount, MovePicker* mp, bool pvNode); + void split(Position& pos, SearchStack* ss, Value* alpha, const Value beta, Value* bestValue, + Depth depth, Move threatMove, int moveCount, MovePicker* mp, bool pvNode); private: Depth minimumSplitDepth; @@ -192,8 +192,8 @@ namespace { // Extensions. Configurable UCI options // Array index 0 is used at non-PV nodes, index 1 at PV nodes. - Depth CheckExtension[2], PawnPushTo7thExtension[2], PassedPawnExtension[2]; - Depth PawnEndgameExtension[2], MateThreatExtension[2]; + Depth CheckExtension[2], PawnPushTo7thExtension[2]; + Depth PassedPawnExtension[2], PawnEndgameExtension[2]; // Minimum depth for use of singular extension const Depth SingularExtensionDepth[2] = { 8 * ONE_PLY /* non-PV */, 6 * ONE_PLY /* PV */}; @@ -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,20 +267,20 @@ 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 - Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck, bool mateThreat, bool* dangerous); + Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck, bool* dangerous); bool check_is_dangerous(Position &pos, Move move, Value futilityBase, Value beta, Value *bValue); bool connected_moves(const Position& pos, Move m1, Move m2); @@ -484,8 +484,6 @@ bool think(Position& pos, bool infinite, bool ponder, int time[], int increment[ PassedPawnExtension[0] = Options["Passed Pawn Extension (non-PV nodes)"].value(); PawnEndgameExtension[1] = Options["Pawn Endgame Extension (PV nodes)"].value(); PawnEndgameExtension[0] = Options["Pawn Endgame Extension (non-PV nodes)"].value(); - MateThreatExtension[1] = Options["Mate Threat Extension (PV nodes)"].value(); - MateThreatExtension[0] = Options["Mate Threat Extension (non-PV nodes)"].value(); UCIMultiPV = Options["MultiPV"].value(); SkillLevel = Options["Skill level"].value(); UseLogFile = Options["Use Search Log"].value(); @@ -652,7 +650,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. @@ -773,12 +771,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]; @@ -792,7 +789,6 @@ namespace { Value bestValue, value, oldAlpha; Value refinedValue, nullValue, futilityBase, futilityValueScaled; // Non-PV specific bool isPvMove, isCheck, singularExtensionNode, moveIsCheck, captureOrPromotion, dangerous, isBadCap; - bool mateThreat = false; int moveCount = 0, playedMoveCount = 0; int threadID = pos.thread(); SplitPoint* sp = NULL; @@ -800,6 +796,7 @@ namespace { refinedValue = bestValue = value = -VALUE_INFINITE; oldAlpha = alpha; isCheck = pos.is_check(); + ss->ply = (ss-1)->ply + 1; if (SpNode) { @@ -807,7 +804,6 @@ namespace { tte = NULL; ttMove = excludedMove = MOVE_NONE; threatMove = sp->threatMove; - mateThreat = sp->mateThreat; goto split_point_start; } else if (Root) @@ -828,12 +824,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; @@ -852,11 +848,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 @@ -868,7 +864,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 { @@ -889,7 +885,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. @@ -928,7 +924,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(); @@ -943,7 +939,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) @@ -957,9 +953,6 @@ namespace { // move which was reduced. If a connection is found, return a fail // low score (which will cause the reduced move to fail high in the // parent node, which will trigger a re-search with full depth). - if (nullValue == value_mated_in(ply + 2)) - mateThreat = true; - threatMove = (ss+1)->bestMove; if ( depth < ThreatDepth @@ -978,17 +971,13 @@ 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; tte = TT.retrieve(posKey); } - // Mate threat detection for PV nodes, otherwise we use null move search - if (PvNode) - mateThreat = pos.has_mate_threat(); - split_point_start: // At split points actual search starts from here // Initialize a MovePicker object for the current position @@ -1055,7 +1044,7 @@ split_point_start: // At split points actual search starts from here captureOrPromotion = pos.move_is_capture_or_promotion(move); // Step 11. Decide the new search depth - ext = extension(pos, move, captureOrPromotion, moveIsCheck, mateThreat, &dangerous); + ext = extension(pos, move, captureOrPromotion, moveIsCheck, &dangerous); // Singular extension search. If all moves but one fail low on a search of // (alpha-s, beta-s), and just one fails high on (alpha, beta), then that move @@ -1066,14 +1055,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; @@ -1162,7 +1151,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 { @@ -1183,7 +1172,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); } @@ -1197,7 +1186,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 } @@ -1206,13 +1195,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); } } @@ -1248,7 +1237,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; @@ -1308,8 +1297,8 @@ 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, - threatMove, mateThreat, moveCount, &mp, PvNode); + ThreadsMgr.split(pos, ss, &alpha, beta, &bestValue, depth, + threatMove, moveCount, &mp, PvNode); } // Step 19. Check for mate and stalemate @@ -1317,7 +1306,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, @@ -1328,7 +1317,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 @@ -1361,13 +1350,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; @@ -1379,9 +1367,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 @@ -1395,10 +1384,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 @@ -1426,7 +1415,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; } @@ -1515,7 +1504,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); @@ -1535,11 +1524,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); @@ -1696,21 +1685,15 @@ split_point_start: // At split points actual search starts from here // the move is marked as 'dangerous' so, at least, we avoid to prune it. template Depth extension(const Position& pos, Move m, bool captureOrPromotion, - bool moveIsCheck, bool mateThreat, bool* dangerous) { + bool moveIsCheck, bool* dangerous) { assert(m != MOVE_NONE); Depth result = DEPTH_ZERO; - *dangerous = moveIsCheck | mateThreat; - - if (*dangerous) - { - if (moveIsCheck && pos.see_sign(m) >= 0) - result += CheckExtension[PvNode]; + *dangerous = moveIsCheck; - if (mateThreat) - result += MateThreatExtension[PvNode]; - } + if (moveIsCheck && pos.see_sign(m) >= 0) + result += CheckExtension[PvNode]; if (pos.type_of_piece_on(move_from(m)) == PAWN) { @@ -1950,11 +1933,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; @@ -2108,9 +2088,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); @@ -2309,11 +2289,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, - bool mateThreat, int moveCount, MovePicker* mp, bool pvNode) { + 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); @@ -2343,10 +2322,8 @@ 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.mateThreat = mateThreat; splitPoint.alpha = *alpha; splitPoint.beta = beta; splitPoint.pvNode = pvNode; @@ -2460,13 +2437,13 @@ split_point_start: // At split points actual search starts from here TTEntry* tte; int ply = 1; - assert(pv[0] != MOVE_NONE && move_is_legal(pos, pv[0])); + assert(pv[0] != MOVE_NONE && pos.move_is_legal(pv[0])); pos.do_move(pv[0], *st++); while ( (tte = TT.retrieve(pos.get_key())) != NULL && tte->move() != MOVE_NONE - && move_is_legal(pos, tte->move()) + && pos.move_is_legal(tte->move()) && ply < PLY_MAX && (!pos.is_draw() || ply < 2)) { @@ -2490,7 +2467,7 @@ split_point_start: // At split points actual search starts from here Value v, m = VALUE_NONE; int ply = 0; - assert(pv[0] != MOVE_NONE && move_is_legal(pos, pv[0])); + assert(pv[0] != MOVE_NONE && pos.move_is_legal(pv[0])); do { k = pos.get_key();