X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=7bacb89c87fe988e53dd504869b945921d148904;hp=8e3e0dab0910e04a2470a300fb86fc4f703107c9;hb=d0b8bc5fdfae9efe75b9828ac72340f13718ebb4;hpb=9a595359628d82026513f7e978d40e944194b057 diff --git a/src/search.cpp b/src/search.cpp index 8e3e0dab..7bacb89c 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -173,7 +173,7 @@ namespace { // If the TT move is at least SingleReplyMargin better then the // remaining ones we will extend it. - const Value SingleReplyMargin = Value(0x64); + const Value SingleReplyMargin = Value(0x20); // Margins for futility pruning in the quiescence search, and at frontier // and near frontier nodes. @@ -182,10 +182,6 @@ namespace { // Each move futility margin is decreased const Value IncrementalFutilityMargin = Value(0x8); - // Remaining depth: 1 ply 1.5 ply 2 ply 2.5 ply 3 ply 3.5 ply - const Value FutilityMargins[12] = { Value(0x100), Value(0x120), Value(0x200), Value(0x220), Value(0x250), Value(0x270), - // 4 ply 4.5 ply 5 ply 5.5 ply 6 ply 6.5 ply - Value(0x2A0), Value(0x2C0), Value(0x340), Value(0x360), Value(0x3A0), Value(0x3C0) }; // Razoring const Depth RazorDepth = 4*OnePly; @@ -406,13 +402,13 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move, Problem = false; ExactMaxTime = maxTime; + if (button_was_pressed("New Game")) + loseOnTime = false; // reset at the beginning of a new game + // Read UCI option values TT.set_size(get_option_value_int("Hash")); if (button_was_pressed("Clear Hash")) - { TT.clear(); - loseOnTime = false; // reset at the beginning of a new game - } bool PonderingEnabled = get_option_value_bool("Ponder"); MultiPV = get_option_value_int("MultiPV"); @@ -526,23 +522,36 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move, << " moves to go: " << movesToGo << std::endl; - // We're ready to start thinking. Call the iterative deepening loop function - // - // FIXME we really need to cleanup all this LSN ugliness - if (!loseOnTime) + // LSN filtering. Used only for developing purpose. Disabled by default. + if ( UseLSNFiltering + && loseOnTime) { - Value v = id_loop(pos, searchMoves); - loseOnTime = ( UseLSNFiltering - && myTime < LSNTime - && myIncrement == 0 - && v < -LSNValue); + // Step 2. If after last move we decided to lose on time, do it now! + while (SearchStartTime + myTime + 1000 > get_system_time()) + ; // wait here } - else + + // We're ready to start thinking. Call the iterative deepening loop function + Value v = id_loop(pos, searchMoves); + + // LSN filtering. Used only for developing purpose. Disabled by default. + if (UseLSNFiltering) { - loseOnTime = false; // reset for next match - while (SearchStartTime + myTime + 1000 > get_system_time()) - ; // wait here - id_loop(pos, searchMoves); // to fail gracefully + // Step 1. If this is sudden death game and our position is hopeless, + // decide to lose on time. + if ( !loseOnTime // If we already lost on time, go to step 3. + && myTime < LSNTime + && myIncrement == 0 + && movesToGo == 0 + && v < -LSNValue) + { + loseOnTime = true; + } + else if (loseOnTime) + { + // Step 3. Now after stepping over the time limit, reset flag for next match. + loseOnTime = false; + } } if (UseLogFile) @@ -668,6 +677,14 @@ namespace { // searchMoves are verified, copied, scored and sorted RootMoveList rml(p, searchMoves); + if (rml.move_count() == 0) + { + if (PonderSearch) + wait_for_stop_or_ponderhit(); + + return pos.is_check()? -VALUE_MATE : VALUE_DRAW; + } + // Print RootMoveList c'tor startup scoring to the standard output, // so that we print information also for iteration 1. std::cout << "info depth " << 1 << "\ninfo depth " << 1 @@ -726,7 +743,7 @@ namespace { // Write PV to transposition table, in case the relevant entries have // been overwritten during the search. - TT.insert_pv(p, ss[0].pv); + //TT.insert_pv(p, ss[0].pv); if (AbortSearch) break; // Value cannot be trusted. Break out immediately! @@ -1108,7 +1125,14 @@ namespace { return alpha; // Transposition table lookup. At PV nodes, we don't use the TT for - // pruning, but only for move ordering. + // pruning, but only for move ordering. This is to avoid problems in + // the following areas: + // + // * Repetition draw detection + // * Fifty move rule detection + // * Searching for a mate + // * Printing of full PV line + // tte = TT.retrieve(pos.get_key()); ttMove = (tte ? tte->move() : MOVE_NONE); @@ -1117,6 +1141,10 @@ namespace { { search_pv(pos, ss, alpha, beta, depth-2*OnePly, ply, threadID); ttMove = ss[ply].pv[ply]; + tte = TT.retrieve(pos.get_key()); + + // If tte->move() != MOVE_NONE then it equals ttMove + assert(!(tte && tte->move()) || tte->move() == ttMove); } // Initialize a MovePicker object for the current position, and prepare @@ -1145,8 +1173,9 @@ namespace { // To verify this we do a reduced search on all the other moves but the ttMove, // if result is lower then TT value minus a margin then we assume ttMove is the // only one playable. It is a kind of relaxed single reply extension. - if ( depth >= 4 * OnePly - && move == ttMove + if ( depth >= 6 * OnePly + && tte + && move == tte->move() && ext < OnePly && is_lower_bound(tte->type()) && tte->depth() >= depth - 3 * OnePly) @@ -1155,8 +1184,7 @@ namespace { if (abs(ttValue) < VALUE_KNOWN_WIN) { - Depth d = Max(Min(depth / 2, depth - 4 * OnePly), OnePly); - Value excValue = search(pos, ss, ttValue - SingleReplyMargin, d, ply, false, threadID, ttMove); + Value excValue = search(pos, ss, ttValue - SingleReplyMargin, depth / 2, ply, false, threadID, move); // If search result is well below the foreseen score of the ttMove then we // assume ttMove is the only one realistically playable and we extend it. @@ -1335,7 +1363,7 @@ namespace { if (tte && ok_to_use_TT(tte, depth, beta, ply)) { - ss[ply].currentMove = ttMove; // can be MOVE_NONE + ss[ply].currentMove = ttMove; // Can be MOVE_NONE return value_from_tt(tte->value(), ply); } @@ -1411,6 +1439,7 @@ namespace { { search(pos, ss, beta, Min(depth/2, depth-2*OnePly), ply, false, threadID); ttMove = ss[ply].pv[ply]; + tte = TT.retrieve(pos.get_key()); } // Initialize a MovePicker object for the current position, and prepare @@ -1420,12 +1449,13 @@ namespace { futilityValue = VALUE_NONE; useFutilityPruning = depth < SelectiveDepth && !isCheck; + // Calculate depth dependant futility pruning parameters + const int FutilityMoveCountMargin = 3 + (1 << (3 * int(depth) / 8)); + const int FutilityValueMargin = 112 * bitScanReverse32(int(depth) * int(depth) / 2); + // Avoid calling evaluate() if we already have the score in TT if (tte && (tte->type() & VALUE_TYPE_EVAL)) - futilityValue = value_from_tt(tte->value(), ply) + FutilityMargins[int(depth) - 2]; - - // Move count pruning limit - const int MCLimit = 3 + (1 << (3*int(depth)/8)); + futilityValue = value_from_tt(tte->value(), ply) + FutilityValueMargin; // Loop through all legal moves until no moves remain or a beta cutoff occurs while ( bestValue < beta @@ -1448,9 +1478,10 @@ namespace { // To verify this we do a reduced search on all the other moves but the ttMove, // if result is lower then TT value minus a margin then we assume ttMove is the // only one playable. It is a kind of relaxed single reply extension. - if ( depth >= 4 * OnePly - && !excludedMove // do not allow recursive single-reply search - && move == ttMove + if ( depth >= 8 * OnePly + && tte + && move == tte->move() + && !excludedMove // Do not allow recursive single-reply search && ext < OnePly && is_lower_bound(tte->type()) && tte->depth() >= depth - 3 * OnePly) @@ -1459,13 +1490,12 @@ namespace { if (abs(ttValue) < VALUE_KNOWN_WIN) { - Depth d = Max(Min(depth / 2, depth - 4 * OnePly), OnePly); - Value excValue = search(pos, ss, ttValue - SingleReplyMargin, d, ply, false, threadID, ttMove); + Value excValue = search(pos, ss, ttValue - SingleReplyMargin, depth / 2, ply, false, threadID, move); // If search result is well below the foreseen score of the ttMove then we // assume ttMove is the only one realistically playable and we extend it. if (excValue < ttValue - SingleReplyMargin) - ext = (depth >= 8 * OnePly) ? OnePly : ext + OnePly / 2; + ext = OnePly; } } @@ -1481,26 +1511,22 @@ namespace { && move != ttMove) { // History pruning. See ok_to_prune() definition - if ( moveCount >= MCLimit + if ( moveCount >= FutilityMoveCountMargin && ok_to_prune(pos, move, ss[ply].threatMove, depth) && bestValue > value_mated_in(PLY_MAX)) continue; // Value based pruning - if (approximateEval < beta) - { - if (futilityValue == VALUE_NONE) - futilityValue = evaluate(pos, ei, threadID) - + 64*(2+bitScanReverse32(int(depth) * int(depth))); + if (futilityValue == VALUE_NONE) + futilityValue = evaluate(pos, ei, threadID) + FutilityValueMargin; - futilityValueScaled = futilityValue - moveCount * IncrementalFutilityMargin; + futilityValueScaled = futilityValue - moveCount * IncrementalFutilityMargin; - if (futilityValueScaled < beta) - { - if (futilityValueScaled > bestValue) - bestValue = futilityValueScaled; - continue; - } + if (futilityValueScaled < beta) + { + if (futilityValueScaled > bestValue) + bestValue = futilityValueScaled; + continue; } } @@ -1520,7 +1546,7 @@ namespace { value = -search(pos, ss, -(beta-1), newDepth-OnePly, ply+1, true, threadID); } else - value = beta; // Just to trigger next condition + value = beta; // Just to trigger next condition if (value >= beta) // Go with full depth non-pv search { @@ -1534,12 +1560,12 @@ namespace { // New best move? if (value > bestValue) { - bestValue = value; - if (value >= beta) - update_pv(ss, ply); + bestValue = value; + if (value >= beta) + update_pv(ss, ply); - if (value == value_mate_in(ply + 1)) - ss[ply].mateKiller = move; + if (value == value_mate_in(ply + 1)) + ss[ply].mateKiller = move; } // Split? @@ -1552,7 +1578,7 @@ namespace { && !thread_should_stop(threadID) && split(pos, ss, ply, &beta, &beta, &bestValue, futilityValue, approximateEval, depth, &moveCount, &mp, threadID, false)) - break; + break; } // All legal moves have been searched. A special case: If there were @@ -1631,10 +1657,10 @@ namespace { } ttMove = (tte ? tte->move() : MOVE_NONE); - // Evaluate the position statically isCheck = pos.is_check(); ei.futilityMargin = Value(0); // Manually initialize futilityMargin + // Evaluate the position statically if (isCheck) staticValue = -VALUE_INFINITE; @@ -1643,7 +1669,7 @@ namespace { // Use the cached evaluation score if possible assert(ei.futilityMargin == Value(0)); - staticValue = tte->value(); + staticValue = value_from_tt(tte->value(), ply); } else staticValue = evaluate(pos, ei, threadID); @@ -1788,6 +1814,8 @@ namespace { bool useFutilityPruning = sp->depth < SelectiveDepth && !isCheck; + const int FutilityValueMargin = 112 * bitScanReverse32(int(sp->depth) * int(sp->depth) / 2); + while ( sp->bestValue < sp->beta && !thread_should_stop(threadID) && (move = sp->mp->get_next_move(sp->lock)) != MOVE_NONE) @@ -1825,8 +1853,7 @@ namespace { if (sp->futilityValue == VALUE_NONE) { EvalInfo ei; - sp->futilityValue = evaluate(pos, ei, threadID) - + FutilityMargins[int(sp->depth) - 2]; + sp->futilityValue = evaluate(pos, ei, threadID) + FutilityValueMargin; } if (sp->futilityValue < sp->beta) @@ -2496,8 +2523,8 @@ namespace { Value v = value_from_tt(tte->value(), ply); return ( tte->depth() >= depth - || v >= Max(value_mate_in(100), beta) - || v < Min(value_mated_in(100), beta)) + || v >= Max(value_mate_in(PLY_MAX), beta) + || v < Min(value_mated_in(PLY_MAX), beta)) && ( (is_lower_bound(tte->type()) && v >= beta) || (is_upper_bound(tte->type()) && v < beta));