X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=6ade1b433494664a2af2f482e60ff8cc25717aa3;hp=94eb6155bf756bfc8f938b43cbd038947bd9ff75;hb=cff8877a1ae270d6f176d16dbcfd72a270e0600f;hpb=4b232f5ddc7d8a05b7e6e3267bcb7a4119ffdc25 diff --git a/src/search.cpp b/src/search.cpp index 94eb6155..6ade1b43 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -47,7 +47,7 @@ namespace { const bool FakeSplit = false; // Different node types, used as template parameter - enum NodeType { NonPV, PV }; + enum NodeType { Root, PV, NonPV, SplitPointPV, SplitPointNonPV }; // RootMove struct is used for moves at the root of the tree. For each root // move, we store two scores, a node count, and a PV (really a refutation @@ -96,7 +96,7 @@ namespace { // MovePickerExt template class extends MovePicker and allows to choose at compile // time the proper moves source according to the type of node. In the default case // we simply create and use a standard MovePicker object. - template struct MovePickerExt : public MovePicker { + template struct MovePickerExt : public MovePicker { MovePickerExt(const Position& p, Move ttm, Depth d, const History& h, SearchStack* ss, Value b) : MovePicker(p, ttm, d, h, ss, b) {} @@ -105,19 +105,23 @@ namespace { }; // In case of a SpNode we use split point's shared MovePicker object as moves source - template<> struct MovePickerExt : public MovePicker { + template<> struct MovePickerExt : public MovePickerExt { MovePickerExt(const Position& p, Move ttm, Depth d, const History& h, SearchStack* ss, Value b) - : MovePicker(p, ttm, d, h, ss, b), mp(ss->sp->mp) {} + : MovePickerExt(p, ttm, d, h, ss, b), mp(ss->sp->mp) {} Move get_next_move() { return mp->get_next_move(); } - - RootMoveList::iterator rm; // Dummy, needed to compile MovePicker* mp; }; + template<> struct MovePickerExt : public MovePickerExt { + + MovePickerExt(const Position& p, Move ttm, Depth d, const History& h, SearchStack* ss, Value b) + : MovePickerExt(p, ttm, d, h, ss, b) {} + }; + // In case of a Root node we use RootMoveList as moves source - template<> struct MovePickerExt : public MovePicker { + template<> struct MovePickerExt : public MovePicker { MovePickerExt(const Position&, Move, Depth, const History&, SearchStack*, Value); Move get_next_move(); @@ -189,9 +193,9 @@ namespace { // Reduction lookup tables (initialized at startup) and their access function int8_t Reductions[2][64][64]; // [pv][depth][moveNumber] - template inline Depth reduction(Depth d, int mn) { + template inline Depth reduction(Depth d, int mn) { - return (Depth) Reductions[PV][Min(d / ONE_PLY, 63)][Min(mn, 63)]; + return (Depth) Reductions[PvNode][Min(d / ONE_PLY, 63)][Min(mn, 63)]; } // Easy move margin. An easy move candidate must be at least this much @@ -233,20 +237,13 @@ namespace { Move id_loop(Position& pos, Move searchMoves[], Move* ponderMove); - template + template Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth); - template + template 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) { - - return depth < ONE_PLY ? qsearch(pos, ss, alpha, beta, DEPTH_ZERO) - : search(pos, ss, alpha, beta, depth); - } - - template + template 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); @@ -304,8 +301,8 @@ void init_search() { { double pvRed = log(double(hd)) * log(double(mc)) / 3.0; double nonPVRed = 0.33 + log(double(hd)) * log(double(mc)) / 2.25; - Reductions[PV][hd][mc] = (int8_t) ( pvRed >= 1.0 ? floor( pvRed * int(ONE_PLY)) : 0); - Reductions[NonPV][hd][mc] = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed * int(ONE_PLY)) : 0); + Reductions[1][hd][mc] = (int8_t) ( pvRed >= 1.0 ? floor( pvRed * int(ONE_PLY)) : 0); + Reductions[0][hd][mc] = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed * int(ONE_PLY)) : 0); } // Init futility margins array @@ -541,7 +538,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); + 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. @@ -663,9 +660,13 @@ namespace { // all this work again. We also don't need to store anything to the hash table // here: This is taken care of after we return from the split point. - template + template Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth) { + const bool PvNode = (NT == PV || NT == Root || NT == SplitPointPV); + const bool SpNode = (NT == SplitPointPV || NT == SplitPointNonPV); + const bool RootNode = (NT == Root); + assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE); assert(beta > alpha && beta <= VALUE_INFINITE); assert(PvNode || alpha == beta - 1); @@ -703,13 +704,13 @@ namespace { threatMove = sp->threatMove; goto split_point_start; } - else if (Root) + else if (RootNode) bestValue = alpha; // Step 1. Initialize node and poll. Polling can abort search ss->currentMove = ss->bestMove = threatMove = (ss+1)->excludedMove = MOVE_NONE; (ss+1)->skipNullMove = false; (ss+1)->reduction = DEPTH_ZERO; - (ss+2)->killers[0] = (ss+2)->killers[1] = (ss+2)->mateKiller = MOVE_NONE; + (ss+2)->killers[0] = (ss+2)->killers[1] = MOVE_NONE; if (threadID == 0 && ++NodesSincePoll > NodesBetweenPolls) { @@ -721,7 +722,7 @@ namespace { if (( StopRequest || Threads[threadID].cutoff_occurred() || pos.is_draw() - || ss->ply > PLY_MAX) && !Root) + || ss->ply > PLY_MAX) && !RootNode) return VALUE_DRAW; // Step 3. Mate distance pruning @@ -742,7 +743,7 @@ namespace { // At PV nodes we check for exact scores, while at non-PV nodes we check for // a fail high/low. Biggest advantage at probing at PV nodes is to have a // smooth experience in analysis mode. - if ( !Root + if ( !RootNode && tte && (PvNode ? tte->depth() >= depth && tte->type() == VALUE_TYPE_EXACT : ok_to_use_TT(tte, depth, beta, ss->ply))) @@ -821,7 +822,8 @@ namespace { pos.do_null_move(st); (ss+1)->skipNullMove = true; - nullValue = -search(pos, ss+1, -beta, -alpha, depth-R*ONE_PLY); + nullValue = depth-R*ONE_PLY < ONE_PLY ? -qsearch(pos, ss+1, -beta, -alpha, DEPTH_ZERO) + : - search(pos, ss+1, -beta, -alpha, depth-R*ONE_PLY); (ss+1)->skipNullMove = false; pos.undo_null_move(); @@ -868,7 +870,7 @@ namespace { Depth d = (PvNode ? depth - 2 * ONE_PLY : depth / 2); ss->skipNullMove = true; - search(pos, ss, alpha, beta, d); + search(pos, ss, alpha, beta, d); ss->skipNullMove = false; tte = TT.probe(posKey); @@ -878,12 +880,12 @@ namespace { split_point_start: // At split points actual search starts from here // Initialize a MovePicker object for the current position - MovePickerExt mp(pos, ttMove, depth, H, ss, (PvNode ? -VALUE_INFINITE : beta)); + MovePickerExt mp(pos, ttMove, depth, H, ss, PvNode ? -VALUE_INFINITE : beta); CheckInfo ci(pos); Bitboard pinned = pos.pinned_pieces(pos.side_to_move()); ss->bestMove = MOVE_NONE; futilityBase = ss->eval + ss->evalMargin; - singularExtensionNode = !Root + singularExtensionNode = !RootNode && !SpNode && depth >= SingularExtensionDepth[PvNode] && ttMove != MOVE_NONE @@ -897,24 +899,29 @@ split_point_start: // At split points actual search starts from here } // Step 10. Loop through moves - // Loop through all legal moves until no moves remain or a beta cutoff occurs + // Loop through all pseudo-legal moves until no moves remain or a beta cutoff occurs while ( bestValue < beta && (move = mp.get_next_move()) != MOVE_NONE && !Threads[threadID].cutoff_occurred()) { assert(move_is_ok(move)); + if (move == excludedMove) + continue; + + // At PV and SpNode nodes we want the moves to be legal + if ((PvNode || SpNode) && !pos.pl_move_is_legal(move, pinned)) + continue; + if (SpNode) { moveCount = ++sp->moveCount; lock_release(&(sp->lock)); } - else if (move == excludedMove || !pos.pl_move_is_legal(move, pinned)) - continue; else moveCount++; - if (Root) + if (RootNode) { // This is used by time management FirstRootMove = (moveCount == 1); @@ -936,7 +943,7 @@ split_point_start: // At split points actual search starts from here } // At Root and at first iteration do a PV search on all the moves to score root moves - isPvMove = (PvNode && moveCount <= (Root ? depth <= ONE_PLY ? 1000 : MultiPV : 1)); + isPvMove = (PvNode && moveCount <= (RootNode ? depth <= ONE_PLY ? 1000 : MultiPV : 1)); givesCheck = pos.move_gives_check(move, ci); captureOrPromotion = pos.move_is_capture(move) || move_is_promotion(move); @@ -950,6 +957,7 @@ split_point_start: // At split points actual search starts from here // a margin then we extend ttMove. if ( singularExtensionNode && move == ttMove + && pos.pl_move_is_legal(move, pinned) && ext < ONE_PLY) { Value ttValue = value_from_tt(tte->value(), ss->ply); @@ -969,7 +977,6 @@ split_point_start: // At split points actual search starts from here } // Update current move (this must be done after singular extension search) - ss->currentMove = move; newDepth = depth - ONE_PLY + ext; // Step 12. Futility pruning (is omitted in PV nodes) @@ -994,7 +1001,7 @@ split_point_start: // At split points actual search starts from here // Value based pruning // We illogically ignore reduction condition depth >= 3*ONE_PLY for predicted depth, // but fixing this made program slightly weaker. - Depth predictedDepth = newDepth - reduction(depth, moveCount); + Depth predictedDepth = newDepth - reduction(depth, moveCount); futilityValueScaled = futilityBase + futility_margin(predictedDepth, moveCount) + H.gain(pos.piece_on(move_from(move)), move_to(move)); @@ -1024,6 +1031,15 @@ split_point_start: // At split points actual search starts from here } } + // Check for legality only before to do the move + if (!pos.pl_move_is_legal(move, pinned)) + { + moveCount--; + continue; + } + + ss->currentMove = move; + // Step 13. Make the move pos.do_move(move, st, ci, givesCheck); @@ -1035,10 +1051,11 @@ split_point_start: // At split points actual search starts from here if (isPvMove) { // Aspiration window is disabled in multi-pv case - if (Root && MultiPV > 1) + if (RootNode && MultiPV > 1) alpha = -VALUE_INFINITE; - value = -search(pos, ss+1, -beta, -alpha, newDepth); + value = newDepth < ONE_PLY ? -qsearch(pos, ss+1, -beta, -alpha, DEPTH_ZERO) + : - search(pos, ss+1, -beta, -alpha, newDepth); } else { @@ -1058,8 +1075,8 @@ split_point_start: // At split points actual search starts from here if (ss->reduction) { Depth d = newDepth - ss->reduction; - value = -search(pos, ss+1, -(alpha+1), -alpha, d); - + value = d < ONE_PLY ? -qsearch(pos, ss+1, -(alpha+1), -alpha, DEPTH_ZERO) + : - search(pos, ss+1, -(alpha+1), -alpha, d); doFullDepthSearch = (value > alpha); } ss->reduction = DEPTH_ZERO; // Restore original reduction @@ -1078,7 +1095,8 @@ 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); + value = d < ONE_PLY ? -qsearch(pos, ss+1, -(rAlpha+1), -rAlpha, DEPTH_ZERO) + : - search(pos, ss+1, -(rAlpha+1), -rAlpha, d); doFullDepthSearch = (value > rAlpha); ss->reduction = DEPTH_ZERO; // Restore original reduction } @@ -1087,13 +1105,15 @@ 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); + value = newDepth < ONE_PLY ? -qsearch(pos, ss+1, -(alpha+1), -alpha, DEPTH_ZERO) + : - 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); + if (PvNode && value > alpha && (RootNode || value < beta)) + value = newDepth < ONE_PLY ? -qsearch(pos, ss+1, -beta, -alpha, DEPTH_ZERO) + : - search(pos, ss+1, -beta, -alpha, newDepth); } } @@ -1117,7 +1137,7 @@ split_point_start: // At split points actual search starts from here if (SpNode) sp->bestValue = value; - if (!Root && value > alpha) + if (!RootNode && value > alpha) { if (PvNode && value < beta) // We want always alpha < beta { @@ -1129,9 +1149,6 @@ split_point_start: // At split points actual search starts from here else if (SpNode) sp->is_betaCutoff = true; - if (value == value_mate_in(ss->ply + 1)) - ss->mateKiller = move; - ss->bestMove = move; if (SpNode) @@ -1139,7 +1156,7 @@ split_point_start: // At split points actual search starts from here } } - if (Root) + if (RootNode) { // Finished searching the move. If StopRequest is true, the search // was aborted because the user interrupted the search or because we @@ -1178,10 +1195,10 @@ split_point_start: // At split points actual search starts from here else mp.rm->pv_score = -VALUE_INFINITE; - } // Root + } // RootNode // Step 18. Check for split - if ( !Root + if ( !RootNode && !SpNode && depth >= Threads.min_split_depth() && bestValue < beta @@ -1241,9 +1258,12 @@ split_point_start: // At split points actual search starts from here // search function when the remaining depth is zero (or, to be more precise, // less than ONE_PLY). - template + template Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth) { + const bool PvNode = (NT == PV); + + assert(NT == PV || NT == NonPV); assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE); assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE); assert(PvNode || alpha == beta - 1); @@ -1334,9 +1354,6 @@ split_point_start: // At split points actual search starts from here { assert(move_is_ok(move)); - if (!pos.pl_move_is_legal(move, pinned)) - continue; - givesCheck = pos.move_gives_check(move, ci); // Futility pruning @@ -1367,7 +1384,8 @@ split_point_start: // At split points actual search starts from here } // Detect non-capture evasions that are candidate to be pruned - evasionPrunable = inCheck + evasionPrunable = !PvNode + && inCheck && bestValue > VALUE_MATED_IN_PLY_MAX && !pos.move_is_capture(move) && !pos.can_castle(pos.side_to_move()); @@ -1396,12 +1414,16 @@ split_point_start: // At split points actual search starts from here continue; } + // Check for legality only before to do the move + if (!pos.pl_move_is_legal(move, pinned)) + continue; + // Update current move ss->currentMove = move; // Make and search the move pos.do_move(move, st, ci, givesCheck); - value = -qsearch(pos, ss+1, -beta, -alpha, depth-ONE_PLY); + value = -qsearch(pos, ss+1, -beta, -alpha, depth-ONE_PLY); pos.undo_move(move); assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); @@ -1580,7 +1602,7 @@ split_point_start: // At split points actual search starts from here // 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. - template + template Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck, bool* dangerous) { @@ -1988,12 +2010,10 @@ split_point_start: // At split points actual search starts from here pos.do_move(pv[0], *st++); - Bitboard pinned = pos.pinned_pieces(pos.side_to_move()); - while ( (tte = TT.probe(pos.get_key())) != NULL && tte->move() != MOVE_NONE && pos.move_is_pl(tte->move()) - && pos.pl_move_is_legal(tte->move(), pinned) + && pos.pl_move_is_legal(tte->move(), pos.pinned_pieces(pos.side_to_move())) && ply < PLY_MAX && (!pos.is_draw() || ply < 2)) { @@ -2058,9 +2078,9 @@ split_point_start: // At split points actual search starts from here } // Specializations for MovePickerExt in case of Root node - MovePickerExt::MovePickerExt(const Position& p, Move ttm, Depth d, + MovePickerExt::MovePickerExt(const Position& p, Move ttm, Depth d, const History& h, SearchStack* ss, Value b) - : MovePicker(p, ttm, d, h, ss, b), firstCall(true) { + : MovePicker(p, ttm, d, h, ss, b), firstCall(true) { Move move; Value score = VALUE_ZERO; @@ -2080,7 +2100,7 @@ split_point_start: // At split points actual search starts from here rm = Rml.begin(); } - Move MovePickerExt::get_next_move() { + Move MovePickerExt::get_next_move() { if (!firstCall) ++rm; @@ -2164,9 +2184,9 @@ void ThreadsManager::idle_loop(int threadID, SplitPoint* sp) { (ss+1)->sp = tsp; if (tsp->pvNode) - search(pos, ss+1, tsp->alpha, tsp->beta, tsp->depth); + search(pos, ss+1, tsp->alpha, tsp->beta, tsp->depth); else - search(pos, ss+1, tsp->alpha, tsp->beta, tsp->depth); + search(pos, ss+1, tsp->alpha, tsp->beta, tsp->depth); assert(threads[threadID].state == Thread::SEARCHING);