X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=3617853e5f23d2f3589b7af48da9decbf48e4593;hp=3f4ad24ca17652319456568ef0169d1ab1ecd7e4;hb=5a0581498cde3d0904924d8ef7ed25ea1a2c855a;hpb=18677852315b960132b0e8daa220c83b1c3c17cd diff --git a/src/search.cpp b/src/search.cpp index 3f4ad24c..3617853e 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -47,6 +47,23 @@ namespace { /// Types + // 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 + // to the number of beta cutoffs occurred under their subtree during + // the last iteration. + + struct BetaCounterType { + + BetaCounterType(); + void clear(); + void add(Color us, Depth d, int threadID); + void read(Color us, int64_t& our, int64_t& their); + + int64_t hits[THREAD_MAX][2]; + }; + + // The RootMove class is used for moves at the root at the tree. For each // root move, we store a score, a node count, and a PV (really a refutation // in the case of moves which fail low). @@ -60,6 +77,7 @@ namespace { Value score; int64_t nodes, cumulativeNodes; Move pv[PLY_MAX_PLUS_2]; + int64_t ourBeta, theirBeta; }; @@ -74,6 +92,7 @@ namespace { inline Value get_move_score(int moveNum) const; inline void set_move_score(int moveNum, Value score); inline void set_move_nodes(int moveNum, int64_t nodes); + inline void set_beta_counters(int moveNum, int64_t our, int64_t their); void set_move_pv(int moveNum, const Move pv[]); inline Move get_move_pv(int moveNum, int i) const; inline int64_t get_move_cumulative_nodes(int moveNum) const; @@ -102,6 +121,9 @@ namespace { // Depth limit for selective search: Depth SelectiveDepth = 7*OnePly; + // Use dynamic LMR? + const bool UseDynamicLMR = false; + // Use internal iterative deepening? const bool UseIIDAtPVNodes = true; const bool UseIIDAtNonPVNodes = false; @@ -111,9 +133,6 @@ namespace { // when the static evaluation is at most IIDMargin below beta. const Value IIDMargin = Value(0x100); - // Use easy moves? - const bool UseEasyMove = true; - // Easy move margin. An easy move candidate must be at least this much // better than the second best move. const Value EasyMoveMargin = Value(0x200); @@ -143,13 +162,14 @@ namespace { bool UseQSearchFutilityPruning = true; bool UseFutilityPruning = true; - // Margins for futility pruning in the quiescence search, at frontier - // nodes, and at pre-frontier nodes - Value FutilityMargin0 = Value(0x80); - Value FutilityMargin1 = Value(0x100); - Value FutilityMargin2 = Value(0x300); + // Margins for futility pruning in the quiescence search, and at frontier + // and near frontier nodes + Value FutilityMarginQS = Value(0x80); + Value FutilityMargins[6] = { Value(0x100), Value(0x200), Value(0x250), + Value(0x2A0), Value(0x340), Value(0x3A0) }; // Razoring + const bool RazorAtDepthOne = false; Depth RazorDepth = 4*OnePly; Value RazorMargin = Value(0x300); @@ -174,9 +194,9 @@ namespace { int NodesSincePoll; int NodesBetweenPolls = 30000; - // Iteration counter + // 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]; @@ -188,8 +208,8 @@ namespace { // Time managment variables int SearchStartTime; int MaxNodes, MaxDepth; - int MaxSearchTime, AbsoluteMaxSearchTime, ExtraSearchTime, TimeAdvantage; - Move BestRootMove, PonderMove, EasyMove; + int MaxSearchTime, AbsoluteMaxSearchTime, ExtraSearchTime; + Move EasyMove; int RootMoveNumber; bool InfiniteSearch; bool PonderSearch; @@ -238,14 +258,13 @@ 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 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); + bool value_is_mate(Value value); bool move_is_killer(Move m, const SearchStack& ss); - Depth extension(const Position &pos, Move m, bool pvNode, bool check, bool singleReply, bool mateThreat); + Depth extension(const Position &pos, Move m, bool pvNode, bool capture, bool check, bool singleReply, bool mateThreat, bool* dangerous); bool ok_to_do_nullmove(const Position &pos); bool ok_to_prune(const Position &pos, Move m, Move threat, Depth d); bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply); @@ -268,9 +287,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, Bitboard dcCandidates, 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) @@ -303,6 +321,24 @@ 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); + currentMoveCaptureValue = Value(0); +} + +void SearchStack::initKillers() { + + mateKiller = MOVE_NONE; + for (int i = 0; i < KILLER_MAX; i++) + killers[i] = MOVE_NONE; +} + + //// //// Functions //// @@ -335,8 +371,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++) { @@ -393,9 +427,10 @@ void think(const Position &pos, bool infinite, bool ponder, int side_to_move, UseQSearchFutilityPruning = get_option_value_bool("Futility Pruning (Quiescence Search)"); UseFutilityPruning = get_option_value_bool("Futility Pruning (Main Search)"); - FutilityMargin0 = value_from_centipawns(get_option_value_int("Futility Margin 0")); - FutilityMargin1 = value_from_centipawns(get_option_value_int("Futility Margin 1")); - FutilityMargin2 = value_from_centipawns(get_option_value_int("Futility Margin 2")); + FutilityMarginQS = value_from_centipawns(get_option_value_int("Futility Margin (Quiescence Search)")); + int fmScale = get_option_value_int("Futility Margin Scale Factor (Main Search)"); + for (int i = 0; i < 6; i++) + FutilityMargins[i] = (FutilityMargins[i] * fmScale) / 100; RazorDepth = (get_option_value_int("Maximum Razoring Depth") + 1) * OnePly; RazorMargin = value_from_centipawns(get_option_value_int("Razoring Margin")); @@ -425,9 +460,6 @@ void think(const Position &pos, bool infinite, bool ponder, int side_to_move, // Set thinking time: int myTime = time[side_to_move]; int myIncrement = increment[side_to_move]; - int oppTime = time[1 - side_to_move]; - - TimeAdvantage = myTime - oppTime; if (!movesToGo) // Sudden death time control { @@ -436,7 +468,7 @@ void think(const Position &pos, bool infinite, bool ponder, int side_to_move, MaxSearchTime = myTime / 30 + myIncrement; AbsoluteMaxSearchTime = Max(myTime / 4, myIncrement - 100); } else { // Blitz game without increment - MaxSearchTime = myTime / 40; + MaxSearchTime = myTime / 30; AbsoluteMaxSearchTime = myTime / 8; } } @@ -568,7 +600,8 @@ void init_threads() { } // Init also the empty search stack - init_search_stack(EmptySearchStack); + EmptySearchStack.init(0); + EmptySearchStack.initKillers(); } @@ -620,12 +653,14 @@ namespace { // Initialize TT.new_search(); H.clear(); - init_search_stack(ss); - + for (int i = 0; i < 3; i++) + { + ss[i].init(i); + ss[i].initKillers(); + } ValueByIteration[0] = Value(0); ValueByIteration[1] = rml.get_move_score(0); Iteration = 1; - LastIterations = false; EasyMove = rml.scan_for_easy_move(); @@ -680,13 +715,6 @@ namespace { ExtraSearchTime = BestMoveChangesByIteration[Iteration] * (MaxSearchTime / 2) + BestMoveChangesByIteration[Iteration-1] * (MaxSearchTime / 3); - // If we need some more and we are in time advantage take it - if (ExtraSearchTime > 0 && TimeAdvantage > 2 * MaxSearchTime) - ExtraSearchTime += MaxSearchTime / 2; - - // 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. @@ -723,6 +751,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]; @@ -731,12 +764,18 @@ namespace { if (UseLogFile) { - UndoInfo u; + if (dbg_show_mean) + dbg_print_mean(LogFile); + + if (dbg_show_hit_rate) + dbg_print_hit_rate(LogFile); + + StateInfo st; LogFile << "Nodes: " << nodes_searched() << std::endl << "Nodes/second: " << nps() << std::endl << "Best move: " << move_to_san(p, ss[0].pv[0]) << std::endl; - p.do_move(ss[0].pv[0], u); + p.do_move(ss[0].pv[0], st); LogFile << "Ponder move: " << move_to_san(p, ss[0].pv[1]) << std::endl << std::endl; } @@ -760,7 +799,7 @@ namespace { { int64_t nodes; Move move; - UndoInfo u; + StateInfo st; Depth ext, newDepth; RootMoveNumber = i + 1; @@ -770,6 +809,9 @@ namespace { // are used to sort the root moves at the next iteration. nodes = nodes_searched(); + // Reset beta cut-off counters + BetaCounter.clear(); + // Pick the next root move, and print the move and the move number to // the standard output. move = ss[0].currentMove = rml.get_move(i); @@ -778,11 +820,12 @@ namespace { << " currmovenumber " << i + 1 << std::endl; // Decide search depth for this move - ext = extension(pos, move, true, pos.move_is_check(move), false, false); + bool dangerous; + ext = extension(pos, move, true, pos.move_is_capture(move), pos.move_is_check(move), false, false, &dangerous); newDepth = (Iteration - 2) * OnePly + ext + InitialDepth; // Make the move, and search it - pos.do_move(move, u, dcCandidates); + pos.do_move(move, st, dcCandidates); if (i < MultiPV) { @@ -810,7 +853,7 @@ namespace { } } - pos.undo_move(move, u); + pos.undo_move(move); // Finished searching the move. If AbortSearch is true, the search // was aborted because the user interrupted the search or because we @@ -824,6 +867,11 @@ namespace { // sort the root moves at the next iteration. rml.set_move_nodes(i, nodes_searched() - nodes); + // Remember the beta-cutoff statistics + int64_t our, their; + BetaCounter.read(pos.side_to_move(), our, their); + rml.set_beta_counters(i, our, their); + assert(value >= -VALUE_INFINITE && value <= VALUE_INFINITE); if (value <= alpha && i >= MultiPV) @@ -906,16 +954,17 @@ namespace { assert(ply >= 0 && ply < PLY_MAX); assert(threadID >= 0 && threadID < ActiveThreads); - // Initialize, and make an early exit in case of an aborted search, - // an instant draw, maximum ply reached, etc. - if (AbortSearch || thread_should_stop(threadID)) - return Value(0); - if (depth < OnePly) return qsearch(pos, ss, alpha, beta, Depth(0), ply, threadID); + // 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); + // After init_node() that calls poll() + if (AbortSearch || thread_should_stop(threadID)) + return Value(0); + if (pos.is_draw()) return VALUE_DRAW; @@ -951,9 +1000,9 @@ namespace { 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 = MateThreatExtension[1] > Depth(0) - && pos.has_mate_threat(opposite_color(pos.side_to_move())); + bool mateThreat = pos.has_mate_threat(opposite_color(us)); // Loop through all legal moves until no moves remain or a beta cutoff // occurs. @@ -966,24 +1015,23 @@ namespace { bool singleReply = (isCheck && mp.number_of_moves() == 1); bool moveIsCheck = pos.move_is_check(move, dcCandidates); bool moveIsCapture = pos.move_is_capture(move); - bool moveIsPassedPawnPush = pos.move_is_passed_pawn_push(move); movesSearched[moveCount++] = ss[ply].currentMove = move; if (moveIsCapture) - ss[ply].currentMoveCaptureValue = pos.midgame_value_of_piece_on(move_to(move)); - else if (move_is_ep(move)) - ss[ply].currentMoveCaptureValue = PawnValueMidgame; + 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 - Depth ext = extension(pos, move, true, moveIsCheck, singleReply, mateThreat); + bool dangerous; + Depth ext = extension(pos, move, true, moveIsCapture, moveIsCheck, singleReply, mateThreat, &dangerous); Depth newDepth = depth - OnePly + ext; // Make and search the move - UndoInfo u; - pos.do_move(move, u, dcCandidates); + StateInfo 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); @@ -992,11 +1040,10 @@ namespace { // 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. if ( depth >= 2*OnePly - && ext == Depth(0) && moveCount >= LMRPVMoves + && !dangerous && !moveIsCapture && !move_promotion(move) - && !moveIsPassedPawnPush && !move_is_castle(move) && !move_is_killer(move, ss[ply])) { @@ -1006,7 +1053,7 @@ namespace { else value = alpha + 1; // Just to trigger next condition - if (value > alpha) // Go with full depth pv search + if (value > alpha) // Go with full depth non-pv search { ss[ply].reduction = Depth(0); value = -search(pos, ss, -alpha, newDepth, ply+1, true, threadID); @@ -1026,7 +1073,7 @@ namespace { } } } - pos.undo_move(move, u); + pos.undo_move(move); assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); @@ -1044,7 +1091,9 @@ namespace { // If we are at ply 1, and we are searching the first root move at // ply 0, set the 'Problem' variable if the score has dropped a lot // (from the computer's point of view) since the previous iteration: - if (Iteration >= 2 && -value <= ValueByIteration[Iteration-1] - ProblemMargin) + if ( ply == 1 + && Iteration >= 2 + && -value <= ValueByIteration[Iteration-1] - ProblemMargin) Problem = true; } @@ -1076,6 +1125,7 @@ namespace { else if (bestValue >= beta) { + BetaCounter.add(pos.side_to_move(), depth, threadID); Move m = ss[ply].pv[ply]; if (ok_to_history(pos, m)) // Only non capture moves are considered { @@ -1100,21 +1150,22 @@ namespace { assert(ply >= 0 && ply < PLY_MAX); assert(threadID >= 0 && threadID < ActiveThreads); - EvalInfo ei; + if (depth < OnePly) + return qsearch(pos, ss, beta-1, beta, Depth(0), ply, threadID); // 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); + + // After init_node() that calls poll() if (AbortSearch || thread_should_stop(threadID)) return Value(0); - if (depth < OnePly) - return qsearch(pos, ss, beta-1, beta, Depth(0), ply, threadID); - - init_node(pos, ss, ply, threadID); - if (pos.is_draw()) return VALUE_DRAW; + EvalInfo ei; + if (ply >= PLY_MAX - 1) return evaluate(pos, ei, threadID); @@ -1131,7 +1182,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); } @@ -1141,19 +1192,27 @@ namespace { // Null move search if ( allowNullmove + && depth > OnePly && !isCheck + && !value_is_mate(beta) && ok_to_do_nullmove(pos) && approximateEval >= beta - NullMoveMargin) { ss[ply].currentMove = MOVE_NULL; - UndoInfo u; - pos.do_null_move(u); - int R = (depth > 7 ? 4 : 3); + StateInfo st; + pos.do_null_move(st); + int R = (depth >= 4 * OnePly ? 4 : 3); // Null move dynamic reduction + Value nullValue = -search(pos, ss, -(beta-1), depth-R*OnePly, ply+1, false, threadID); - pos.undo_null_move(u); - if (nullValue >= beta) + pos.undo_null_move(); + + if (value_is_mate(nullValue)) + { + /* Do not return unproven mates */ + } + else if (nullValue >= beta) { if (depth < 6 * OnePly) return beta; @@ -1164,9 +1223,9 @@ namespace { return beta; } else { // The null move failed low, which means that we may be faced with - // some kind of threat. If the previous move was reduced, check if + // some kind of threat. If the previous move was reduced, check if // the move that refuted the null move was somehow connected to the - // move which was reduced. If a connection is found, return a fail + // 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)) @@ -1180,11 +1239,17 @@ namespace { } } // Null move search not allowed, try razoring - else if ( (approximateEval < beta - RazorMargin && depth < RazorDepth) - ||(approximateEval < beta - PawnValueMidgame && depth <= OnePly)) + else if ( !value_is_mate(beta) + && approximateEval < beta - RazorMargin + && depth < RazorDepth + && (RazorAtDepthOne || depth > OnePly) + && ttMove == MOVE_NONE + && !pos.has_pawn_on_7th(pos.side_to_move())) { Value v = qsearch(pos, ss, beta-1, beta, Depth(0), ply, threadID); - if (v < beta) + if ( (v < beta - RazorMargin - RazorMargin / 4) + || (depth <= 2*OnePly && v < beta - RazorMargin) + || (depth <= OnePly && v < beta - RazorMargin / 2)) return v; } @@ -1220,30 +1285,32 @@ namespace { bool singleReply = (isCheck && mp.number_of_moves() == 1); bool moveIsCheck = pos.move_is_check(move, dcCandidates); bool moveIsCapture = pos.move_is_capture(move); - bool moveIsPassedPawnPush = pos.move_is_passed_pawn_push(move); movesSearched[moveCount++] = ss[ply].currentMove = move; // Decide the new search depth - Depth ext = extension(pos, move, false, moveIsCheck, singleReply, mateThreat); + bool dangerous; + Depth ext = extension(pos, move, false, moveIsCapture, moveIsCheck, singleReply, mateThreat, &dangerous); Depth newDepth = depth - OnePly + ext; // Futility pruning if ( useFutilityPruning - && ext == Depth(0) + && !dangerous && !moveIsCapture - && !moveIsPassedPawnPush && !move_promotion(move)) { + // History pruning. See ok_to_prune() definition if ( moveCount >= 2 + int(depth) && ok_to_prune(pos, move, ss[ply].threatMove, depth)) continue; - if (depth < 3 * OnePly && approximateEval < beta) + // Value based pruning + if (depth < 7 * OnePly && approximateEval < beta) { if (futilityValue == VALUE_NONE) futilityValue = evaluate(pos, ei, threadID) - + (depth < 2 * OnePly ? FutilityMargin1 : FutilityMargin2); + + FutilityMargins[int(depth)/2 - 1] + + 32 * (depth & 1); if (futilityValue < beta) { @@ -1255,22 +1322,26 @@ namespace { } // Make and search the move - UndoInfo u; - pos.do_move(move, u, dcCandidates); + StateInfo 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. - if ( depth >= 2*OnePly - && ext == Depth(0) - && moveCount >= LMRNonPVMoves + if ( depth >= 2*OnePly + && moveCount >= LMRNonPVMoves + && !dangerous && !moveIsCapture && !move_promotion(move) - && !moveIsPassedPawnPush && !move_is_castle(move) && !move_is_killer(move, ss[ply])) { - ss[ply].reduction = OnePly; - value = -search(pos, ss, -(beta-1), newDepth-OnePly, ply+1, true, threadID); + // LMR dynamic reduction + Depth R = UseDynamicLMR + && moveCount >= 2 * LMRNonPVMoves + && depth > 7*OnePly ? 2*OnePly : OnePly; + + ss[ply].reduction = R; + value = -search(pos, ss, -(beta-1), newDepth-R, ply+1, true, threadID); } else value = beta; // Just to trigger next condition @@ -1280,7 +1351,7 @@ namespace { ss[ply].reduction = Depth(0); value = -search(pos, ss, -(beta-1), newDepth, ply+1, true, threadID); } - pos.undo_move(move, u); + pos.undo_move(move); assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); @@ -1322,6 +1393,7 @@ namespace { TT.store(pos, value_to_tt(bestValue, ply), depth, MOVE_NONE, VALUE_TYPE_UPPER); else { + BetaCounter.add(pos.side_to_move(), depth, threadID); Move m = ss[ply].pv[ply]; if (ok_to_history(pos, m)) // Only non capture moves are considered { @@ -1330,6 +1402,9 @@ namespace { } TT.store(pos, value_to_tt(bestValue, ply), depth, m, VALUE_TYPE_LOWER); } + + assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); + return bestValue; } @@ -1347,35 +1422,69 @@ namespace { assert(ply >= 0 && ply < PLY_MAX); assert(threadID >= 0 && threadID < ActiveThreads); - EvalInfo ei; - // 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); + + // After init_node() that calls poll() if (AbortSearch || thread_should_stop(threadID)) return Value(0); - init_node(pos, ss, ply, threadID); - 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 - Value staticValue = evaluate(pos, ei, threadID); + EvalInfo ei; + Value staticValue; + bool isCheck = pos.is_check(); + + 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(); + ei.futilityMargin = Value(0); // manually initialize futilityMargin + } + else + staticValue = evaluate(pos, ei, threadID); if (ply == PLY_MAX - 1) - return staticValue; + return evaluate(pos, ei, threadID); // Initialize "stand pat score", and return it immediately if it is // at least beta. - Value bestValue = (pos.is_check() ? -VALUE_INFINITE : staticValue); + Value bestValue = staticValue; if (bestValue >= beta) + { + // Update transposition table before to leave + TT.store(pos, value_to_tt(bestValue, ply), depth, MOVE_NONE, VALUE_TYPE_EXACT); return bestValue; + } + else if (!isCheck && !tte && ei.futilityMargin == 0) + { + // Store the score to avoid a future costly evaluation() call + TT.store(pos, value_to_tt(bestValue, ply), Depth(-127*OnePly), MOVE_NONE, VALUE_TYPE_EVAL); + } if (bestValue > alpha) alpha = bestValue; @@ -1383,13 +1492,12 @@ 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. - MovePicker mp = MovePicker(pos, false, MOVE_NONE, EmptySearchStack, depth, &ei); + MovePicker mp = MovePicker(pos, pvNode, MOVE_NONE, EmptySearchStack, depth); Move move; int moveCount = 0; Bitboard dcCandidates = mp.discovered_check_candidates(); - bool isCheck = pos.is_check(); - bool pvNode = (beta - alpha != 1); - bool enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMidgame; + Color us = pos.side_to_move(); + bool enoughMaterial = pos.non_pawn_material(us) > RookValueMidgame; // Loop through the moves until no moves remain or a beta cutoff // occurs. @@ -1398,25 +1506,23 @@ namespace { { assert(move_is_ok(move)); - bool moveIsCheck = pos.move_is_check(move, dcCandidates); - bool moveIsPassedPawnPush = pos.move_is_passed_pawn_push(move); - moveCount++; ss[ply].currentMove = move; // Futility pruning if ( UseQSearchFutilityPruning + && enoughMaterial && !isCheck - && !moveIsCheck - && !move_promotion(move) - && !moveIsPassedPawnPush && !pvNode - && enoughMaterial) + && !move_promotion(move) + && !pos.move_is_check(move, dcCandidates) + && !pos.move_is_passed_pawn_push(move)) { Value futilityValue = staticValue + Max(pos.midgame_value_of_piece_on(move_to(move)), pos.endgame_value_of_piece_on(move_to(move))) - + FutilityMargin0 + + (move_is_ep(move) ? PawnValueEndgame : Value(0)) + + FutilityMarginQS + ei.futilityMargin; if (futilityValue < alpha) @@ -1436,10 +1542,10 @@ namespace { continue; // Make and search the move. - UndoInfo u; - pos.do_move(move, u, dcCandidates); + StateInfo st; + pos.do_move(move, st, dcCandidates); Value value = -qsearch(pos, ss, -beta, -alpha, depth-OnePly, ply+1, threadID); - pos.undo_move(move, u); + pos.undo_move(move); assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); @@ -1462,9 +1568,6 @@ 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); - // Update killers only for good check moves Move m = ss[ply].currentMove; if (alpha >= beta && ok_to_history(pos, m)) // Only non capture moves are considered @@ -1506,7 +1609,6 @@ namespace { bool moveIsCheck = pos.move_is_check(move, sp->dcCandidates); bool moveIsCapture = pos.move_is_capture(move); - bool moveIsPassedPawnPush = pos.move_is_passed_pawn_push(move); lock_grab(&(sp->lock)); int moveCount = ++sp->moves; @@ -1515,29 +1617,28 @@ namespace { ss[sp->ply].currentMove = move; // Decide the new search depth. - Depth ext = extension(pos, move, false, moveIsCheck, false, false); + bool dangerous; + Depth ext = extension(pos, move, false, moveIsCapture, moveIsCheck, false, false, &dangerous); Depth newDepth = sp->depth - OnePly + ext; // Prune? if ( useFutilityPruning - && ext == Depth(0) + && !dangerous && !moveIsCapture - && !moveIsPassedPawnPush && !move_promotion(move) && moveCount >= 2 + int(sp->depth) && ok_to_prune(pos, move, ss[sp->ply].threatMove, sp->depth)) continue; // Make and search the move. - UndoInfo u; - pos.do_move(move, u, sp->dcCandidates); + StateInfo 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. - if ( ext == Depth(0) + if ( !dangerous && moveCount >= LMRNonPVMoves && !moveIsCapture - && !moveIsPassedPawnPush && !move_promotion(move) && !move_is_castle(move) && !move_is_killer(move, ss[sp->ply])) @@ -1553,7 +1654,7 @@ namespace { ss[sp->ply].reduction = Depth(0); value = -search(pos, ss, -(sp->beta - 1), newDepth, sp->ply+1, true, threadID); } - pos.undo_move(move, u); + pos.undo_move(move); assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); @@ -1618,12 +1719,14 @@ namespace { { bool moveIsCheck = pos.move_is_check(move, sp->dcCandidates); bool moveIsCapture = pos.move_is_capture(move); - bool moveIsPassedPawnPush = pos.move_is_passed_pawn_push(move); assert(move_is_ok(move)); - ss[sp->ply].currentMoveCaptureValue = move_is_ep(move)? - PawnValueMidgame : pos.midgame_value_of_piece_on(move_to(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; @@ -1632,19 +1735,19 @@ namespace { ss[sp->ply].currentMove = move; // Decide the new search depth. - Depth ext = extension(pos, move, true, moveIsCheck, false, false); + bool dangerous; + Depth ext = extension(pos, move, true, moveIsCapture, moveIsCheck, false, false, &dangerous); Depth newDepth = sp->depth - OnePly + ext; // Make and search the move. - UndoInfo u; - pos.do_move(move, u, sp->dcCandidates); + StateInfo 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. - if ( ext == Depth(0) + if ( !dangerous && moveCount >= LMRPVMoves && !moveIsCapture - && !moveIsPassedPawnPush && !move_promotion(move) && !move_is_castle(move) && !move_is_killer(move, ss[sp->ply])) @@ -1674,7 +1777,7 @@ namespace { Threads[threadID].failHighPly1 = false; } } - pos.undo_move(move, u); + pos.undo_move(move); assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); @@ -1704,8 +1807,10 @@ namespace { } // If we are at ply 1, and we are searching the first root move at // ply 0, set the 'Problem' variable if the score has dropped a lot - // (from the computer's point of view) since the previous iteration: - if (Iteration >= 2 && -value <= ValueByIteration[Iteration-1] - ProblemMargin) + // (from the computer's point of view) since the previous iteration. + if ( sp->ply == 1 + && Iteration >= 2 + && -value <= ValueByIteration[Iteration-1] - ProblemMargin) Problem = true; } lock_release(&(sp->lock)); @@ -1714,7 +1819,7 @@ namespace { lock_grab(&(sp->lock)); // If this is the master thread and we have been asked to stop because of - // a beta cutoff higher up in the tree, stop all slave threads: + // a beta cutoff higher up in the tree, stop all slave threads. if (sp->master == threadID && thread_should_stop(threadID)) for (int i = 0; i < ActiveThreads; i++) if (sp->slaves[i]) @@ -1726,6 +1831,32 @@ namespace { lock_release(&(sp->lock)); } + /// The BetaCounterType class + + BetaCounterType::BetaCounterType() { clear(); } + + void BetaCounterType::clear() { + + for (int i = 0; i < THREAD_MAX; i++) + hits[i][WHITE] = hits[i][BLACK] = 0ULL; + } + + void BetaCounterType::add(Color us, Depth d, int threadID) { + + // Weighted count based on depth + hits[threadID][us] += int(d); + } + + void BetaCounterType::read(Color us, int64_t& our, int64_t& their) { + + our = their = 0UL; + for (int i = 0; i < THREAD_MAX; i++) + { + our += hits[i][us]; + their += hits[i][opposite_color(us)]; + } + } + /// The RootMove class @@ -1745,7 +1876,7 @@ namespace { if (score != m.score) return (score < m.score); - return nodes <= m.nodes; + return theirBeta <= m.theirBeta; } /// The RootMoveList class @@ -1771,15 +1902,15 @@ namespace { if (includeMove) { // Find a quick score for the move - UndoInfo u; + StateInfo st; SearchStack ss[PLY_MAX_PLUS_2]; moves[count].move = mlist[i].move; moves[count].nodes = 0ULL; - pos.do_move(moves[count].move, u); + pos.do_move(moves[count].move, st); moves[count].score = -qsearch(pos, ss, -VALUE_INFINITE, VALUE_INFINITE, Depth(0), 1, 0); - pos.undo_move(moves[count].move, u); + pos.undo_move(moves[count].move); moves[count].pv[0] = moves[i].move; moves[count].pv[1] = MOVE_NONE; // FIXME count++; @@ -1808,6 +1939,11 @@ namespace { moves[moveNum].cumulativeNodes += nodes; } + inline void RootMoveList::set_beta_counters(int moveNum, int64_t our, int64_t their) { + moves[moveNum].ourBeta = our; + moves[moveNum].theirBeta = their; + } + void RootMoveList::set_move_pv(int moveNum, const Move pv[]) { int j; for(j = 0; pv[j] != MOVE_NONE; j++) @@ -1876,34 +2012,6 @@ 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 @@ -1924,13 +2032,8 @@ namespace { } } - 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); @@ -2001,7 +2104,7 @@ namespace { // Case 4: The destination square for m2 is attacked by the moving piece // in m1: - if(pos.piece_attacks_square(t1, t2)) + if(pos.piece_attacks_square(pos.piece_on(t1), t1, t2)) return true; // Case 5: Discovered check, checking piece is the piece moved in m1: @@ -2033,6 +2136,18 @@ namespace { } + // value_is_mate() checks if the given value is a mate one + // eventually compensated for the ply. + + bool value_is_mate(Value value) { + + assert(abs(value) <= VALUE_INFINITE); + + return value <= value_mated_in(PLY_MAX) + || value >= value_mate_in(PLY_MAX); + } + + // move_is_killer() checks if the given move is among the // killer moves of that ply. @@ -2049,12 +2164,18 @@ namespace { // extension() decides whether a move should be searched with normal depth, // or with extended depth. Certain classes of moves (checking moves, in - // particular) are searched with bigger depth than ordinary moves. + // particular) are searched with bigger depth than ordinary moves and in + // any case are marked as 'dangerous'. Note that also if a move is not + // extended, as example because the corresponding UCI option is set to zero, + // the move is marked as 'dangerous' so, at least, we avoid to prune it. - Depth extension(const Position &pos, Move m, bool pvNode, - bool check, bool singleReply, bool mateThreat) { + Depth extension(const Position& pos, Move m, bool pvNode, bool capture, bool check, + bool singleReply, bool mateThreat, bool* dangerous) { + + assert(m != MOVE_NONE); Depth result = Depth(0); + *dangerous = check || singleReply || mateThreat; if (check) result += CheckExtension[pvNode]; @@ -2062,26 +2183,42 @@ namespace { if (singleReply) result += SingleReplyExtension[pvNode]; - if (pos.move_is_pawn_push_to_7th(m)) - result += PawnPushTo7thExtension[pvNode]; - - if (pos.move_is_passed_pawn_push(m)) - result += PassedPawnExtension[pvNode]; - if (mateThreat) result += MateThreatExtension[pvNode]; - if ( pos.midgame_value_of_piece_on(move_to(m)) >= RookValueMidgame + if (pos.type_of_piece_on(move_from(m)) == PAWN) + { + if (pos.move_is_pawn_push_to_7th(m)) + { + result += PawnPushTo7thExtension[pvNode]; + *dangerous = true; + } + if (pos.move_is_passed_pawn_push(m)) + { + result += PassedPawnExtension[pvNode]; + *dangerous = true; + } + } + + if ( capture + && pos.type_of_piece_on(move_to(m)) != PAWN && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK) - pos.midgame_value_of_piece_on(move_to(m)) == Value(0)) - && !move_promotion(m)) + && !move_promotion(m) + && !move_is_ep(m)) + { result += PawnEndgameExtension[pvNode]; + *dangerous = true; + } if ( pvNode - && pos.move_is_capture(m) + && capture && pos.type_of_piece_on(move_to(m)) != PAWN && pos.see(m) >= 0) + { result += OnePly/2; + *dangerous = true; + } return Min(result, OnePly); } @@ -2123,31 +2260,35 @@ namespace { tto = move_to(threat); // Case 1: Castling moves are never pruned. - if(move_is_castle(m)) - return false; + if (move_is_castle(m)) + return false; // Case 2: Don't prune moves which move the threatened piece - if(!PruneEscapeMoves && threat != MOVE_NONE && mfrom == tto) - return false; + if (!PruneEscapeMoves && threat != MOVE_NONE && mfrom == tto) + return false; // Case 3: If the threatened piece has value less than or equal to the // value of the threatening piece, don't prune move which defend it. - if(!PruneDefendingMoves && threat != MOVE_NONE - && (piece_value_midgame(pos.piece_on(tfrom)) - >= piece_value_midgame(pos.piece_on(tto))) - && pos.move_attacks_square(m, tto)) + if ( !PruneDefendingMoves + && threat != MOVE_NONE + && pos.move_is_capture(threat) + && ( pos.midgame_value_of_piece_on(tfrom) >= pos.midgame_value_of_piece_on(tto) + || pos.type_of_piece_on(tfrom) == KING) + && pos.move_attacks_square(m, tto)) return false; // Case 4: Don't prune moves with good history. - if(!H.ok_to_prune(pos.piece_on(move_from(m)), m, d)) - return false; + if (!H.ok_to_prune(pos.piece_on(move_from(m)), m, d)) + return false; // Case 5: If the moving piece in the threatened move is a slider, don't // prune safe moves which block its ray. - if(!PruneBlockingMoves && threat != MOVE_NONE - && piece_is_slider(pos.piece_on(tfrom)) - && bit_is_set(squares_between(tfrom, tto), mto) && pos.see(m) >= 0) - return false; + if ( !PruneBlockingMoves + && threat != MOVE_NONE + && piece_is_slider(pos.piece_on(tfrom)) + && bit_is_set(squares_between(tfrom, tto), mto) + && pos.see(m) >= 0) + return false; return true; } @@ -2302,7 +2443,7 @@ namespace { || ( !FailHigh && !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; @@ -2316,7 +2457,7 @@ namespace { void ponderhit() { int t = current_search_time(); PonderSearch = false; - if(Iteration >= 2 && + if(Iteration >= 3 && (!InfiniteSearch && (StopOnPonderhit || t > AbsoluteMaxSearchTime || (RootMoveNumber == 1 && @@ -2524,9 +2665,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, + 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);