X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;ds=sidebyside;f=src%2Fsearch.cpp;h=cd4bf3e4d26faad6a5f3a3c7f5e535d4bab13e14;hb=c0136fb7286416be2ec179b4787f53d77023eeaf;hp=0ac1f364ed70ec743cefe5da1bc7cb55619b540e;hpb=e4e12ed59516201dc77fa72a291ac7385cdb482b;p=stockfish diff --git a/src/search.cpp b/src/search.cpp index 0ac1f364..cd4bf3e4 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -89,7 +89,7 @@ namespace { void idle_loop(int threadID, SplitPoint* sp); template - void split(const Position& pos, SearchStack* ss, int ply, Value* alpha, const Value beta, Value* bestValue, + void split(const Position& pos, SearchStack* ss, Value* alpha, const Value beta, Value* bestValue, Depth depth, bool mateThreat, int* moveCount, MovePicker* mp, int master, bool pvNode); private: @@ -285,10 +285,10 @@ namespace { Value root_search(Position& pos, SearchStack* ss, RootMoveList& rml, Value* alphaPtr, Value* betaPtr); template - Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply, bool allowNullmove, int threadID, Move excludedMove = MOVE_NONE); + Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, bool allowNullmove, int threadID, Move excludedMove = MOVE_NONE); template - Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int ply, int threadID); + Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int threadID); template void sp_search(SplitPoint* sp, int threadID); @@ -296,7 +296,6 @@ namespace { template Depth extension(const Position& pos, Move m, bool captureOrPromotion, bool moveIsCheck, bool singleEvasion, bool mateThreat, bool* dangerous); - 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); @@ -637,6 +636,7 @@ namespace { H.clear(); init_ss_array(ss); ValueByIteration[1] = rml.get_move_score(0); + p.reset_ply(); Iteration = 1; // Is one move significantly better than others after initial scoring ? @@ -877,7 +877,7 @@ namespace { 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, false, 0); + value = -search(pos, ss+1, -beta, -alpha, newDepth, false, 0); } else { @@ -894,7 +894,7 @@ namespace { if (ss->reduction) { // Reduced depth non-pv search using alpha as upperbound - value = -search(pos, ss+1, -(alpha+1), -alpha, newDepth-ss->reduction, 1, true, 0); + value = -search(pos, ss+1, -(alpha+1), -alpha, newDepth-ss->reduction, true, 0); doFullDepthSearch = (value > alpha); } } @@ -904,12 +904,12 @@ namespace { { // Full depth non-pv search using alpha as upperbound ss->reduction = Depth(0); - value = -search(pos, ss+1, -(alpha+1), -alpha, newDepth, 1, true, 0); + value = -search(pos, ss+1, -(alpha+1), -alpha, newDepth, 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+1, -beta, -alpha, newDepth, 1, false, 0); + value = -search(pos, ss+1, -beta, -alpha, newDepth, false, 0); } } @@ -1033,12 +1033,12 @@ namespace { template Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, - int ply, bool allowNullmove, int threadID, Move excludedMove) { + bool allowNullmove, int threadID, Move excludedMove) { assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE); assert(beta > alpha && beta <= VALUE_INFINITE); assert(PvNode || alpha == beta - 1); - assert(ply >= 0 && ply < PLY_MAX); + assert(pos.ply() > 0 && pos.ply() < PLY_MAX); assert(threadID >= 0 && threadID < TM.active_threads()); Move movesSearched[256]; @@ -1052,15 +1052,20 @@ namespace { bool isCheck, singleEvasion, moveIsCheck, captureOrPromotion, dangerous; bool mateThreat = false; int moveCount = 0; + int ply = pos.ply(); refinedValue = bestValue = value = -VALUE_INFINITE; oldAlpha = alpha; - if (depth < OnePly) - return qsearch(pos, ss, alpha, beta, Depth(0), ply, threadID); + // Step 1. Initialize node and poll. Polling can abort search + TM.incrementNodeCounter(threadID); + ss->init(ply); + (ss + 2)->initKillers(); - // Step 1. Initialize node and poll - // Polling can abort search. - init_node(ss, ply, threadID); + if (threadID == 0 && ++NodesSincePoll > NodesBetweenPolls) + { + NodesSincePoll = 0; + poll(); + } // Step 2. Check for aborted search and immediate draw if (AbortSearch || TM.thread_should_stop(threadID)) @@ -1129,7 +1134,7 @@ namespace { && !pos.has_pawn_on_7th(pos.side_to_move())) { Value rbeta = beta - razor_margin(depth); - Value v = qsearch(pos, ss, rbeta-1, rbeta, Depth(0), ply, threadID); + Value v = qsearch(pos, ss, rbeta-1, rbeta, Depth(0), threadID); if (v < rbeta) // Logically we should return (v + razor_margin(depth)), but // surprisingly this did slightly weaker in tests. @@ -1171,8 +1176,8 @@ namespace { pos.do_null_move(st); - nullValue = -search(pos, ss+1, -beta, -alpha, depth-R*OnePly, ply+1, false, threadID); - + nullValue = depth-R*OnePly < OnePly ? -qsearch(pos, ss+1, -beta, -alpha, Depth(0), threadID) + : - search(pos, ss+1, -beta, -alpha, depth-R*OnePly, false, threadID); pos.undo_null_move(); if (nullValue >= beta) @@ -1185,7 +1190,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, false, threadID); if (v >= beta) return nullValue; } else { @@ -1212,7 +1217,7 @@ namespace { && (PvNode || (!isCheck && ss->eval >= beta - IIDMargin))) { Depth d = (PvNode ? depth - 2 * OnePly : depth / 2); - search(pos, ss, alpha, beta, d, ply, false, threadID); + search(pos, ss, alpha, beta, d, false, threadID); ttMove = ss->pv[ply]; tte = TT.retrieve(posKey); } @@ -1259,7 +1264,7 @@ namespace { if (abs(ttValue) < VALUE_KNOWN_WIN) { Value b = ttValue - SingularExtensionMargin; - Value v = search(pos, ss, b - 1, b, depth / 2, ply, false, threadID, move); + Value v = search(pos, ss, b - 1, b, depth / 2, false, threadID, move); if (v < ttValue - SingularExtensionMargin) ext = OnePly; @@ -1306,7 +1311,8 @@ 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+1, -beta, -alpha, newDepth, ply+1, false, threadID); + value = newDepth < OnePly ? -qsearch(pos, ss+1, -beta, -alpha, Depth(0), threadID) + : - search(pos, ss+1, -beta, -alpha, newDepth, false, threadID); else { // Step 14. Reduced depth search @@ -1322,7 +1328,10 @@ namespace { ss->reduction = reduction(depth, moveCount); if (ss->reduction) { - value = -search(pos, ss+1, -(alpha+1), -alpha, newDepth-ss->reduction, ply+1, true, threadID); + Depth r = newDepth - ss->reduction; + value = r < OnePly ? -qsearch(pos, ss+1, -(alpha+1), -alpha, Depth(0), threadID) + : - search(pos, ss+1, -(alpha+1), -alpha, r, true, threadID); + doFullDepthSearch = (value > alpha); } @@ -1331,8 +1340,10 @@ namespace { // if the move fails high again then go with full depth search. if (doFullDepthSearch && ss->reduction > 2 * OnePly) { + assert(newDepth - OnePly >= OnePly); + ss->reduction = OnePly; - value = -search(pos, ss+1, -(alpha+1), -alpha, newDepth-ss->reduction, ply+1, true, threadID); + value = -search(pos, ss+1, -(alpha+1), -alpha, newDepth-ss->reduction, true, threadID); doFullDepthSearch = (value > alpha); } } @@ -1341,13 +1352,15 @@ namespace { if (doFullDepthSearch) { ss->reduction = Depth(0); - value = -search(pos, ss+1, -(alpha+1), -alpha, newDepth, ply+1, true, threadID); + value = newDepth < OnePly ? -qsearch(pos, ss+1, -(alpha+1), -alpha, Depth(0), threadID) + : - search(pos, ss+1, -(alpha+1), -alpha, newDepth, true, threadID); // 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 && value < beta) - value = -search(pos, ss+1, -beta, -alpha, newDepth, ply+1, false, threadID); + value = newDepth < OnePly ? -qsearch(pos, ss+1, -beta, -alpha, Depth(0), threadID) + : - search(pos, ss+1, -beta, -alpha, newDepth, false, threadID); } } @@ -1380,7 +1393,7 @@ namespace { && TM.available_thread_exists(threadID) && !AbortSearch && !TM.thread_should_stop(threadID)) - TM.split(pos, ss, ply, &alpha, beta, &bestValue, depth, + TM.split(pos, ss, &alpha, beta, &bestValue, depth, mateThreat, &moveCount, &mp, threadID, PvNode); } @@ -1425,14 +1438,13 @@ namespace { // less than OnePly). template - Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, - Depth depth, int ply, int threadID) { + Value qsearch(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth, int threadID) { assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE); assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE); assert(PvNode || alpha == beta - 1); assert(depth <= 0); - assert(ply >= 0 && ply < PLY_MAX); + assert(pos.ply() > 0 && pos.ply() < PLY_MAX); assert(threadID >= 0 && threadID < TM.active_threads()); EvalInfo ei; @@ -1442,16 +1454,13 @@ namespace { bool isCheck, enoughMaterial, moveIsCheck, evasionPrunable; const TTEntry* tte = NULL; int moveCount = 0; + int ply = pos.ply(); Value oldAlpha = alpha; - // Initialize, and make an early exit in case of an aborted search, - // an instant draw, maximum ply reached, etc. - init_node(ss, ply, threadID); - - // After init_node() that calls poll() - if (AbortSearch || TM.thread_should_stop(threadID)) - return Value(0); + TM.incrementNodeCounter(threadID); + ss->init(ply); + // Check for an instant draw or maximum ply reached if (pos.is_draw() || ply >= PLY_MAX - 1) return VALUE_DRAW; @@ -1563,7 +1572,7 @@ namespace { // Make and search the move pos.do_move(move, st, ci, moveIsCheck); - value = -qsearch(pos, ss+1, -beta, -alpha, depth-OnePly, ply+1, threadID); + value = -qsearch(pos, ss+1, -beta, -alpha, depth-OnePly, threadID); pos.undo_move(move); assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); @@ -1636,6 +1645,7 @@ namespace { Position pos(*sp->pos); CheckInfo ci(pos); + int ply = pos.ply(); SearchStack* ss = sp->sstack[threadID] + 1; isCheck = pos.is_check(); @@ -1709,7 +1719,7 @@ namespace { if (ss->reduction) { Value localAlpha = sp->alpha; - value = -search(pos, ss+1, -(localAlpha+1), -localAlpha, newDepth-ss->reduction, sp->ply+1, true, threadID); + value = -search(pos, ss+1, -(localAlpha+1), -localAlpha, newDepth-ss->reduction, true, threadID); doFullDepthSearch = (value > localAlpha); } @@ -1720,7 +1730,7 @@ namespace { { ss->reduction = OnePly; Value localAlpha = sp->alpha; - value = -search(pos, ss+1, -(localAlpha+1), -localAlpha, newDepth-ss->reduction, sp->ply+1, true, threadID); + value = -search(pos, ss+1, -(localAlpha+1), -localAlpha, newDepth-ss->reduction, true, threadID); doFullDepthSearch = (value > localAlpha); } } @@ -1730,10 +1740,10 @@ namespace { { ss->reduction = Depth(0); Value localAlpha = sp->alpha; - value = -search(pos, ss+1, -(localAlpha+1), -localAlpha, newDepth, sp->ply+1, true, threadID); + value = -search(pos, ss+1, -(localAlpha+1), -localAlpha, newDepth, true, threadID); if (PvNode && value > localAlpha && value < sp->beta) - value = -search(pos, ss+1, -sp->beta, -sp->alpha, newDepth, sp->ply+1, false, threadID); + value = -search(pos, ss+1, -sp->beta, -sp->alpha, newDepth, false, threadID); } // Step 16. Undo move @@ -1756,7 +1766,7 @@ namespace { if (PvNode && value < sp->beta) // This guarantees that always: sp->alpha < sp->beta sp->alpha = value; - sp_update_pv(sp->parentSstack, ss, sp->ply); + sp_update_pv(sp->parentSstack, ss, ply); } } } @@ -1768,32 +1778,6 @@ namespace { lock_release(&(sp->lock)); } - // init_node() is called at the beginning of all the search functions - // (search() 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(SearchStack* ss, int ply, int threadID) { - - assert(ply >= 0 && ply < PLY_MAX); - assert(threadID >= 0 && threadID < TM.active_threads()); - - TM.incrementNodeCounter(threadID); - - if (threadID == 0) - { - NodesSincePoll++; - if (NodesSincePoll >= NodesBetweenPolls) - { - poll(); - NodesSincePoll = 0; - } - } - ss->init(ply); - (ss + 2)->initKillers(); - } - // update_pv() is called whenever a search returns a value > alpha. // It updates the PV in the SearchStack object corresponding to the // current node. @@ -2477,10 +2461,7 @@ namespace { // Initialize SplitPointStack locks for (i = 0; i < MAX_THREADS; i++) for (int j = 0; j < ACTIVE_SPLIT_POINTS_MAX; j++) - { - SplitPointStack[i][j].parent = NULL; lock_init(&(SplitPointStack[i][j].lock), NULL); - } // Will be set just before program exits to properly end the threads AllThreadsShouldExit = false; @@ -2530,7 +2511,7 @@ namespace { // Wait for thread termination for (int i = 1; i < MAX_THREADS; i++) - while (threads[i].state != THREAD_TERMINATED); + while (threads[i].state != THREAD_TERMINATED) {} // Now we can safely destroy the locks for (int i = 0; i < MAX_THREADS; i++) @@ -2622,11 +2603,10 @@ namespace { // split() returns. template - void ThreadsManager::split(const Position& p, SearchStack* ss, int ply, Value* alpha, - const Value beta, Value* bestValue, Depth depth, bool mateThreat, - int* moveCount, MovePicker* mp, int master, bool pvNode) { + void ThreadsManager::split(const Position& p, SearchStack* ss, Value* alpha, const Value beta, + Value* bestValue, Depth depth, bool mateThreat, int* moveCount, + MovePicker* mp, int master, bool pvNode) { assert(p.is_ok()); - assert(ply > 0 && ply < PLY_MAX); assert(*bestValue >= -VALUE_INFINITE); assert(*bestValue <= *alpha); assert(*alpha < beta); @@ -2652,7 +2632,6 @@ namespace { // Initialize the split point object splitPoint->parent = threads[master].splitPoint; splitPoint->stopRequest = false; - splitPoint->ply = ply; splitPoint->depth = depth; splitPoint->mateThreat = mateThreat; splitPoint->alpha = *alpha; @@ -2787,7 +2766,7 @@ namespace { init_ss_array(ss); pos.do_move(cur->move, st); moves[count].move = cur->move; - moves[count].score = -qsearch(pos, ss, -VALUE_INFINITE, VALUE_INFINITE, Depth(0), 1, 0); + moves[count].score = -qsearch(pos, ss+1, -VALUE_INFINITE, VALUE_INFINITE, Depth(0), 0); moves[count].pv[0] = cur->move; moves[count].pv[1] = MOVE_NONE; pos.undo_move(cur->move);