X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=37c3bd71bb40e2aab91f4e45751684b0e86d7ebb;hp=95aa76c4e14732ef2db6340a7fa26a28753777b1;hb=b4870595a5652f7a5ecf577e33d0302b725b7f51;hpb=b075d8ca53f860c36bc33d66f301a15e4675cdbd diff --git a/src/search.cpp b/src/search.cpp index 95aa76c4..37c3bd71 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -52,7 +52,7 @@ using std::endl; namespace { /// Types - + enum NodeType { NonPV, PV }; // ThreadsManager class is used to handle all the threads related stuff in search, // init, starting, parking and, the most important, launching a slave thread at a @@ -215,11 +215,10 @@ namespace { // Step 14. Reduced search // Reduction lookup tables (initialized at startup) and their getter functions - int8_t PVReductionMatrix[64][64]; // [depth][moveNumber] - int8_t NonPVReductionMatrix[64][64]; // [depth][moveNumber] + int8_t ReductionMatrix[2][64][64]; // [pv][depth][moveNumber] - inline Depth pv_reduction(Depth d, int mn) { return (Depth) PVReductionMatrix[Min(d / 2, 63)][Min(mn, 63)]; } - inline Depth nonpv_reduction(Depth d, int mn) { return (Depth) NonPVReductionMatrix[Min(d / 2, 63)][Min(mn, 63)]; } + template + inline Depth reduction(Depth d, int mn) { return (Depth) ReductionMatrix[PV][Min(d / 2, 63)][Min(mn, 63)]; } // Common adjustments @@ -280,9 +279,12 @@ namespace { Value id_loop(const Position& pos, Move searchMoves[]); Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value* alphaPtr, Value* betaPtr); - template + template Value search(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, bool allowNullmove, int threadID, Move excludedMove = MOVE_NONE); + template + Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck, bool singleEvasion, bool mateThreat, bool* dangerous); + Value qsearch(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID); void sp_search(SplitPoint* sp, int threadID); void sp_search_pv(SplitPoint* sp, int threadID); @@ -292,7 +294,6 @@ namespace { 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&, Move, bool, bool, bool, bool, bool, bool*); bool ok_to_do_nullmove(const Position& pos); bool ok_to_prune(const Position& pos, Move m, Move threat); bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply); @@ -552,8 +553,8 @@ void init_search() { { double pvRed = log(double(i)) * log(double(j)) / 3.0; double nonPVRed = log(double(i)) * log(double(j)) / 1.5; - PVReductionMatrix[i][j] = (int8_t) ( pvRed >= 1.0 ? floor( pvRed * int(OnePly)) : 0); - NonPVReductionMatrix[i][j] = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed * int(OnePly)) : 0); + ReductionMatrix[PV][i][j] = (int8_t) ( pvRed >= 1.0 ? floor( pvRed * int(OnePly)) : 0); + ReductionMatrix[NonPV][i][j] = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed * int(OnePly)) : 0); } // Init futility margins array @@ -845,7 +846,7 @@ namespace { // Step 11. Decide the new search depth depth = (Iteration - 2) * OnePly + InitialDepth; - ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, false, false, &dangerous); + ext = extension(pos, move, captureOrPromotion, moveIsCheck, false, false, &dangerous); newDepth = depth + ext; // Step 12. Futility pruning (omitted at root) @@ -870,7 +871,7 @@ namespace { alpha = -VALUE_INFINITE; // Full depth PV search, done on first move or after a fail high - value = -search(pos, ss, -beta, -alpha, newDepth, 1, false, 0); + value = -search(pos, ss, -beta, -alpha, newDepth, 1, false, 0); } else { @@ -883,11 +884,11 @@ namespace { && !captureOrPromotion && !move_is_castle(move)) { - ss[0].reduction = pv_reduction(depth, i - MultiPV + 2); + ss[0].reduction = reduction(depth, i - MultiPV + 2); if (ss[0].reduction) { // Reduced depth non-pv search using alpha as upperbound - value = -search(pos, ss, -(alpha+1), -alpha, newDepth-ss[0].reduction, 1, true, 0); + value = -search(pos, ss, -(alpha+1), -alpha, newDepth-ss[0].reduction, 1, true, 0); doFullDepthSearch = (value > alpha); } } @@ -897,12 +898,12 @@ namespace { { // Full depth non-pv search using alpha as upperbound ss[0].reduction = Depth(0); - value = -search(pos, ss, -(alpha+1), -alpha, newDepth, 1, true, 0); + value = -search(pos, ss, -(alpha+1), -alpha, newDepth, 1, true, 0); // If we are above alpha then research at same depth but as PV // to get a correct score or eventually a fail high above beta. if (value > alpha) - value = -search(pos, ss, -beta, -alpha, newDepth, 1, false, 0); + value = -search(pos, ss, -beta, -alpha, newDepth, 1, false, 0); } } @@ -1024,11 +1025,10 @@ namespace { // search_pv() is the main search function for PV nodes. - template + template Value search(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, bool allowNullmove, int threadID, Move excludedMove) { - assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE); assert(beta > alpha && beta <= VALUE_INFINITE); assert(ply >= 0 && ply < PLY_MAX); @@ -1161,7 +1161,7 @@ namespace { pos.do_null_move(st); - nullValue = -search(pos, ss, -beta, -alpha, depth-R*OnePly, ply+1, false, threadID); + nullValue = -search(pos, ss, -beta, -alpha, depth-R*OnePly, ply+1, false, threadID); pos.undo_null_move(); @@ -1175,7 +1175,7 @@ namespace { return nullValue; // Do zugzwang verification search - Value v = search(pos, ss, alpha, beta, depth-5*OnePly, ply, false, threadID); + Value v = search(pos, ss, alpha, beta, depth-5*OnePly, ply, false, threadID); if (v >= beta) return nullValue; } else { @@ -1202,7 +1202,7 @@ namespace { && depth >= IIDDepthAtPVNodes && ttMove == MOVE_NONE) { - search(pos, ss, alpha, beta, depth-2*OnePly, ply, false, threadID); + search(pos, ss, alpha, beta, depth-2*OnePly, ply, false, threadID); ttMove = ss[ply].pv[ply]; tte = TT.retrieve(posKey); } @@ -1213,7 +1213,7 @@ namespace { && !isCheck && ss[ply].eval >= beta - IIDMargin) { - search(pos, ss, alpha, beta, depth/2, ply, false, threadID); + search(pos, ss, alpha, beta, depth/2, ply, false, threadID); ttMove = ss[ply].pv[ply]; tte = TT.retrieve(posKey); } @@ -1242,7 +1242,7 @@ namespace { captureOrPromotion = pos.move_is_capture_or_promotion(move); // Step 11. Decide the new search depth - ext = extension(pos, move, PvNode, captureOrPromotion, moveIsCheck, singleEvasion, mateThreat, &dangerous); + ext = extension(pos, move, captureOrPromotion, moveIsCheck, singleEvasion, mateThreat, &dangerous); // Singular extension search. We extend the TT move if its value is much better than // its siblings. To verify this we do a reduced search on all the other moves but the @@ -1259,7 +1259,7 @@ namespace { if (abs(ttValue) < VALUE_KNOWN_WIN) { - Value excValue = search(pos, ss, ttValue - SingularExtensionMargin - 1, ttValue - SingularExtensionMargin, depth / 2, ply, false, threadID, move); + Value excValue = search(pos, ss, ttValue - SingularExtensionMargin - 1, ttValue - SingularExtensionMargin, depth / 2, ply, false, threadID, move); if (excValue < ttValue - SingularExtensionMargin) ext = OnePly; @@ -1286,7 +1286,7 @@ namespace { continue; // Value based pruning - Depth predictedDepth = newDepth - nonpv_reduction(depth, moveCount); // We illogically ignore reduction condition depth >= 3*OnePly + Depth predictedDepth = newDepth - reduction(depth, moveCount); // We illogically ignore reduction condition depth >= 3*OnePly futilityValueScaled = ss[ply].eval + futility_margin(predictedDepth, moveCount) + H.gain(pos.piece_on(move_from(move)), move_to(move)); @@ -1304,7 +1304,7 @@ namespace { // Step extra. pv search (only in PV nodes) // The first move in list is the expected PV if (PvNode && moveCount == 1) - value = -search(pos, ss, -beta, -alpha, newDepth, ply+1, false, threadID); + value = -search(pos, ss, -beta, -alpha, newDepth, ply+1, false, threadID); else { // Step 14. Reduced search @@ -1317,10 +1317,10 @@ namespace { && !move_is_castle(move) && !move_is_killer(move, ss[ply])) { - ss[ply].reduction = (PvNode ? pv_reduction(depth, moveCount) : nonpv_reduction(depth, moveCount)); + ss[ply].reduction = reduction(depth, moveCount); if (ss[ply].reduction) { - value = -search(pos, ss, -(alpha+1), -alpha, newDepth-ss[ply].reduction, ply+1, true, threadID); + value = -search(pos, ss, -(alpha+1), -alpha, newDepth-ss[ply].reduction, ply+1, true, threadID); doFullDepthSearch = (value > alpha); } } @@ -1329,11 +1329,11 @@ namespace { if (doFullDepthSearch) { ss[ply].reduction = Depth(0); - value = -search(pos, ss, -(alpha+1), -alpha, newDepth, ply+1, true, threadID); + value = -search(pos, ss, -(alpha+1), -alpha, newDepth, ply+1, true, threadID); // Step extra. pv search (only in PV nodes) if (PvNode && value > alpha && value < beta) - value = -search(pos, ss, -beta, -alpha, newDepth, ply+1, false, threadID); + value = -search(pos, ss, -beta, -alpha, newDepth, ply+1, false, threadID); } } @@ -1637,7 +1637,7 @@ namespace { captureOrPromotion = pos.move_is_capture_or_promotion(move); // Step 11. Decide the new search depth - ext = extension(pos, move, false, captureOrPromotion, moveIsCheck, false, sp->mateThreat, &dangerous); + ext = extension(pos, move, captureOrPromotion, moveIsCheck, false, sp->mateThreat, &dangerous); newDepth = sp->depth - OnePly + ext; // Update current move @@ -1659,7 +1659,7 @@ namespace { } // Value based pruning - Depth predictedDepth = newDepth - nonpv_reduction(sp->depth, moveCount); + Depth predictedDepth = newDepth - reduction(sp->depth, moveCount); futilityValueScaled = ss[sp->ply].eval + futility_margin(predictedDepth, moveCount) + H.gain(pos.piece_on(move_from(move)), move_to(move)); @@ -1685,10 +1685,10 @@ namespace { && !move_is_castle(move) && !move_is_killer(move, ss[sp->ply])) { - ss[sp->ply].reduction = nonpv_reduction(sp->depth, moveCount); + ss[sp->ply].reduction = reduction(sp->depth, moveCount); if (ss[sp->ply].reduction) { - value = -search(pos, ss, -(sp->alpha+1), -(sp->alpha), newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID); + value = -search(pos, ss, -(sp->alpha+1), -(sp->alpha), newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID); doFullDepthSearch = (value >= sp->beta && !TM.thread_should_stop(threadID)); } } @@ -1697,7 +1697,7 @@ namespace { if (doFullDepthSearch) { ss[sp->ply].reduction = Depth(0); - value = -search(pos, ss, -(sp->alpha+1), -(sp->alpha), newDepth, sp->ply+1, true, threadID); + value = -search(pos, ss, -(sp->alpha+1), -(sp->alpha), newDepth, sp->ply+1, true, threadID); } // Step 16. Undo move @@ -1770,7 +1770,7 @@ namespace { captureOrPromotion = pos.move_is_capture_or_promotion(move); // Step 11. Decide the new search depth - ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, false, sp->mateThreat, &dangerous); + ext = extension(pos, move, captureOrPromotion, moveIsCheck, false, sp->mateThreat, &dangerous); newDepth = sp->depth - OnePly + ext; // Update current move @@ -1790,11 +1790,11 @@ namespace { && !move_is_castle(move) && !move_is_killer(move, ss[sp->ply])) { - ss[sp->ply].reduction = pv_reduction(sp->depth, moveCount); + ss[sp->ply].reduction = reduction(sp->depth, moveCount); if (ss[sp->ply].reduction) { Value localAlpha = sp->alpha; - value = -search(pos, ss, -(localAlpha+1), -localAlpha, newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID); + value = -search(pos, ss, -(localAlpha+1), -localAlpha, newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID); doFullDepthSearch = (value > localAlpha && !TM.thread_should_stop(threadID)); } } @@ -1804,7 +1804,7 @@ namespace { { Value localAlpha = sp->alpha; ss[sp->ply].reduction = Depth(0); - value = -search(pos, ss, -(localAlpha+1), -localAlpha, newDepth, sp->ply+1, true, threadID); + value = -search(pos, ss, -(localAlpha+1), -localAlpha, newDepth, sp->ply+1, true, threadID); if (value > localAlpha && value < sp->beta && !TM.thread_should_stop(threadID)) { @@ -1812,7 +1812,7 @@ namespace { // to be higher or equal then beta, if so, avoid to start a PV search. localAlpha = sp->alpha; if (localAlpha < sp->beta) - value = -search(pos, ss, -sp->beta, -localAlpha, newDepth, sp->ply+1, false, threadID); + value = -search(pos, ss, -sp->beta, -localAlpha, newDepth, sp->ply+1, false, threadID); } } @@ -2004,9 +2004,9 @@ namespace { // 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 captureOrPromotion, - bool moveIsCheck, bool singleEvasion, bool mateThreat, bool* dangerous) { + template + Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck, + bool singleEvasion, bool mateThreat, bool* dangerous) { assert(m != MOVE_NONE); @@ -2016,13 +2016,13 @@ namespace { if (*dangerous) { if (moveIsCheck) - result += CheckExtension[pvNode]; + result += CheckExtension[PvNode]; if (singleEvasion) - result += SingleEvasionExtension[pvNode]; + result += SingleEvasionExtension[PvNode]; if (mateThreat) - result += MateThreatExtension[pvNode]; + result += MateThreatExtension[PvNode]; } if (pos.type_of_piece_on(move_from(m)) == PAWN) @@ -2030,12 +2030,12 @@ namespace { Color c = pos.side_to_move(); if (relative_rank(c, move_to(m)) == RANK_7) { - result += PawnPushTo7thExtension[pvNode]; + result += PawnPushTo7thExtension[PvNode]; *dangerous = true; } if (pos.pawn_is_passed(c, move_to(m))) { - result += PassedPawnExtension[pvNode]; + result += PassedPawnExtension[PvNode]; *dangerous = true; } } @@ -2047,11 +2047,11 @@ namespace { && !move_is_promotion(m) && !move_is_ep(m)) { - result += PawnEndgameExtension[pvNode]; + result += PawnEndgameExtension[PvNode]; *dangerous = true; } - if ( pvNode + if ( PvNode && captureOrPromotion && pos.type_of_piece_on(move_to(m)) != PAWN && pos.see_sign(m) >= 0)