X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=a10e1180c344a3af45a23bf293386d27cc48ddbf;hp=0e68178147c7b2cbba34845c89e57218e6ea9b86;hb=4bebb15e9426ec80ee50d016a812a49a36dd82bd;hpb=289a767ab3a683a6f2aed74b738ceb87bb632466 diff --git a/src/search.cpp b/src/search.cpp index 0e681781..a10e1180 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -86,11 +86,12 @@ namespace { TimeManager TimeMgr; int BestMoveChanges; Value DrawValue[COLOR_NB]; - History Hist; - Gains Gain; + HistoryStats History; + GainsStats Gains; + 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); @@ -145,7 +146,7 @@ void Search::init() { // Init futility move count array for (d = 0; d < 32; d++) - FutilityMoveCounts[d] = int(3.001 + 0.25 * pow(double(d), 2.0)); + FutilityMoveCounts[d] = int(3.001 + 0.3 * pow(double(d), 1.8)); } @@ -162,11 +163,11 @@ size_t Search::perft(Position& pos, Depth depth) { size_t cnt = 0; CheckInfo ci(pos); - for (MoveList ml(pos); !ml.end(); ++ml) + for (MoveList it(pos); *it; ++it) { - pos.do_move(ml.move(), st, ci, pos.move_gives_check(ml.move(), ci)); + pos.do_move(*it, st, ci, pos.move_gives_check(*it, ci)); cnt += perft(pos, depth - ONE_PLY); - pos.undo_move(ml.move()); + pos.undo_move(*it); } return cnt; @@ -264,6 +265,10 @@ void Search::think() { finalize: + // When search is stopped this info is not printed + sync_cout << "info nodes " << RootPos.nodes_searched() + << " time " << Time::now() - SearchTime + 1 << sync_endl; + // When we reach max depth we arrive here even without Signals.stop is raised, // but if we are pondering or in infinite search, according to UCI protocol, // we shouldn't print the best move before the GUI sends a "stop" or "ponderhit" @@ -290,17 +295,18 @@ 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(); - Hist.clear(); - Gain.clear(); + History.clear(); + Gains.clear(); + Countermoves.clear(); PVSize = Options["MultiPV"]; Skill skill(Options["Skill Level"]); @@ -343,9 +349,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 @@ -410,8 +414,12 @@ namespace { if (Options["Use Search Log"]) { + RootMove& rm = RootMoves[0]; + if (skill.best != MOVE_NONE) + rm = *std::find(RootMoves.begin(), RootMoves.end(), skill.best); + Log log(Options["Search Log Filename"]); - log << pretty_pv(pos, depth, bestValue, Time::now() - SearchTime, &RootMoves[0].pv[0]) + log << pretty_pv(pos, depth, rm.score, Time::now() - SearchTime, &rm.pv[0]) << std::endl; } @@ -445,11 +453,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; @@ -477,7 +485,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); @@ -523,6 +531,7 @@ namespace { bestValue = -VALUE_INFINITE; ss->currentMove = threatMove = (ss+1)->excludedMove = bestMove = MOVE_NONE; ss->ply = (ss-1)->ply + 1; + ss->futilityMoveCount = 0; (ss+1)->skipNullMove = false; (ss+1)->reduction = DEPTH_ZERO; (ss+2)->killers[0] = (ss+2)->killers[1] = MOVE_NONE; @@ -616,7 +625,7 @@ namespace { && type_of(move) == NORMAL) { Square to = to_sq(move); - Gain.update(pos.piece_on(to), to, -(ss-1)->staticEval - ss->staticEval); + Gains.update(pos.piece_on(to), to, -(ss-1)->staticEval - ss->staticEval); } // Step 6. Razoring (is omitted in PV nodes) @@ -645,6 +654,7 @@ namespace { && !inCheck && eval - futility_margin(depth, (ss-1)->futilityMoveCount) >= beta && abs(beta) < VALUE_MATE_IN_MAX_PLY + && abs(eval) < VALUE_KNOWN_WIN && pos.non_pawn_material(pos.side_to_move())) return eval - futility_margin(depth, (ss-1)->futilityMoveCount); @@ -669,7 +679,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(); @@ -684,7 +694,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) @@ -704,7 +714,7 @@ namespace { && (ss-1)->reduction && threatMove != MOVE_NONE && allows(pos, (ss-1)->currentMove, threatMove)) - return beta - 1; + return alpha; } } @@ -726,7 +736,7 @@ namespace { assert((ss-1)->currentMove != MOVE_NONE); assert((ss-1)->currentMove != MOVE_NULL); - MovePicker mp(pos, ttMove, Hist, pos.captured_piece_type()); + MovePicker mp(pos, ttMove, History, pos.captured_piece_type()); CheckInfo ci(pos); while ((move = mp.next_move()) != MOVE_NONE) @@ -734,7 +744,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; @@ -749,7 +759,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); @@ -758,7 +768,11 @@ namespace { split_point_start: // At split points actual search starts from here - MovePicker mp(pos, ttMove, depth, Hist, ss, PvNode ? -VALUE_INFINITE : beta); + Square prevMoveSq = to_sq((ss-1)->currentMove); + Move countermoves[] = { Countermoves[pos.piece_on(prevMoveSq)][prevMoveSq].first, + Countermoves[pos.piece_on(prevMoveSq)][prevMoveSq].second }; + + MovePicker mp(pos, ttMove, depth, History, countermoves, ss, PvNode ? -VALUE_INFINITE : beta); CheckInfo ci(pos); value = bestValue; // Workaround a bogus 'uninitialized' warning under gcc singularExtensionNode = !RootNode @@ -806,7 +820,6 @@ split_point_start: // At split points actual search starts from here << " currmovenumber " << moveCount + PVIdx << sync_endl; } - ss->futilityMoveCount = 0; ext = DEPTH_ZERO; captureOrPromotion = pos.is_capture_or_promotion(move); givesCheck = pos.move_gives_check(move, ci); @@ -842,7 +855,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; @@ -877,7 +890,7 @@ split_point_start: // At split points actual search starts from here // but fixing this made program slightly weaker. Depth predictedDepth = newDepth - reduction(depth, moveCount); futilityValue = ss->staticEval + ss->evalMargin + futility_margin(predictedDepth, moveCount) - + Gain[pos.piece_moved(move)][to_sq(move)]; + + Gains[pos.piece_moved(move)][to_sq(move)]; if (futilityValue < beta) { @@ -906,6 +919,8 @@ split_point_start: // At split points actual search starts from here // far in the move list we are to be more aggressive in the child node. ss->futilityMoveCount = moveCount; } + else + ss->futilityMoveCount = 0; // Check for legality only before to do the move if (!RootNode && !SpNode && !pos.pl_move_is_legal(move, ci.pinned)) @@ -933,11 +948,18 @@ 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); + Depth d = std::max(newDepth - ss->reduction, ONE_PLY); 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; @@ -954,7 +976,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 @@ -964,7 +986,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); @@ -1039,7 +1061,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; } @@ -1082,13 +1104,15 @@ split_point_start: // At split points actual search starts from here // Increase history value of the cut-off move Value bonus = Value(int(depth) * int(depth)); - Hist.update(pos.piece_moved(bestMove), to_sq(bestMove), bonus); + History.update(pos.piece_moved(bestMove), to_sq(bestMove), bonus); + if (is_ok((ss-1)->currentMove)) + Countermoves.update(pos.piece_on(prevMoveSq), prevMoveSq, bestMove); // Decrease history of all the other played non-capture moves for (int i = 0; i < playedMoveCount - 1; i++) { Move m = movesSearched[i]; - Hist.update(pos.piece_moved(m), to_sq(m), -bonus); + History.update(pos.piece_moved(m), to_sq(m), -bonus); } } } @@ -1201,7 +1225,7 @@ split_point_start: // At split points actual search starts from here // to search the moves. Because the depth is <= 0 here, only captures, // queen promotions and checks (only if depth >= DEPTH_QS_CHECKS) will // be generated. - MovePicker mp(pos, ttMove, depth, Hist, to_sq((ss-1)->currentMove)); + MovePicker mp(pos, ttMove, depth, History, to_sq((ss-1)->currentMove)); CheckInfo ci(pos); // Loop through the moves until no moves remain or a beta cutoff occurs @@ -1233,7 +1257,6 @@ split_point_start: // At split points actual search starts from here // Prune moves with negative or equal SEE and also moves with positive // SEE where capturing piece loses a tempo and SEE < beta - futilityBase. if ( futilityBase < beta - && depth < DEPTH_ZERO && pos.see(move, beta - futilityBase) <= 0) { bestValue = std::max(bestValue, futilityBase); @@ -1446,15 +1469,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)))) @@ -1518,7 +1541,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; @@ -1543,8 +1566,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"; @@ -1672,11 +1695,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(); @@ -1686,13 +1709,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);