X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=6aa13a5e84573ecfb6a3c5c1ecdecface8e72e67;hp=2b41ec448da40db166b8a107e7a529ddc0a491e1;hb=6f28bcd483647e9ea1e7da629ed900fd254430ca;hpb=8f59de48f559e477dc383d5b51a0b842986758d0 diff --git a/src/search.cpp b/src/search.cpp index 2b41ec44..6aa13a5e 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -47,6 +47,60 @@ namespace { /// Types + //The IterationInfoType is used to store search history + //iteration by iteration. + // + //Because we use relatively small (dynamic) aspiration window, + //there happens many fail highs and fail lows in root. And + //because we don't do researches in those cases, "value" stored + //here is not necessarily exact. Instead in case of fail high/low + //we guess what the right value might be and store our guess + //as "speculated value" and then move on... + + class IterationInfoType { + private: + Value _value; + Value _speculatedValue; + bool _failHigh; + bool _failLow; + public: + IterationInfoType() { + clear(); + } + + inline void clear() { + set(Value(0)); + } + + inline void set(Value v) { + set(v, v, false, false); + } + + inline void set(Value v, Value specV, bool fHigh, bool fLow) { + _value = v; + _speculatedValue = specV; + _failHigh = fHigh; + _failLow = fLow; + } + + inline Value value() { + return _value; + } + + inline Value speculated_value() { + return _speculatedValue; + } + + inline bool fail_high() { + return _failHigh; + } + + inline bool fail_low() { + return _failLow; + } + }; + + // The BetaCounterType class is used to order moves at ply one. // Apart for the first one that has its score, following moves // normally have score -VALUE_INFINITE, so are ordered according @@ -125,9 +179,6 @@ namespace { const bool UseIIDAtPVNodes = true; const bool UseIIDAtNonPVNodes = false; - // Use null move driven internal iterative deepening? - bool UseNullDrivenIID = false; - // Internal iterative deepening margin. At Non-PV moves, when // UseIIDAtNonPVNodes is true, we do an internal iterative deepening search // when the static evaluation is at most IIDMargin below beta. @@ -196,11 +247,10 @@ namespace { // Iteration counters int Iteration; - bool LastIterations; BetaCounterType BetaCounter; // Scores and number of times the best move changed for each iteration: - Value ValueByIteration[PLY_MAX_PLUS_2]; + IterationInfoType IterationInfo[PLY_MAX_PLUS_2]; int BestMoveChangesByIteration[PLY_MAX_PLUS_2]; // MultiPV mode @@ -210,7 +260,7 @@ namespace { int SearchStartTime; int MaxNodes, MaxDepth; int MaxSearchTime, AbsoluteMaxSearchTime, ExtraSearchTime; - Move BestRootMove, PonderMove, EasyMove; + Move EasyMove; int RootMoveNumber; bool InfiniteSearch; bool PonderSearch; @@ -218,6 +268,7 @@ namespace { bool AbortSearch; bool Quit; bool FailHigh; + bool FailLow; bool Problem; bool PonderingEnabled; int ExactMaxTime; @@ -250,7 +301,8 @@ namespace { /// Functions Value id_loop(const Position &pos, Move searchMoves[]); - Value root_search(Position &pos, SearchStack ss[], RootMoveList &rml); + Value root_search(Position &pos, SearchStack ss[], RootMoveList &rml, + Value alpha, Value beta); Value search_pv(Position &pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID); Value search(Position &pos, SearchStack ss[], Value beta, @@ -259,9 +311,7 @@ namespace { Depth depth, int ply, int threadID); void sp_search(SplitPoint *sp, int threadID); void sp_search_pv(SplitPoint *sp, int threadID); - void init_search_stack(SearchStack& ss); - void init_search_stack(SearchStack ss[]); - void init_node(const Position &pos, SearchStack ss[], int ply, int threadID); + void init_node(SearchStack ss[], int ply, int threadID); void update_pv(SearchStack ss[], int ply); void sp_update_pv(SearchStack *pss, SearchStack ss[], int ply); bool connected_moves(const Position &pos, Move m1, Move m2); @@ -290,8 +340,8 @@ namespace { bool thread_is_available(int slave, int master); bool idle_thread_exists(int master); bool split(const Position &pos, SearchStack *ss, int ply, - Value *alpha, Value *beta, Value *bestValue, Depth depth, - int *moves, MovePicker *mp, int master, bool pvNode); + Value *alpha, Value *beta, Value *bestValue, Depth depth, int *moves, + MovePicker *mp, Bitboard dcCandidates, int master, bool pvNode); void wake_sleeping_threads(); #if !defined(_MSC_VER) @@ -324,6 +374,23 @@ History H; // Should be made local? SearchStack EmptySearchStack; +// SearchStack::init() initializes a search stack. Used at the beginning of a +// new search from the root. +void SearchStack::init(int ply) { + + pv[ply] = pv[ply + 1] = MOVE_NONE; + currentMove = threatMove = MOVE_NONE; + reduction = Depth(0); +} + +void SearchStack::initKillers() { + + mateKiller = MOVE_NONE; + for (int i = 0; i < KILLER_MAX; i++) + killers[i] = MOVE_NONE; +} + + //// //// Functions //// @@ -356,8 +423,6 @@ void think(const Position &pos, bool infinite, bool ponder, int side_to_move, // Initialize global search variables Idle = false; SearchStartTime = get_system_time(); - BestRootMove = MOVE_NONE; - PonderMove = MOVE_NONE; EasyMove = MOVE_NONE; for (int i = 0; i < THREAD_MAX; i++) { @@ -371,6 +436,7 @@ void think(const Position &pos, bool infinite, bool ponder, int side_to_move, AbortSearch = false; Quit = false; FailHigh = false; + FailLow = false; Problem = false; ExactMaxTime = maxTime; @@ -411,7 +477,6 @@ void think(const Position &pos, bool infinite, bool ponder, int side_to_move, if (UseLogFile) LogFile.open(get_option_value_string("Search Log Filename").c_str(), std::ios::out | std::ios::app); - UseNullDrivenIID = get_option_value_bool("Null driven IID"); UseQSearchFutilityPruning = get_option_value_bool("Futility Pruning (Quiescence Search)"); UseFutilityPruning = get_option_value_bool("Futility Pruning (Main Search)"); @@ -588,7 +653,8 @@ void init_threads() { } // Init also the empty search stack - init_search_stack(EmptySearchStack); + EmptySearchStack.init(0); + EmptySearchStack.initKillers(); } @@ -640,17 +706,18 @@ namespace { // Initialize TT.new_search(); H.clear(); - init_search_stack(ss); - - ValueByIteration[0] = Value(0); - ValueByIteration[1] = rml.get_move_score(0); + for (int i = 0; i < 3; i++) + { + ss[i].init(i); + ss[i].initKillers(); + } + IterationInfo[1].set(rml.get_move_score(0)); Iteration = 1; - LastIterations = false; EasyMove = rml.scan_for_easy_move(); // Iterative deepening loop - while (!AbortSearch && Iteration < PLY_MAX) + while (Iteration < PLY_MAX) { // Initialize iteration rml.sort(); @@ -661,8 +728,59 @@ namespace { std::cout << "info depth " << Iteration << std::endl; + //Calculate dynamic search window based on previous iterations. + Value alpha; + Value beta; + + if (MultiPV == 1 && Iteration >= 6) { + Value prevDelta1 = IterationInfo[Iteration - 1].speculated_value() - IterationInfo[Iteration - 2].speculated_value(); + Value prevDelta2 = IterationInfo[Iteration - 2].speculated_value() - IterationInfo[Iteration - 3].speculated_value(); + + Value delta = Max((2 * Abs(prevDelta1) + Abs(prevDelta2)) , ProblemMargin); + + alpha = IterationInfo[Iteration - 1].value() - delta; + beta = IterationInfo[Iteration - 1].value() + delta; + if (alpha < - VALUE_INFINITE) alpha = - VALUE_INFINITE; + if (beta > VALUE_INFINITE) beta = VALUE_INFINITE; + + } else { + alpha = - VALUE_INFINITE; + beta = VALUE_INFINITE; + } + // Search to the current depth - ValueByIteration[Iteration] = root_search(p, ss, rml); + Value value = root_search(p, ss, rml, alpha, beta); + if (AbortSearch) + break; //Value cannot be trusted. Break out immediately! + + // Write PV to transposition table, in case the relevant entries have + // been overwritten during the search: + TT.insert_pv(p, ss[0].pv); + + //Save info about search result + Value speculated_value = value; + bool fHigh = false; + bool fLow = false; + + Value prev_value = IterationInfo[Iteration - 1].value(); + Value delta = value - prev_value; + + if (value >= beta) { + fHigh = true; + speculated_value = prev_value + 2 * delta; + BestMoveChangesByIteration[Iteration] += 2; //This is used to tell time management to allocate more time + } else if (value <= alpha) { + fLow = true; + speculated_value = prev_value + 2 * delta; + BestMoveChangesByIteration[Iteration] += 3; //This is used to tell time management to allocate more time + } else { + //nothing + } + + if (speculated_value < - VALUE_INFINITE) speculated_value = - VALUE_INFINITE; + if (speculated_value > VALUE_INFINITE) speculated_value = VALUE_INFINITE; + + IterationInfo[Iteration].set(value, speculated_value, fHigh, fLow); // Erase the easy move if it differs from the new best move if (ss[0].pv[0] != EasyMove) @@ -681,13 +799,13 @@ namespace { // Stop search early when the last two iterations returned a mate score if ( Iteration >= 6 - && abs(ValueByIteration[Iteration]) >= abs(VALUE_MATE) - 100 - && abs(ValueByIteration[Iteration-1]) >= abs(VALUE_MATE) - 100) + && abs(IterationInfo[Iteration].value()) >= abs(VALUE_MATE) - 100 + && abs(IterationInfo[Iteration-1].value()) >= abs(VALUE_MATE) - 100) stopSearch = true; // Stop search early if one move seems to be much better than the rest int64_t nodes = nodes_searched(); - if ( Iteration >= 8 + if ( Iteration >= 8 && !fLow && !fHigh && EasyMove == ss[0].pv[0] && ( ( rml.get_move_cumulative_nodes(0) > (nodes * 85) / 100 && current_search_time() > MaxSearchTime / 16) @@ -700,9 +818,6 @@ namespace { ExtraSearchTime = BestMoveChangesByIteration[Iteration] * (MaxSearchTime / 2) + BestMoveChangesByIteration[Iteration-1] * (MaxSearchTime / 3); - // Try to guess if the current iteration is the last one or the last two - LastIterations = (current_search_time() > ((MaxSearchTime + ExtraSearchTime)*58) / 128); - // Stop search if most of MaxSearchTime is consumed at the end of the // iteration. We probably don't have enough time to search the first // move at the next iteration anyway. @@ -711,15 +826,13 @@ namespace { if (stopSearch) { + //FIXME: Implement fail-low emergency measures if (!PonderSearch) break; else StopOnPonderhit = true; } } - // Write PV to transposition table, in case the relevant entries have - // been overwritten during the search: - TT.insert_pv(p, ss[0].pv); if (MaxDepth && Iteration >= MaxDepth) break; @@ -739,6 +852,11 @@ namespace { << " hashfull " << TT.full() << std::endl; // Print the best move and the ponder move to the standard output + if (ss[0].pv[0] == MOVE_NONE) + { + ss[0].pv[0] = rml.get_move(0); + ss[0].pv[1] = MOVE_NONE; + } std::cout << "bestmove " << ss[0].pv[0]; if (ss[0].pv[1] != MOVE_NONE) std::cout << " ponder " << ss[0].pv[1]; @@ -771,14 +889,22 @@ namespace { // scheme (perhaps we should try to use this at internal PV nodes, too?) // and prints some information to the standard output. - Value root_search(Position &pos, SearchStack ss[], RootMoveList &rml) { + Value root_search(Position &pos, SearchStack ss[], RootMoveList &rml, Value alpha, Value beta) { - Value alpha = -VALUE_INFINITE; - Value beta = VALUE_INFINITE, value; + Value bestValue = -VALUE_INFINITE; + Value oldAlpha = alpha; + Value value; + Bitboard dcCandidates = pos.discovered_check_candidates(pos.side_to_move()); // Loop through all the moves in the root move list for (int i = 0; i < rml.move_count() && !AbortSearch; i++) { + if (alpha >= beta) { //Aspiration window failed high, ignore rest of the moves! + rml.set_move_score(i, -VALUE_INFINITE); + //Leave node-counters and beta-counters as they are. + continue; + } + int64_t nodes; Move move; StateInfo st; @@ -807,16 +933,16 @@ namespace { newDepth = (Iteration - 2) * OnePly + ext + InitialDepth; // Make the move, and search it - pos.do_move(move, st); + pos.do_move(move, st, dcCandidates); if (i < MultiPV) { - value = -search_pv(pos, ss, -beta, VALUE_INFINITE, newDepth, 1, 0); + value = -search_pv(pos, ss, -beta, -alpha, newDepth, 1, 0); // If the value has dropped a lot compared to the last iteration, // set the boolean variable Problem to true. This variable is used // for time managment: When Problem is true, we try to complete the // current iteration before playing a move. - Problem = (Iteration >= 2 && value <= ValueByIteration[Iteration-1] - ProblemMargin); + Problem = (Iteration >= 2 && value <= IterationInfo[Iteration-1].value() - ProblemMargin); if (Problem && StopOnPonderhit) StopOnPonderhit = false; @@ -856,7 +982,7 @@ namespace { assert(value >= -VALUE_INFINITE && value <= VALUE_INFINITE); - if (value <= alpha && i >= MultiPV) + if (value <= bestValue && i >= MultiPV) rml.set_move_score(i, -VALUE_INFINITE); else { @@ -892,11 +1018,16 @@ namespace { LogFile << pretty_pv(pos, current_search_time(), Iteration, nodes_searched(), value, ss[0].pv) << std::endl; - alpha = value; + if (value > bestValue) + { + bestValue = value; + if (value > alpha) + alpha = value; + } // Reset the global variable Problem to false if the value isn't too // far below the final value from the last iteration. - if (value > ValueByIteration[Iteration - 1] - NoProblemMargin) + if (value > IterationInfo[Iteration - 1].value() - NoProblemMargin) Problem = false; } else // MultiPV > 1 @@ -919,10 +1050,17 @@ namespace { std::cout << std::endl; } alpha = rml.get_move_score(Min(i, MultiPV-1)); + bestValue = alpha; //In MultiPV-mode bestValue and alpha are always same thing. } } + + if (bestValue <= oldAlpha) + FailLow = true; + else + FailLow = false; + } - return alpha; + return bestValue; } @@ -941,7 +1079,7 @@ namespace { // Initialize, and make an early exit in case of an aborted search, // an instant draw, maximum ply reached, etc. - init_node(pos, ss, ply, threadID); + init_node(ss, ply, threadID); // After init_node() that calls poll() if (AbortSearch || thread_should_stop(threadID)) @@ -981,6 +1119,7 @@ namespace { Move move, movesSearched[256]; int moveCount = 0; Value value, bestValue = -VALUE_INFINITE; + Bitboard dcCandidates = mp.discovered_check_candidates(); Color us = pos.side_to_move(); bool isCheck = pos.is_check(); bool mateThreat = pos.has_mate_threat(opposite_color(us)); @@ -994,17 +1133,11 @@ namespace { assert(move_is_ok(move)); bool singleReply = (isCheck && mp.number_of_moves() == 1); - bool moveIsCheck = pos.move_is_check(move); + bool moveIsCheck = pos.move_is_check(move, dcCandidates); bool moveIsCapture = pos.move_is_capture(move); movesSearched[moveCount++] = ss[ply].currentMove = move; - if (moveIsCapture) - ss[ply].currentMoveCaptureValue = - move_is_ep(move)? PawnValueMidgame : pos.midgame_value_of_piece_on(move_to(move)); - else - ss[ply].currentMoveCaptureValue = Value(0); - // Decide the new search depth bool dangerous; Depth ext = extension(pos, move, true, moveIsCapture, moveIsCheck, singleReply, mateThreat, &dangerous); @@ -1012,7 +1145,7 @@ namespace { // Make and search the move StateInfo st; - pos.do_move(move, st); + pos.do_move(move, st, dcCandidates); if (moveCount == 1) // The first move in list is the PV value = -search_pv(pos, ss, -beta, -alpha, newDepth, ply+1, threadID); @@ -1074,7 +1207,7 @@ namespace { // (from the computer's point of view) since the previous iteration: if ( ply == 1 && Iteration >= 2 - && -value <= ValueByIteration[Iteration-1] - ProblemMargin) + && -value <= IterationInfo[Iteration-1].value() - ProblemMargin) Problem = true; } @@ -1087,7 +1220,7 @@ namespace { && !AbortSearch && !thread_should_stop(threadID) && split(pos, ss, ply, &alpha, &beta, &bestValue, depth, - &moveCount, &mp, threadID, true)) + &moveCount, &mp, dcCandidates, threadID, true)) break; } @@ -1136,7 +1269,7 @@ namespace { // Initialize, and make an early exit in case of an aborted search, // an instant draw, maximum ply reached, etc. - init_node(pos, ss, ply, threadID); + init_node(ss, ply, threadID); // After init_node() that calls poll() if (AbortSearch || thread_should_stop(threadID)) @@ -1169,7 +1302,6 @@ namespace { Value approximateEval = quick_evaluate(pos); bool mateThreat = false; - bool nullDrivenIID = false; bool isCheck = pos.is_check(); // Null move search @@ -1184,23 +1316,10 @@ namespace { StateInfo st; pos.do_null_move(st); - int R = (depth >= 4 * OnePly ? 4 : 3); // Null move dynamic reduction + int R = (depth >= 5 * OnePly ? 4 : 3); // Null move dynamic reduction Value nullValue = -search(pos, ss, -(beta-1), depth-R*OnePly, ply+1, false, threadID); - // Check for a null capture artifact, if the value without the null capture - // is above beta then mark the node as a suspicious failed low. We will verify - // later if we are really under threat. - if ( UseNullDrivenIID - && nullValue < beta - && depth > 6 * OnePly - &&!value_is_mate(nullValue) - && ttMove == MOVE_NONE - && ss[ply + 1].currentMove != MOVE_NONE - && pos.move_is_capture(ss[ply + 1].currentMove) - && pos.see(ss[ply + 1].currentMove) + nullValue >= beta) - nullDrivenIID = true; - pos.undo_null_move(); if (value_is_mate(nullValue)) @@ -1224,10 +1343,8 @@ namespace { // 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; - nullDrivenIID = false; - } + ss[ply].threatMove = ss[ply + 1].currentMove; if ( depth < ThreatDepth && ss[ply - 1].reduction @@ -1245,8 +1362,8 @@ namespace { { Value v = qsearch(pos, ss, beta-1, beta, Depth(0), ply, threadID); if ( (v < beta - RazorMargin - RazorMargin / 4) - || (depth < 3*OnePly && v < beta - RazorMargin) - || (depth < 2*OnePly && v < beta - RazorMargin / 2)) + || (depth <= 2*OnePly && v < beta - RazorMargin) + || (depth <= OnePly && v < beta - RazorMargin / 2)) return v; } @@ -1257,22 +1374,6 @@ namespace { search(pos, ss, beta, Min(depth/2, depth-2*OnePly), ply, false, threadID); ttMove = ss[ply].pv[ply]; } - else if (nullDrivenIID) - { - // The null move failed low due to a suspicious capture. Perhaps we - // are facing a null capture artifact due to the side to move change - // and this position should fail high. So do a normal search with a - // reduced depth to get a good ttMove to use in the following full - // depth search. - Move tm = ss[ply].threatMove; - - assert(tm != MOVE_NONE); - assert(ttMove == MOVE_NONE); - - search(pos, ss, beta, depth/2, ply, false, threadID); - ttMove = ss[ply].pv[ply]; - ss[ply].threatMove = tm; - } // Initialize a MovePicker object for the current position, and prepare // to search all moves: @@ -1281,6 +1382,7 @@ namespace { Move move, movesSearched[256]; int moveCount = 0; Value value, bestValue = -VALUE_INFINITE; + Bitboard dcCandidates = mp.discovered_check_candidates(); Value futilityValue = VALUE_NONE; bool useFutilityPruning = UseFutilityPruning && depth < SelectiveDepth @@ -1295,7 +1397,7 @@ namespace { assert(move_is_ok(move)); bool singleReply = (isCheck && mp.number_of_moves() == 1); - bool moveIsCheck = pos.move_is_check(move); + bool moveIsCheck = pos.move_is_check(move, dcCandidates); bool moveIsCapture = pos.move_is_capture(move); movesSearched[moveCount++] = ss[ply].currentMove = move; @@ -1335,7 +1437,7 @@ namespace { // Make and search the move StateInfo st; - pos.do_move(move, st); + pos.do_move(move, st, dcCandidates); // Try to reduce non-pv search depth by one ply if move seems not problematic, // if the move fails high will be re-searched at full depth. @@ -1382,7 +1484,7 @@ namespace { && !AbortSearch && !thread_should_stop(threadID) && split(pos, ss, ply, &beta, &beta, &bestValue, depth, &moveCount, - &mp, threadID, false)) + &mp, dcCandidates, threadID, false)) break; } @@ -1409,6 +1511,9 @@ namespace { } TT.store(pos, value_to_tt(bestValue, ply), depth, m, VALUE_TYPE_LOWER); } + + assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); + return bestValue; } @@ -1428,7 +1533,7 @@ namespace { // Initialize, and make an early exit in case of an aborted search, // an instant draw, maximum ply reached, etc. - init_node(pos, ss, ply, threadID); + init_node(ss, ply, threadID); // After init_node() that calls poll() if (AbortSearch || thread_should_stop(threadID)) @@ -1437,15 +1542,39 @@ namespace { if (pos.is_draw()) return VALUE_DRAW; - // Transposition table lookup - const TTEntry* tte = TT.retrieve(pos); - if (tte && ok_to_use_TT(tte, depth, beta, ply)) - return value_from_tt(tte->value(), ply); + // Transposition table lookup, only when not in PV + TTEntry* tte = NULL; + bool pvNode = (beta - alpha != 1); + if (!pvNode) + { + tte = TT.retrieve(pos); + if (tte && ok_to_use_TT(tte, depth, beta, ply)) + { + assert(tte->type() != VALUE_TYPE_EVAL); + + return value_from_tt(tte->value(), ply); + } + } // Evaluate the position statically EvalInfo ei; + Value staticValue; bool isCheck = pos.is_check(); - Value staticValue = (isCheck ? -VALUE_INFINITE : evaluate(pos, ei, threadID)); + ei.futilityMargin = Value(0); // Manually initialize futilityMargin + + if (isCheck) + staticValue = -VALUE_INFINITE; + + else if (tte && tte->type() == VALUE_TYPE_EVAL) + { + // Use the cached evaluation score if possible + assert(tte->value() == evaluate(pos, ei, threadID)); + assert(ei.futilityMargin == Value(0)); + + staticValue = tte->value(); + } + else + staticValue = evaluate(pos, ei, threadID); if (ply == PLY_MAX - 1) return evaluate(pos, ei, threadID); @@ -1455,7 +1584,13 @@ namespace { Value bestValue = staticValue; if (bestValue >= beta) + { + // Store the score to avoid a future costly evaluation() call + if (!isCheck && !tte && ei.futilityMargin == 0) + TT.store(pos, value_to_tt(bestValue, ply), Depth(-127*OnePly), MOVE_NONE, VALUE_TYPE_EVAL); + return bestValue; + } if (bestValue > alpha) alpha = bestValue; @@ -1463,10 +1598,10 @@ namespace { // Initialize a MovePicker object for the current position, and prepare // to search the moves. Because the depth is <= 0 here, only captures, // queen promotions and checks (only if depth == 0) will be generated. - bool pvNode = (beta - alpha != 1); - MovePicker mp = MovePicker(pos, pvNode, MOVE_NONE, EmptySearchStack, depth, isCheck ? NULL : &ei); + MovePicker mp = MovePicker(pos, pvNode, MOVE_NONE, EmptySearchStack, depth); Move move; int moveCount = 0; + Bitboard dcCandidates = mp.discovered_check_candidates(); Color us = pos.side_to_move(); bool enoughMaterial = pos.non_pawn_material(us) > RookValueMidgame; @@ -1486,7 +1621,7 @@ namespace { && !isCheck && !pvNode && !move_promotion(move) - && !pos.move_is_check(move) + && !pos.move_is_check(move, dcCandidates) && !pos.move_is_passed_pawn_push(move)) { Value futilityValue = staticValue @@ -1514,7 +1649,7 @@ namespace { // Make and search the move. StateInfo st; - pos.do_move(move, st); + pos.do_move(move, st, dcCandidates); Value value = -qsearch(pos, ss, -beta, -alpha, depth-OnePly, ply+1, threadID); pos.undo_move(move); @@ -1540,7 +1675,14 @@ namespace { assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); // Update transposition table - TT.store(pos, value_to_tt(bestValue, ply), depth, MOVE_NONE, VALUE_TYPE_EXACT); + if (!pvNode) + { + Depth d = (depth == Depth(0) ? Depth(0) : Depth(-1)); + if (bestValue < beta) + TT.store(pos, value_to_tt(bestValue, ply), d, MOVE_NONE, VALUE_TYPE_UPPER); + else + TT.store(pos, value_to_tt(bestValue, ply), d, MOVE_NONE, VALUE_TYPE_LOWER); + } // Update killers only for good check moves Move m = ss[ply].currentMove; @@ -1581,7 +1723,7 @@ namespace { { assert(move_is_ok(move)); - bool moveIsCheck = pos.move_is_check(move); + bool moveIsCheck = pos.move_is_check(move, sp->dcCandidates); bool moveIsCapture = pos.move_is_capture(move); lock_grab(&(sp->lock)); @@ -1606,7 +1748,7 @@ namespace { // Make and search the move. StateInfo st; - pos.do_move(move, st); + pos.do_move(move, st, sp->dcCandidates); // Try to reduce non-pv search depth by one ply if move seems not problematic, // if the move fails high will be re-searched at full depth. @@ -1691,17 +1833,11 @@ namespace { && !thread_should_stop(threadID) && (move = sp->mp->get_next_move(sp->lock)) != MOVE_NONE) { - bool moveIsCheck = pos.move_is_check(move); + bool moveIsCheck = pos.move_is_check(move, sp->dcCandidates); bool moveIsCapture = pos.move_is_capture(move); assert(move_is_ok(move)); - if (moveIsCapture) - ss[sp->ply].currentMoveCaptureValue = - move_is_ep(move)? PawnValueMidgame : pos.midgame_value_of_piece_on(move_to(move)); - else - ss[sp->ply].currentMoveCaptureValue = Value(0); - lock_grab(&(sp->lock)); int moveCount = ++sp->moves; lock_release(&(sp->lock)); @@ -1715,7 +1851,7 @@ namespace { // Make and search the move. StateInfo st; - pos.do_move(move, st); + pos.do_move(move, st, sp->dcCandidates); // Try to reduce non-pv search depth by one ply if move seems not problematic, // if the move fails high will be re-searched at full depth. @@ -1784,7 +1920,7 @@ namespace { // (from the computer's point of view) since the previous iteration. if ( sp->ply == 1 && Iteration >= 2 - && -value <= ValueByIteration[Iteration-1] - ProblemMargin) + && -value <= IterationInfo[Iteration-1].value() - ProblemMargin) Problem = true; } lock_release(&(sp->lock)); @@ -1986,41 +2122,13 @@ namespace { } - // init_search_stack() initializes a search stack at the beginning of a - // new search from the root. - void init_search_stack(SearchStack& ss) { - - ss.pv[0] = MOVE_NONE; - ss.pv[1] = MOVE_NONE; - ss.currentMove = MOVE_NONE; - ss.threatMove = MOVE_NONE; - ss.reduction = Depth(0); - for (int j = 0; j < KILLER_MAX; j++) - ss.killers[j] = MOVE_NONE; - } - - void init_search_stack(SearchStack ss[]) { - - for (int i = 0; i < 3; i++) - { - ss[i].pv[i] = MOVE_NONE; - ss[i].pv[i+1] = MOVE_NONE; - ss[i].currentMove = MOVE_NONE; - ss[i].threatMove = MOVE_NONE; - ss[i].reduction = Depth(0); - for (int j = 0; j < KILLER_MAX; j++) - ss[i].killers[j] = MOVE_NONE; - } - } - - // init_node() is called at the beginning of all the search functions // (search(), search_pv(), qsearch(), and so on) and initializes the search // stack object corresponding to the current node. Once every // NodesBetweenPolls nodes, init_node() also calls poll(), which polls // for user input and checks whether it is time to stop the search. - void init_node(const Position &pos, SearchStack ss[], int ply, int threadID) { + void init_node(SearchStack ss[], int ply, int threadID) { assert(ply >= 0 && ply < PLY_MAX); assert(threadID >= 0 && threadID < ActiveThreads); @@ -2033,13 +2141,9 @@ namespace { NodesSincePoll = 0; } } - ss[ply].pv[ply] = ss[ply].pv[ply+1] = ss[ply].currentMove = MOVE_NONE; - ss[ply+2].mateKiller = MOVE_NONE; - ss[ply].threatMove = MOVE_NONE; - ss[ply].reduction = Depth(0); - ss[ply].currentMoveCaptureValue = Value(0); - for (int j = 0; j < KILLER_MAX; j++) - ss[ply+2].killers[j] = MOVE_NONE; + + ss[ply].init(ply); + ss[ply+2].initKillers(); if(Threads[threadID].printCurrentLine) print_current_line(ss, ply, threadID); @@ -2445,11 +2549,11 @@ namespace { return; bool overTime = t > AbsoluteMaxSearchTime - || (RootMoveNumber == 1 && t > MaxSearchTime + ExtraSearchTime) - || ( !FailHigh && !fail_high_ply_1() && !Problem + || (RootMoveNumber == 1 && t > MaxSearchTime + ExtraSearchTime && !FailLow) //FIXME: BUG?? + || ( !FailHigh && !FailLow && !fail_high_ply_1() && !Problem && t > 6*(MaxSearchTime + ExtraSearchTime)); - if ( (Iteration >= 2 && (!InfiniteSearch && overTime)) + if ( (Iteration >= 3 && (!InfiniteSearch && overTime)) || (ExactMaxTime && t >= ExactMaxTime) || (Iteration >= 3 && MaxNodes && nodes_searched() >= MaxNodes)) AbortSearch = true; @@ -2463,12 +2567,12 @@ namespace { void ponderhit() { int t = current_search_time(); PonderSearch = false; - if(Iteration >= 2 && + if(Iteration >= 3 && (!InfiniteSearch && (StopOnPonderhit || t > AbsoluteMaxSearchTime || (RootMoveNumber == 1 && - t > MaxSearchTime + ExtraSearchTime) || - (!FailHigh && !fail_high_ply_1() && !Problem && + t > MaxSearchTime + ExtraSearchTime && !FailLow) || + (!FailHigh && !FailLow && !fail_high_ply_1() && !Problem && t > 6*(MaxSearchTime + ExtraSearchTime))))) AbortSearch = true; } @@ -2671,8 +2775,9 @@ namespace { // splitPoint->cpus becomes 0), split() returns true. bool split(const Position &p, SearchStack *sstck, int ply, - Value *alpha, Value *beta, Value *bestValue, - Depth depth, int *moves, MovePicker *mp, int master, bool pvNode) { + Value *alpha, Value *beta, Value *bestValue, Depth depth, int *moves, + MovePicker *mp, Bitboard dcCandidates, int master, bool pvNode) { + assert(p.is_ok()); assert(sstck != NULL); assert(ply >= 0 && ply < PLY_MAX); @@ -2708,6 +2813,7 @@ namespace { splitPoint->alpha = pvNode? *alpha : (*beta - 1); splitPoint->beta = *beta; splitPoint->pvNode = pvNode; + splitPoint->dcCandidates = dcCandidates; splitPoint->bestValue = *bestValue; splitPoint->master = master; splitPoint->mp = mp;