X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=502f12cf72cefa0ff75a38ada3be7f5e37a89787;hp=bc0fff881ef7f003ead9e194d35ab91b887cc207;hb=2e2f1064ba5bec031dbad18c34866de89cbc8276;hpb=6b8026806c80bb894e57d276629b35ed703f8489 diff --git a/src/search.cpp b/src/search.cpp index bc0fff88..502f12cf 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -289,7 +289,6 @@ namespace { /// Local functions Move id_loop(Position& pos, Move searchMoves[], Move* ponderMove); - Value root_search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, RootMoveList& rml); template Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply); @@ -332,7 +331,54 @@ namespace { DWORD WINAPI init_thread(LPVOID threadID); #endif -} + + // A dispatcher to choose among different move sources according to the type of node + template struct MovePickerExt; + + // In Root nodes use RootMoveList Rml as source + template<> struct MovePickerExt { + + MovePickerExt(const Position&, Move, Depth, const History&, SearchStack*, Value) + : rm(Rml->begin()), firstCall(true) {} + + Move get_next_move() { + + if (!firstCall) + ++rm; + else + firstCall = false; + + return rm != Rml->end() ? rm->pv[0] : MOVE_NONE; + } + int number_of_evasions() const { return (int)Rml->size(); } + + RootMoveList::iterator rm; + bool firstCall; + }; + + // In SpNodes use split point's shared MovePicker as move source + template<> struct MovePickerExt { + + MovePickerExt(const Position&, Move, Depth, const History&, SearchStack* ss, Value) + : mp(ss->sp->mp) {} + + Move get_next_move() { return mp->get_next_move(); } + int number_of_evasions() const { return mp->number_of_evasions(); } + + RootMoveList::iterator rm; // Dummy, never used + MovePicker* mp; + }; + + // Normal case, create and use a MovePicker object as source + template<> struct MovePickerExt : public MovePicker { + + MovePickerExt(const Position& p, Move ttm, Depth d, const History& h, + SearchStack* ss, Value beta) : MovePicker(p, ttm, d, h, ss, beta) {} + + RootMoveList::iterator rm; // Dummy, never used + }; + +} // namespace //// @@ -406,7 +452,7 @@ int64_t perft(Position& pos, Depth depth) /// think() is the external interface to Stockfish's search, and is called when /// the program receives the UCI 'go' command. It initializes various -/// search-related global variables, and calls root_search(). It returns false +/// search-related global variables, and calls id_loop(). It returns false /// when a quit command is received during the search. bool think(Position& pos, bool infinite, bool ponder, int time[], int increment[], @@ -548,7 +594,7 @@ bool think(Position& pos, bool infinite, bool ponder, int time[], int increment[ namespace { - // id_loop() is the main iterative deepening loop. It calls root_search + // id_loop() is the main iterative deepening loop. It calls search() // repeatedly with increasing depth until the allocated thinking time has // been consumed, the user stops the search, or the maximum search depth is // reached. @@ -628,7 +674,6 @@ namespace { rml.sort(); // Search to the current depth, rml is updated and sorted - //value = root_search(pos, ss, alpha, beta, depth, rml); value = search(pos, ss, alpha, beta, depth, 0); // Sort the moves before to return @@ -727,228 +772,6 @@ namespace { } - // root_search() is the function which searches the root node. It is - // similar to search_pv except that it prints some information to the - // standard output and handles the fail low/high loops. - - Value root_search(Position& pos, SearchStack* ss, Value alpha, - Value beta, Depth depth, RootMoveList& rml) { - - assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE); - assert(beta > alpha && beta <= VALUE_INFINITE); - assert(pos.thread() >= 0 && pos.thread() < ThreadsMgr.active_threads()); - - Move movesSearched[MOVES_MAX]; - StateInfo st; - Key posKey; - Move move; - Depth ext, newDepth; - ValueType vt; - Value bestValue, value, oldAlpha; - bool isCheck, moveIsCheck, captureOrPromotion, dangerous, isPvMove; - int moveCount = 0; - - bestValue = value = -VALUE_INFINITE; - oldAlpha = alpha; - isCheck = pos.is_check(); - - // Step 1. Initialize node (polling is omitted at root) - ss->currentMove = ss->bestMove = MOVE_NONE; - (ss+2)->killers[0] = (ss+2)->killers[1] = (ss+2)->mateKiller = MOVE_NONE; - - // Step 2. Check for aborted search (omitted at root) - // Step 3. Mate distance pruning (omitted at root) - // Step 4. Transposition table lookup (omitted at root) - posKey = pos.get_key(); - - // Step 5. Evaluate the position statically - // At root we do this only to get reference value for child nodes - ss->evalMargin = VALUE_NONE; - ss->eval = isCheck ? VALUE_NONE : evaluate(pos, ss->evalMargin); - - // Step 6. Razoring (omitted at root) - // Step 7. Static null move pruning (omitted at root) - // Step 8. Null move search with verification search (omitted at root) - // Step 9. Internal iterative deepening (omitted at root) - - CheckInfo ci(pos); - int64_t nodes; - RootMoveList::iterator rm = rml.begin(); - bestValue = alpha; - - // Step 10. Loop through moves - // Loop through all legal moves until no moves remain or a beta cutoff occurs - while ( bestValue < beta - && rm != rml.end() - && !StopRequest) - { - move = ss->currentMove = rm->pv[0]; - movesSearched[moveCount++] = move; - isPvMove = (moveCount <= MultiPV); - - // This is used by time management - FirstRootMove = (rm == rml.begin()); - - // Save the current node count before the move is searched - nodes = pos.nodes_searched(); - - // If it's time to send nodes info, do it here where we have the - // correct accumulated node counts searched by each thread. - if (SendSearchedNodes) - { - SendSearchedNodes = false; - cout << "info nodes " << nodes - << " nps " << nps(pos) - << " time " << current_search_time() << endl; - } - - if (current_search_time() >= 1000) - cout << "info currmove " << move - << " currmovenumber " << moveCount << endl; - - moveIsCheck = pos.move_is_check(move); - captureOrPromotion = pos.move_is_capture_or_promotion(move); - - // Step 11. Decide the new search depth - ext = extension(pos, move, captureOrPromotion, moveIsCheck, false, false, &dangerous); - newDepth = depth + ext; - - // Step 12. Futility pruning (omitted at root) - // Step 13. Make the move - pos.do_move(move, st, ci, moveIsCheck); - - // Step extra. pv search - // We do pv search for PV moves - if (isPvMove) - { - // Aspiration window is disabled in multi-pv case - if (MultiPV > 1) - alpha = -VALUE_INFINITE; - - // Full depth PV search, done on first move or after a fail high - value = -search(pos, ss+1, -beta, -alpha, newDepth, 1); - } - else - { - // Step 14. Reduced search - // if the move fails high will be re-searched at full depth - bool doFullDepthSearch = true; - - if ( depth >= 3 * ONE_PLY - && !captureOrPromotion - && !dangerous - && !move_is_castle(move) - && ss->killers[0] != move - && ss->killers[1] != move) - { - ss->reduction = reduction(depth, moveCount - MultiPV + 1); - - if (ss->reduction) - { - Depth d = newDepth - ss->reduction; - value = -search(pos, ss+1, -(alpha+1), -alpha, d, 1); - - doFullDepthSearch = (value > alpha); - } - ss->reduction = DEPTH_ZERO; // Restore original reduction - } - - // Step 15. Full depth search - if (doFullDepthSearch) - { - // Full depth non-pv search using alpha as upperbound - value = -search(pos, ss+1, -(alpha+1), -alpha, newDepth, 1); - - // 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+1, -beta, -alpha, newDepth, 1); - } - } - - // Step 16. Undo move - pos.undo_move(move); - - assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); - - // Finished searching the move. If StopRequest is true, the search - // was aborted because the user interrupted the search or because we - // ran out of time. In this case, the return value of the search cannot - // be trusted, and we break out of the loop without updating the best - // move and/or PV. - if (StopRequest) - break; - - // Remember searched nodes counts for this move - rm->nodes += pos.nodes_searched() - nodes; - - // Step 17. Check for new best move - if (!isPvMove && value <= alpha) - rm->pv_score = -VALUE_INFINITE; - else - { - // PV move or new best move! - - // Update PV - ss->bestMove = move; - rm->pv_score = value; - rm->extract_pv_from_tt(pos); - - // We record how often the best move has been changed in each - // iteration. This information is used for time managment: When - // the best move changes frequently, we allocate some more time. - if (!isPvMove && MultiPV == 1) - BestMoveChangesByIteration[Iteration]++; - - // Inform GUI that PV has changed, in case of multi-pv UCI protocol - // requires we send all the PV lines properly sorted. - rml.sort_multipv(moveCount); - - for (int j = 0; j < Min(MultiPV, (int)rml.size()); j++) - cout << rml[j].pv_info_to_uci(pos, alpha, beta, j) << endl; - - // Update alpha. In multi-pv we don't use aspiration window - if (MultiPV == 1) - { - // Raise alpha to setup proper non-pv search upper bound - if (value > alpha) - alpha = bestValue = value; - } - else // Set alpha equal to minimum score among the PV lines - alpha = bestValue = rml[Min(moveCount, MultiPV) - 1].pv_score; // FIXME why moveCount? - - } // PV move or new best move - - ++rm; - - } // Root moves loop - - // Step 20. Update tables - // If the search is not aborted, update the transposition table, - // history counters, and killer moves. - if (!StopRequest) - { - move = bestValue <= oldAlpha ? MOVE_NONE : ss->bestMove; - vt = bestValue <= oldAlpha ? VALUE_TYPE_UPPER - : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT; - - TT.store(posKey, value_to_tt(bestValue, 0), vt, depth, move, ss->eval, ss->evalMargin); - - // Update killers and history only for non capture moves that fails high - if ( bestValue >= beta - && !pos.move_is_capture_or_promotion(move)) - { - update_history(pos, move, depth, movesSearched, moveCount); - update_killers(move, ss->killers); - } - } - - assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); - - return bestValue; - } - - // search<>() is the main search function for both PV and non-PV nodes and for // normal and SplitPoint nodes. When called just after a split point the search // is simpler because we have already probed the hash table, done a null move @@ -967,7 +790,6 @@ namespace { Move movesSearched[MOVES_MAX]; int64_t nodes; - RootMoveList::iterator rm; StateInfo st; const TTEntry *tte; Key posKey; @@ -1182,9 +1004,7 @@ namespace { split_point_start: // At split points actual search starts from here // Initialize a MovePicker object for the current position - // FIXME currently MovePicker() c'tor is needless called also in SplitPoint - MovePicker mpBase(pos, ttMove, depth, H, ss, (PvNode ? -VALUE_INFINITE : beta)); - MovePicker& mp = SpNode ? *sp->mp : mpBase; + MovePickerExt mp(pos, ttMove, depth, H, ss, (PvNode ? -VALUE_INFINITE : beta)); CheckInfo ci(pos); ss->bestMove = MOVE_NONE; singleEvasion = !SpNode && isCheck && mp.number_of_evasions() == 1; @@ -1198,10 +1018,7 @@ split_point_start: // At split points actual search starts from here && (tte->type() & VALUE_TYPE_LOWER) && tte->depth() >= depth - 3 * ONE_PLY; if (Root) - { - rm = Rml->begin(); bestValue = alpha; - } if (SpNode) { @@ -1212,16 +1029,25 @@ 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 while ( bestValue < beta - && (!Root || rm != Rml->end()) - && ( Root || (move = mp.get_next_move()) != MOVE_NONE) + && (move = mp.get_next_move()) != MOVE_NONE && !ThreadsMgr.cutoff_at_splitpoint(threadID)) { - if (Root) + assert(move_is_ok(move)); + + if (SpNode) { - move = rm->pv[0]; + moveCount = ++sp->moveCount; + lock_release(&(sp->lock)); + } + else if (move == excludedMove) + continue; + else + movesSearched[moveCount++] = move; + if (Root) + { // This is used by time management - FirstRootMove = (rm == Rml->begin()); + FirstRootMove = (moveCount == 1); // Save the current node count before the move is searched nodes = pos.nodes_searched(); @@ -1241,18 +1067,6 @@ split_point_start: // At split points actual search starts from here << " currmovenumber " << moveCount << endl; } - assert(move_is_ok(move)); - - if (SpNode) - { - moveCount = ++sp->moveCount; - lock_release(&(sp->lock)); - } - else if (move == excludedMove) - continue; - else - movesSearched[moveCount++] = move; - isPvMove = (PvNode && moveCount <= (Root ? MultiPV : 1)); moveIsCheck = pos.move_is_check(move, ci); captureOrPromotion = pos.move_is_capture_or_promotion(move); @@ -1446,19 +1260,19 @@ split_point_start: // At split points actual search starts from here break; // Remember searched nodes counts for this move - rm->nodes += pos.nodes_searched() - nodes; + mp.rm->nodes += pos.nodes_searched() - nodes; // Step 17. Check for new best move if (!isPvMove && value <= alpha) - rm->pv_score = -VALUE_INFINITE; + mp.rm->pv_score = -VALUE_INFINITE; else { // PV move or new best move! // Update PV ss->bestMove = move; - rm->pv_score = value; - rm->extract_pv_from_tt(pos); + mp.rm->pv_score = value; + mp.rm->extract_pv_from_tt(pos); // We record how often the best move has been changed in each // iteration. This information is used for time managment: When @@ -1484,8 +1298,6 @@ split_point_start: // At split points actual search starts from here alpha = bestValue = (*Rml)[Min(moveCount, MultiPV) - 1].pv_score; // FIXME why moveCount? } // PV move or new best move - - ++rm; } // Step 18. Check for split @@ -1499,7 +1311,7 @@ split_point_start: // At split points actual search starts from here && !ThreadsMgr.cutoff_at_splitpoint(threadID) && Iteration <= 99) ThreadsMgr.split(pos, ss, ply, &alpha, beta, &bestValue, depth, - threatMove, mateThreat, moveCount, &mp, PvNode); + threatMove, mateThreat, moveCount, (MovePicker*)&mp, PvNode); } // Step 19. Check for mate and stalemate