X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;ds=sidebyside;f=src%2Fsearch.cpp;h=4550f5f7002ac39adc345efa8205b0990becee42;hb=a3819188de0f8193182264fe6e32d1b53bf1dacf;hp=0ac1f364ed70ec743cefe5da1bc7cb55619b540e;hpb=e4e12ed59516201dc77fa72a291ac7385cdb482b;p=stockfish diff --git a/src/search.cpp b/src/search.cpp index 0ac1f364..4550f5f7 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,15 +296,14 @@ 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); bool value_is_mate(Value value); bool move_is_killer(Move m, SearchStack* ss); 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); + bool connected_threat(const Position& pos, Move m, Move threat); Value refine_eval(const TTEntry* tte, Value defaultEval, int ply); void update_history(const Position& pos, Move move, Depth depth, Move movesSearched[], int moveCount); void update_killers(Move m, SearchStack* ss); @@ -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; @@ -1281,7 +1286,7 @@ namespace { { // Move count based pruning if ( moveCount >= futility_move_count(depth) - && ok_to_prune(pos, move, ss->threatMove) + && !(ss->threatMove && connected_threat(pos, move, ss->threatMove)) && bestValue > value_mated_in(PLY_MAX)) continue; @@ -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 d = newDepth - ss->reduction; + value = d < OnePly ? -qsearch(pos, ss+1, -(alpha+1), -alpha, Depth(0), threadID) + : - search(pos, ss+1, -(alpha+1), -alpha, d, 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(); @@ -1671,7 +1681,7 @@ namespace { { // Move count based pruning if ( moveCount >= futility_move_count(sp->depth) - && ok_to_prune(pos, move, ss->threatMove) + && !(ss->threatMove && connected_threat(pos, move, ss->threatMove)) && sp->bestValue > value_mated_in(PLY_MAX)) { lock_grab(&(sp->lock)); @@ -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. @@ -1994,24 +1978,19 @@ namespace { } - // ok_to_prune() tests whether it is safe to forward prune a move. Only - // non-tactical moves late in the move list close to the leaves are - // candidates for pruning. + // connected_threat() tests whether it is safe to forward prune a move or if + // is somehow coonected to the threat move returned by null search. - bool ok_to_prune(const Position& pos, Move m, Move threat) { + bool connected_threat(const Position& pos, Move m, Move threat) { assert(move_is_ok(m)); - assert(threat == MOVE_NONE || move_is_ok(threat)); + assert(threat && move_is_ok(threat)); assert(!pos.move_is_check(m)); assert(!pos.move_is_capture_or_promotion(m)); assert(!pos.move_is_passed_pawn_push(m)); Square mfrom, mto, tfrom, tto; - // Prune if there isn't any threat move - if (threat == MOVE_NONE) - return true; - mfrom = move_from(m); mto = move_to(m); tfrom = move_from(threat); @@ -2019,7 +1998,7 @@ namespace { // Case 1: Don't prune moves which move the threatened piece if (mfrom == tto) - return false; + return true; // Case 2: If the threatened piece has value less than or equal to the // value of the threatening piece, don't prune move which defend it. @@ -2027,16 +2006,16 @@ namespace { && ( 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; + return true; // Case 3: If the moving piece in the threatened move is a slider, don't // prune safe moves which block its ray. if ( piece_is_slider(pos.piece_on(tfrom)) && bit_is_set(squares_between(tfrom, tto), mto) && pos.see_sign(m) >= 0) - return false; + return true; - return true; + return false; } @@ -2477,10 +2456,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 +2506,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 +2598,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 +2627,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 +2761,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);