X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=a1e1cea5c9c6a948977728575ee1ddb638e8a01c;hp=7ff9aaa466902ae5b851ea2c225a853d8416c576;hb=4fc773454759081c2cd921e460d542f2dfd4aa24;hpb=05c6f7a40b62f286873945f937c2ef3cae183e41 diff --git a/src/search.cpp b/src/search.cpp index 7ff9aaa4..a1e1cea5 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -91,7 +91,7 @@ namespace { CountermovesStats Countermoves; template - Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth); + Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode); template Value qsearch(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth); @@ -155,21 +155,17 @@ void Search::init() { size_t Search::perft(Position& pos, Depth depth) { - // At the last ply just return the number of legal moves (leaf nodes) - if (depth == ONE_PLY) - return MoveList(pos).size(); - StateInfo st; size_t cnt = 0; CheckInfo ci(pos); + const bool leaf = depth == 2 * ONE_PLY; for (MoveList it(pos); *it; ++it) { pos.do_move(*it, st, ci, pos.move_gives_check(*it, ci)); - cnt += perft(pos, depth - ONE_PLY); + cnt += leaf ? MoveList(pos).size() : perft(pos, depth - ONE_PLY); pos.undo_move(*it); } - return cnt; } @@ -295,14 +291,14 @@ namespace { void id_loop(Position& pos) { - Stack ss[MAX_PLY_PLUS_2]; + Stack stack[MAX_PLY_PLUS_2], *ss = stack+1; // To allow referencing (ss-1) int depth, prevBestMoveChanges; Value bestValue, alpha, beta, delta; - memset(ss, 0, 4 * sizeof(Stack)); + memset(ss-1, 0, 4 * sizeof(Stack)); depth = BestMoveChanges = 0; bestValue = delta = -VALUE_INFINITE; - ss->currentMove = MOVE_NULL; // Hack to skip update gains + (ss-1)->currentMove = MOVE_NULL; // Hack to skip update gains TT.new_search(); History.clear(); Gains.clear(); @@ -349,9 +345,7 @@ namespace { // research with bigger window until not failing high/low anymore. while (true) { - // Search starts from ss+1 to allow referencing (ss-1). This is - // needed by update gains and ss copy when splitting at Root. - bestValue = search(pos, ss+1, alpha, beta, depth * ONE_PLY); + bestValue = search(pos, ss, alpha, beta, depth * ONE_PLY, false); // Bring to front the best move. It is critical that sorting is // done with a stable algorithm because all the values but the first @@ -421,7 +415,7 @@ namespace { rm = *std::find(RootMoves.begin(), RootMoves.end(), skill.best); Log log(Options["Search Log Filename"]); - log << pretty_pv(pos, depth, rm.score, Time::now() - SearchTime, rm.pv.data()) + log << pretty_pv(pos, depth, rm.score, Time::now() - SearchTime, &rm.pv[0]) << std::endl; } @@ -455,11 +449,11 @@ namespace { || Time::now() - SearchTime > (TimeMgr.available_time() * 20) / 100)) { Value rBeta = bestValue - 2 * PawnValueMg; - (ss+1)->excludedMove = RootMoves[0].pv[0]; - (ss+1)->skipNullMove = true; - Value v = search(pos, ss+1, rBeta - 1, rBeta, (depth - 3) * ONE_PLY); - (ss+1)->skipNullMove = false; - (ss+1)->excludedMove = MOVE_NONE; + ss->excludedMove = RootMoves[0].pv[0]; + ss->skipNullMove = true; + Value v = search(pos, ss, rBeta - 1, rBeta, (depth - 3) * ONE_PLY, true); + ss->skipNullMove = false; + ss->excludedMove = MOVE_NONE; if (v < rBeta) stop = true; @@ -487,7 +481,7 @@ namespace { // here: This is taken care of after we return from the split point. template - Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth) { + Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode) { const bool PvNode = (NT == PV || NT == Root || NT == SplitPointPV || NT == SplitPointRoot); const bool SpNode = (NT == SplitPointPV || NT == SplitPointNonPV || NT == SplitPointRoot); @@ -497,7 +491,7 @@ namespace { assert(PvNode || (alpha == beta - 1)); assert(depth > DEPTH_ZERO); - Move movesSearched[64]; + Move quietsSearched[64]; StateInfo st; const TTEntry *tte; SplitPoint* splitPoint; @@ -508,11 +502,11 @@ namespace { Value eval, nullValue, futilityValue; bool inCheck, givesCheck, pvMove, singularExtensionNode; bool captureOrPromotion, dangerous, doFullDepthSearch; - int moveCount, playedMoveCount; + int moveCount, quietCount; // Step 1. Initialize node Thread* thisThread = pos.this_thread(); - moveCount = playedMoveCount = 0; + moveCount = quietCount = 0; inCheck = pos.checkers(); if (SpNode) @@ -576,9 +570,9 @@ namespace { && tte && tte->depth() >= depth && ttValue != VALUE_NONE // Only in case of TT access race - && ( PvNode ? tte->type() == BOUND_EXACT - : ttValue >= beta ? (tte->type() & BOUND_LOWER) - : (tte->type() & BOUND_UPPER))) + && ( PvNode ? tte->bound() == BOUND_EXACT + : ttValue >= beta ? (tte->bound() & BOUND_LOWER) + : (tte->bound() & BOUND_UPPER))) { TT.refresh(tte); ss->currentMove = ttMove; // Can be MOVE_NONE @@ -607,8 +601,8 @@ namespace { // Can ttValue be used as a better position evaluation? if (ttValue != VALUE_NONE) - if ( ((tte->type() & BOUND_LOWER) && ttValue > eval) - || ((tte->type() & BOUND_UPPER) && ttValue < eval)) + if ( ((tte->bound() & BOUND_LOWER) && ttValue > eval) + || ((tte->bound() & BOUND_UPPER) && ttValue < eval)) eval = ttValue; } else @@ -620,10 +614,10 @@ namespace { // Update gain for the parent non-capture move given the static position // evaluation before and after the move. - if ( (move = (ss-1)->currentMove) != MOVE_NULL - && (ss-1)->staticEval != VALUE_NONE + if ( !pos.captured_piece_type() && ss->staticEval != VALUE_NONE - && !pos.captured_piece_type() + && (ss-1)->staticEval != VALUE_NONE + && (move = (ss-1)->currentMove) != MOVE_NULL && type_of(move) == NORMAL) { Square to = to_sq(move); @@ -681,7 +675,7 @@ namespace { pos.do_null_move(st); (ss+1)->skipNullMove = true; nullValue = depth-R < ONE_PLY ? -qsearch(pos, ss+1, -beta, -alpha, DEPTH_ZERO) - : - search(pos, ss+1, -beta, -alpha, depth-R); + : - search(pos, ss+1, -beta, -alpha, depth-R, !cutNode); (ss+1)->skipNullMove = false; pos.undo_null_move(); @@ -696,7 +690,7 @@ namespace { // Do verification search at high depths ss->skipNullMove = true; - Value v = search(pos, ss, alpha, beta, depth-R); + Value v = search(pos, ss, alpha, beta, depth-R, false); ss->skipNullMove = false; if (v >= beta) @@ -716,7 +710,7 @@ namespace { && (ss-1)->reduction && threatMove != MOVE_NONE && allows(pos, (ss-1)->currentMove, threatMove)) - return beta - 1; + return alpha; } } @@ -728,7 +722,6 @@ namespace { && depth >= 5 * ONE_PLY && !inCheck && !ss->skipNullMove - && excludedMove == MOVE_NONE && abs(beta) < VALUE_MATE_IN_MAX_PLY) { Value rbeta = beta + 200; @@ -746,7 +739,7 @@ namespace { { ss->currentMove = move; pos.do_move(move, st, ci, pos.move_gives_check(move, ci)); - value = -search(pos, ss+1, -rbeta, -rbeta+1, rdepth); + value = -search(pos, ss+1, -rbeta, -rbeta+1, rdepth, !cutNode); pos.undo_move(move); if (value >= rbeta) return value; @@ -761,7 +754,7 @@ namespace { Depth d = depth - 2 * ONE_PLY - (PvNode ? DEPTH_ZERO : depth / 4); ss->skipNullMove = true; - search(pos, ss, alpha, beta, d); + search(pos, ss, alpha, beta, d, true); ss->skipNullMove = false; tte = TT.probe(posKey); @@ -782,7 +775,7 @@ split_point_start: // At split points actual search starts from here && depth >= (PvNode ? 6 * ONE_PLY : 8 * ONE_PLY) && ttMove != MOVE_NONE && !excludedMove // Recursive singular search is not allowed - && (tte->type() & BOUND_LOWER) + && (tte->bound() & BOUND_LOWER) && tte->depth() >= depth - 3 * ONE_PLY; // Step 11. Loop through moves @@ -857,7 +850,7 @@ split_point_start: // At split points actual search starts from here Value rBeta = ttValue - int(depth); ss->excludedMove = move; ss->skipNullMove = true; - value = search(pos, ss, rBeta - 1, rBeta, depth / 2); + value = search(pos, ss, rBeta - 1, rBeta, depth / 2, cutNode); ss->skipNullMove = false; ss->excludedMove = MOVE_NONE; @@ -933,8 +926,8 @@ split_point_start: // At split points actual search starts from here pvMove = PvNode && moveCount == 1; ss->currentMove = move; - if (!SpNode && !captureOrPromotion && playedMoveCount < 64) - movesSearched[playedMoveCount++] = move; + if (!SpNode && !captureOrPromotion && quietCount < 64) + quietsSearched[quietCount++] = move; // Step 14. Make the move pos.do_move(move, st, ci, givesCheck); @@ -950,6 +943,10 @@ split_point_start: // At split points actual search starts from here && move != ss->killers[1]) { ss->reduction = reduction(depth, moveCount); + + if (!PvNode && cutNode) + ss->reduction += ONE_PLY; + if (move == countermoves[0] || move == countermoves[1]) ss->reduction = std::max(DEPTH_ZERO, ss->reduction-ONE_PLY); @@ -957,7 +954,7 @@ split_point_start: // At split points actual search starts from here if (SpNode) alpha = splitPoint->alpha; - value = -search(pos, ss+1, -(alpha+1), -alpha, d); + value = -search(pos, ss+1, -(alpha+1), -alpha, d, true); doFullDepthSearch = (value > alpha && ss->reduction != DEPTH_ZERO); ss->reduction = DEPTH_ZERO; @@ -974,7 +971,7 @@ split_point_start: // At split points actual search starts from here value = newDepth < ONE_PLY ? givesCheck ? -qsearch(pos, ss+1, -(alpha+1), -alpha, DEPTH_ZERO) : -qsearch(pos, ss+1, -(alpha+1), -alpha, DEPTH_ZERO) - : - search(pos, ss+1, -(alpha+1), -alpha, newDepth); + : - search(pos, ss+1, -(alpha+1), -alpha, newDepth, !cutNode); } // Only for PV nodes do a full PV search on the first move or after a fail @@ -984,7 +981,7 @@ split_point_start: // At split points actual search starts from here value = newDepth < ONE_PLY ? givesCheck ? -qsearch(pos, ss+1, -beta, -alpha, DEPTH_ZERO) : -qsearch(pos, ss+1, -beta, -alpha, DEPTH_ZERO) - : - search(pos, ss+1, -beta, -alpha, newDepth); + : - search(pos, ss+1, -beta, -alpha, newDepth, false); // Step 17. Undo move pos.undo_move(move); @@ -1059,7 +1056,7 @@ split_point_start: // At split points actual search starts from here assert(bestValue < beta); thisThread->split(pos, ss, alpha, beta, &bestValue, &bestMove, - depth, threatMove, moveCount, &mp, NT); + depth, threatMove, moveCount, &mp, NT, cutNode); if (bestValue >= beta) break; } @@ -1081,43 +1078,37 @@ split_point_start: // At split points actual search starts from here // If we have pruned all the moves without searching return a fail-low score if (bestValue == -VALUE_INFINITE) - { - assert(!playedMoveCount); - bestValue = alpha; - } - if (bestValue >= beta) // Failed high + TT.store(posKey, value_to_tt(bestValue, ss->ply), + bestValue >= beta ? BOUND_LOWER : + PvNode && bestMove ? BOUND_EXACT : BOUND_UPPER, + depth, bestMove, ss->staticEval, ss->evalMargin); + + // Quiet best move: update killers, history and countermoves + if ( bestValue >= beta + && !pos.is_capture_or_promotion(bestMove) + && !inCheck) { - TT.store(posKey, value_to_tt(bestValue, ss->ply), BOUND_LOWER, depth, - bestMove, ss->staticEval, ss->evalMargin); - - if (!pos.is_capture_or_promotion(bestMove) && !inCheck) + if (ss->killers[0] != bestMove) { - if (bestMove != ss->killers[0]) - { - ss->killers[1] = ss->killers[0]; - ss->killers[0] = bestMove; - } - - // Increase history value of the cut-off move - Value bonus = Value(int(depth) * int(depth)); - History.update(pos.piece_moved(bestMove), to_sq(bestMove), bonus); - if (is_ok((ss-1)->currentMove)) - Countermoves.update(pos.piece_on(prevMoveSq), prevMoveSq, bestMove); + ss->killers[1] = ss->killers[0]; + ss->killers[0] = bestMove; + } - // Decrease history of all the other played non-capture moves - for (int i = 0; i < playedMoveCount - 1; i++) - { - Move m = movesSearched[i]; - History.update(pos.piece_moved(m), to_sq(m), -bonus); - } + // Increase history value of the cut-off move and decrease all the other + // played non-capture moves. + Value bonus = Value(int(depth) * int(depth)); + History.update(pos.piece_moved(bestMove), to_sq(bestMove), bonus); + for (int i = 0; i < quietCount - 1; i++) + { + Move m = quietsSearched[i]; + History.update(pos.piece_moved(m), to_sq(m), -bonus); } + + if (is_ok((ss-1)->currentMove)) + Countermoves.update(pos.piece_on(prevMoveSq), prevMoveSq, bestMove); } - else // Failed low or PV search - TT.store(posKey, value_to_tt(bestValue, ss->ply), - PvNode && bestMove != MOVE_NONE ? BOUND_EXACT : BOUND_UPPER, - depth, bestMove, ss->staticEval, ss->evalMargin); assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); @@ -1175,9 +1166,9 @@ split_point_start: // At split points actual search starts from here if ( tte && tte->depth() >= ttDepth && ttValue != VALUE_NONE // Only in case of TT access race - && ( PvNode ? tte->type() == BOUND_EXACT - : ttValue >= beta ? (tte->type() & BOUND_LOWER) - : (tte->type() & BOUND_UPPER))) + && ( PvNode ? tte->bound() == BOUND_EXACT + : ttValue >= beta ? (tte->bound() & BOUND_LOWER) + : (tte->bound() & BOUND_UPPER))) { ss->currentMove = ttMove; // Can be MOVE_NONE return ttValue; @@ -1467,15 +1458,15 @@ split_point_start: // At split points actual search starts from here { // Update occupancy as if the piece and the threat are moving Bitboard occ = pos.pieces() ^ m1from ^ m1to ^ m2from; - Piece piece = pos.piece_on(m1from); + Piece pc = pos.piece_on(m1from); // The moved piece attacks the square 'tto' ? - if (pos.attacks_from(piece, m1to, occ) & m2to) + if (pos.attacks_from(pc, m1to, occ) & m2to) return true; // Scan for possible X-ray attackers behind the moved piece - Bitboard xray = (attacks_bb< ROOK>(m2to, occ) & pos.pieces(color_of(piece), QUEEN, ROOK)) - | (attacks_bb(m2to, occ) & pos.pieces(color_of(piece), QUEEN, BISHOP)); + Bitboard xray = (attacks_bb< ROOK>(m2to, occ) & pos.pieces(color_of(pc), QUEEN, ROOK)) + | (attacks_bb(m2to, occ) & pos.pieces(color_of(pc), QUEEN, BISHOP)); // Verify attackers are triggered by our move and not already existing if (xray && (xray ^ (xray & pos.attacks_from(m2to)))) @@ -1539,7 +1530,7 @@ split_point_start: // At split points actual search starts from here string uci_pv(const Position& pos, int depth, Value alpha, Value beta) { std::stringstream s; - Time::point elaspsed = Time::now() - SearchTime + 1; + Time::point elapsed = Time::now() - SearchTime + 1; size_t uciPVSize = std::min((size_t)Options["MultiPV"], RootMoves.size()); int selDepth = 0; @@ -1564,8 +1555,8 @@ split_point_start: // At split points actual search starts from here << " seldepth " << selDepth << " score " << (i == PVIdx ? score_to_uci(v, alpha, beta) : score_to_uci(v)) << " nodes " << pos.nodes_searched() - << " nps " << pos.nodes_searched() * 1000 / elaspsed - << " time " << elaspsed + << " nps " << pos.nodes_searched() * 1000 / elapsed + << " time " << elapsed << " multipv " << i + 1 << " pv"; @@ -1587,7 +1578,7 @@ split_point_start: // At split points actual search starts from here void RootMove::extract_pv_from_tt(Position& pos) { StateInfo state[MAX_PLY_PLUS_2], *st = state; - TTEntry* tte; + const TTEntry* tte; int ply = 0; Move m = pv[0]; @@ -1620,7 +1611,7 @@ void RootMove::extract_pv_from_tt(Position& pos) { void RootMove::insert_pv_in_tt(Position& pos) { StateInfo state[MAX_PLY_PLUS_2], *st = state; - TTEntry* tte; + const TTEntry* tte; int ply = 0; do { @@ -1693,11 +1684,11 @@ void Thread::idle_loop() { Threads.mutex.unlock(); - Stack ss[MAX_PLY_PLUS_2]; + Stack stack[MAX_PLY_PLUS_2], *ss = stack+1; // To allow referencing (ss-1) Position pos(*sp->pos, this); - memcpy(ss, sp->ss - 1, 4 * sizeof(Stack)); - (ss+1)->splitPoint = sp; + memcpy(ss-1, sp->ss-1, 4 * sizeof(Stack)); + ss->splitPoint = sp; sp->mutex.lock(); @@ -1707,13 +1698,13 @@ void Thread::idle_loop() { switch (sp->nodeType) { case Root: - search(pos, ss+1, sp->alpha, sp->beta, sp->depth); + search(pos, ss, sp->alpha, sp->beta, sp->depth, sp->cutNode); break; case PV: - search(pos, ss+1, sp->alpha, sp->beta, sp->depth); + search(pos, ss, sp->alpha, sp->beta, sp->depth, sp->cutNode); break; case NonPV: - search(pos, ss+1, sp->alpha, sp->beta, sp->depth); + search(pos, ss, sp->alpha, sp->beta, sp->depth, sp->cutNode); break; default: assert(false);