X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=86a8defd53898aa49de8ce1eefd1f9b12b64075d;hp=c7bc8d1752f8c15e18ecf43baf1d3e0ae8f329d5;hb=78908b7aed41ba0a70c557182ab1b27792db9b0c;hpb=0759d8f4302d0ad262a2dabca465f1618677aeba diff --git a/src/search.cpp b/src/search.cpp index c7bc8d17..86a8defd 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -1,7 +1,7 @@ /* Stockfish, a UCI chess playing engine derived from Glaurung 2.1 Copyright (C) 2004-2008 Tord Romstad (Glaurung author) - Copyright (C) 2008-2010 Marco Costalba, Joona Kiiski, Tord Romstad + Copyright (C) 2008-2012 Marco Costalba, Joona Kiiski, Tord Romstad Stockfish is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by @@ -67,7 +67,6 @@ namespace { RootMove(){} RootMove(Move m) { - nodes = 0; score = prevScore = -VALUE_INFINITE; pv.push_back(m); pv.push_back(MOVE_NONE); @@ -79,7 +78,6 @@ namespace { void extract_pv_from_tt(Position& pos); void insert_pv_in_tt(Position& pos); - int64_t nodes; Value score; Value prevScore; std::vector pv; @@ -141,6 +139,9 @@ namespace { // better than the second best move. const Value EasyMoveMargin = Value(0x150); + // This is the minimum interval in msec between two check_time() calls + const int TimerResolution = 5; + /// Namespace variables @@ -199,19 +200,19 @@ namespace { FORCE_INLINE bool is_dangerous(const Position& pos, Move m, bool captureOrPromotion) { // Test for a pawn pushed to 7th or a passed pawn move - if (type_of(pos.piece_on(move_from(m))) == PAWN) + if (type_of(pos.piece_moved(m)) == PAWN) { Color c = pos.side_to_move(); - if ( relative_rank(c, move_to(m)) == RANK_7 - || pos.pawn_is_passed(c, move_to(m))) + if ( relative_rank(c, to_sq(m)) == RANK_7 + || pos.pawn_is_passed(c, to_sq(m))) return true; } // Test for a capture that triggers a pawn endgame if ( captureOrPromotion - && type_of(pos.piece_on(move_to(m))) != PAWN + && type_of(pos.piece_on(to_sq(m))) != PAWN && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK) - - PieceValueMidgame[pos.piece_on(move_to(m))] == VALUE_ZERO) + - PieceValueMidgame[pos.piece_on(to_sq(m))] == VALUE_ZERO) && !is_special(m)) return true; @@ -254,22 +255,22 @@ void Search::init() { int64_t Search::perft(Position& pos, Depth depth) { StateInfo st; - int64_t sum = 0; + int64_t cnt = 0; MoveList ml(pos); // At the last ply just return the number of moves (leaf nodes) - if (depth <= ONE_PLY) + if (depth == ONE_PLY) return ml.size(); CheckInfo ci(pos); for ( ; !ml.end(); ++ml) { pos.do_move(ml.move(), st, ci, pos.move_gives_check(ml.move(), ci)); - sum += perft(pos, depth - ONE_PLY); + cnt += perft(pos, depth - ONE_PLY); pos.undo_move(ml.move()); } - return sum; + return cnt; } @@ -292,22 +293,17 @@ void Search::think() { // Populate RootMoves with all the legal moves (default) or, if a SearchMoves // is given, with the subset of legal moves to search. for (MoveList ml(pos); !ml.end(); ++ml) - if ( SearchMoves.empty() - || count(SearchMoves.begin(), SearchMoves.end(), ml.move())) + if (SearchMoves.empty() || count(SearchMoves.begin(), SearchMoves.end(), ml.move())) RootMoves.push_back(RootMove(ml.move())); if (Options["OwnBook"]) { - if (book.name() != (string)Options["Book File"]) - book.open(Options["Book File"]); - - Move bookMove = book.probe(pos, Options["Best Book Move"]); + Move bookMove = book.probe(pos, Options["Book File"], Options["Best Book Move"]); - if ( bookMove != MOVE_NONE - && count(RootMoves.begin(), RootMoves.end(), bookMove)) + if (bookMove && count(RootMoves.begin(), RootMoves.end(), bookMove)) { std::swap(RootMoves[0], *find(RootMoves.begin(), RootMoves.end(), bookMove)); - goto finish; + goto finalize; } } @@ -350,8 +346,8 @@ void Search::think() { // Set best timer interval to avoid lagging under time pressure. Timer is // used to check for remaining available thinking time. - if (TimeMgr.available_time()) - Threads.set_timer(std::min(100, std::max(TimeMgr.available_time() / 8, 20))); + if (Limits.use_time_management()) + Threads.set_timer(std::min(100, std::max(TimeMgr.available_time() / 16, TimerResolution))); else Threads.set_timer(100); @@ -377,7 +373,7 @@ void Search::think() { pos.undo_move(RootMoves[0].pv[0]); } -finish: +finalize: // When we reach max depth we arrive here even without a StopRequest, but if // we are pondering or in infinite search, we shouldn't print the best move @@ -399,7 +395,7 @@ namespace { void id_loop(Position& pos) { - Stack ss[PLY_MAX_PLUS_2]; + Stack ss[MAX_PLY_PLUS_2]; int depth, prevBestMoveChanges; Value bestValue, alpha, beta, delta; bool bestMoveNeverChanged = true; @@ -421,7 +417,7 @@ namespace { } // Iterative deepening loop until requested to stop or target depth reached - while (!Signals.stop && ++depth <= PLY_MAX && (!Limits.maxDepth || depth <= Limits.maxDepth)) + while (!Signals.stop && ++depth <= MAX_PLY && (!Limits.maxDepth || depth <= Limits.maxDepth)) { // Save last iteration's scores before first PV line is searched and all // the move scores but the (new) PV are set to -VALUE_INFINITE. @@ -520,7 +516,7 @@ namespace { bestMoveNeverChanged = false; // Do we have time for the next iteration? Can we stop searching now? - if (!Signals.stop && !Signals.stopOnPonderhit && Limits.useTimeManagement()) + if (!Signals.stop && !Signals.stopOnPonderhit && Limits.use_time_management()) { bool stop = false; // Local variable, not the volatile Signals.stop @@ -535,15 +531,15 @@ namespace { stop = true; // Stop search early if one move seems to be much better than others - if ( depth >= 10 + if ( depth >= 12 && !stop - && ( bestMoveNeverChanged + && ( (bestMoveNeverChanged && pos.captured_piece_type()) || elapsed_time() > (TimeMgr.available_time() * 40) / 100)) { Value rBeta = bestValue - EasyMoveMargin; (ss+1)->excludedMove = RootMoves[0].pv[0]; (ss+1)->skipNullMove = true; - Value v = search(pos, ss+1, rBeta - 1, rBeta, (depth * ONE_PLY) / 2); + Value v = search(pos, ss+1, rBeta - 1, rBeta, (depth - 3) * ONE_PLY); (ss+1)->skipNullMove = false; (ss+1)->excludedMove = MOVE_NONE; @@ -594,7 +590,6 @@ namespace { assert(pos.thread() >= 0 && pos.thread() < Threads.size()); Move movesSearched[MAX_MOVES]; - int64_t nodes; StateInfo st; const TTEntry *tte; Key posKey; @@ -637,7 +632,7 @@ namespace { // Step 2. Check for aborted search and immediate draw if (( Signals.stop || pos.is_draw() - || ss->ply > PLY_MAX) && !RootNode) + || ss->ply > MAX_PLY) && !RootNode) return VALUE_DRAW; // Step 3. Mate distance pruning. Even if we mate at the next move our score @@ -706,10 +701,10 @@ namespace { if ( (move = (ss-1)->currentMove) != MOVE_NULL && (ss-1)->eval != VALUE_NONE && ss->eval != VALUE_NONE - && pos.captured_piece_type() == NO_PIECE_TYPE + && !pos.captured_piece_type() && !is_special(move)) { - Square to = move_to(move); + Square to = to_sq(move); H.update_gain(pos.piece_on(to), to, -(ss-1)->eval - ss->eval); } @@ -719,7 +714,7 @@ namespace { && !inCheck && refinedValue + razor_margin(depth) < beta && ttMove == MOVE_NONE - && abs(beta) < VALUE_MATE_IN_PLY_MAX + && abs(beta) < VALUE_MATE_IN_MAX_PLY && !pos.has_pawn_on_7th(pos.side_to_move())) { Value rbeta = beta - razor_margin(depth); @@ -738,7 +733,7 @@ namespace { && depth < RazorDepth && !inCheck && refinedValue - futility_margin(depth, 0) >= beta - && abs(beta) < VALUE_MATE_IN_PLY_MAX + && abs(beta) < VALUE_MATE_IN_MAX_PLY && pos.non_pawn_material(pos.side_to_move())) return refinedValue - futility_margin(depth, 0); @@ -748,7 +743,7 @@ namespace { && depth > ONE_PLY && !inCheck && refinedValue >= beta - && abs(beta) < VALUE_MATE_IN_PLY_MAX + && abs(beta) < VALUE_MATE_IN_MAX_PLY && pos.non_pawn_material(pos.side_to_move())) { ss->currentMove = MOVE_NULL; @@ -770,7 +765,7 @@ namespace { if (nullValue >= beta) { // Do not return unproven mate scores - if (nullValue >= VALUE_MATE_IN_PLY_MAX) + if (nullValue >= VALUE_MATE_IN_MAX_PLY) nullValue = beta; if (depth < 6 * ONE_PLY) @@ -811,7 +806,7 @@ namespace { && !inCheck && !ss->skipNullMove && excludedMove == MOVE_NONE - && abs(beta) < VALUE_MATE_IN_PLY_MAX) + && abs(beta) < VALUE_MATE_IN_MAX_PLY) { Value rbeta = beta + 200; Depth rdepth = depth - ONE_PLY - 3 * ONE_PLY; @@ -873,7 +868,8 @@ split_point_start: // At split points actual search starts from here // Loop through all pseudo-legal moves until no moves remain or a beta cutoff occurs while ( bestValue < beta && (move = mp.next_move()) != MOVE_NONE - && !thread.cutoff_occurred()) + && !thread.cutoff_occurred() + && !Signals.stop) { assert(is_ok(move)); @@ -901,7 +897,6 @@ split_point_start: // At split points actual search starts from here if (RootNode) { Signals.firstRootMove = (moveCount == 1); - nodes = pos.nodes_searched(); if (pos.thread() == 0 && elapsed_time() > 2000) cout << "info depth " << depth / ONE_PLY @@ -958,7 +953,7 @@ split_point_start: // At split points actual search starts from here && !dangerous && move != ttMove && !is_castle(move) - && (bestValue > VALUE_MATED_IN_PLY_MAX || bestValue == -VALUE_INFINITE)) + && (bestValue > VALUE_MATED_IN_MAX_PLY || bestValue == -VALUE_INFINITE)) { // Move count based pruning if ( moveCount >= futility_move_count(depth) @@ -975,7 +970,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 = futilityBase + futility_margin(predictedDepth, moveCount) - + H.gain(pos.piece_on(move_from(move)), move_to(move)); + + H.gain(pos.piece_moved(move), to_sq(move)); if (futilityValue < beta) { @@ -1068,7 +1063,6 @@ split_point_start: // At split points actual search starts from here if (RootNode && !Signals.stop) { RootMove& rm = *find(RootMoves.begin(), RootMoves.end(), move); - rm.nodes += pos.nodes_searched() - nodes; // PV move or new best move ? if (isPvMove || value > alpha) @@ -1160,13 +1154,13 @@ 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)); - H.add(pos.piece_on(move_from(move)), move_to(move), bonus); + H.add(pos.piece_moved(move), to_sq(move), bonus); // Decrease history of all the other played non-capture moves for (int i = 0; i < playedMoveCount - 1; i++) { Move m = movesSearched[i]; - H.add(pos.piece_on(move_from(m)), move_to(m), -bonus); + H.add(pos.piece_moved(m), to_sq(m), -bonus); } } } @@ -1213,7 +1207,7 @@ split_point_start: // At split points actual search starts from here ss->ply = (ss-1)->ply + 1; // Check for an instant draw or maximum ply reached - if (pos.is_draw() || ss->ply > PLY_MAX) + if (pos.is_draw() || ss->ply > MAX_PLY) return VALUE_DRAW; // Decide whether or not to include checks, this fixes also the type of @@ -1272,7 +1266,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, H, move_to((ss-1)->currentMove)); + MovePicker mp(pos, ttMove, depth, H, to_sq((ss-1)->currentMove)); CheckInfo ci(pos); // Loop through the moves until no moves remain or a beta cutoff occurs @@ -1293,7 +1287,7 @@ split_point_start: // At split points actual search starts from here && !pos.is_passed_pawn_push(move)) { futilityValue = futilityBase - + PieceValueEndgame[pos.piece_on(move_to(move))] + + PieceValueEndgame[pos.piece_on(to_sq(move))] + (is_enpassant(move) ? PawnValueEndgame : VALUE_ZERO); if (futilityValue < beta) @@ -1314,7 +1308,7 @@ split_point_start: // At split points actual search starts from here // Detect non-capture evasions that are candidate to be pruned evasionPrunable = !PvNode && inCheck - && bestValue > VALUE_MATED_IN_PLY_MAX + && bestValue > VALUE_MATED_IN_MAX_PLY && !pos.is_capture(move) && !pos.can_castle(pos.side_to_move()); @@ -1397,9 +1391,9 @@ split_point_start: // At split points actual search starts from here Color them; Value futilityValue, bv = *bestValue; - from = move_from(move); - to = move_to(move); - them = flip(pos.side_to_move()); + from = from_sq(move); + to = to_sq(move); + them = ~pos.side_to_move(); ksq = pos.king_square(them); kingAtt = pos.attacks_from(ksq); pc = pos.piece_on(from); @@ -1458,14 +1452,14 @@ split_point_start: // At split points actual search starts from here assert(is_ok(m2)); // Case 1: The moving piece is the same in both moves - f2 = move_from(m2); - t1 = move_to(m1); + f2 = from_sq(m2); + t1 = to_sq(m1); if (f2 == t1) return true; // Case 2: The destination square for m2 was vacated by m1 - t2 = move_to(m2); - f1 = move_from(m1); + t2 = to_sq(m2); + f1 = from_sq(m1); if (t2 == f1) return true; @@ -1500,10 +1494,10 @@ split_point_start: // At split points actual search starts from here Value value_to_tt(Value v, int ply) { - if (v >= VALUE_MATE_IN_PLY_MAX) + if (v >= VALUE_MATE_IN_MAX_PLY) return v + ply; - if (v <= VALUE_MATED_IN_PLY_MAX) + if (v <= VALUE_MATED_IN_MAX_PLY) return v - ply; return v; @@ -1516,10 +1510,10 @@ split_point_start: // At split points actual search starts from here Value value_from_tt(Value v, int ply) { - if (v >= VALUE_MATE_IN_PLY_MAX) + if (v >= VALUE_MATE_IN_MAX_PLY) return v - ply; - if (v <= VALUE_MATED_IN_PLY_MAX) + if (v <= VALUE_MATED_IN_MAX_PLY) return v + ply; return v; @@ -1538,10 +1532,10 @@ split_point_start: // At split points actual search starts from here Square mfrom, mto, tfrom, tto; - mfrom = move_from(m); - mto = move_to(m); - tfrom = move_from(threat); - tto = move_to(threat); + mfrom = from_sq(m); + mto = to_sq(m); + tfrom = from_sq(threat); + tto = to_sq(threat); // Case 1: Don't prune moves which move the threatened piece if (mfrom == tto) @@ -1574,8 +1568,8 @@ split_point_start: // At split points actual search starts from here Value v = value_from_tt(tte->value(), ply); return ( tte->depth() >= depth - || v >= std::max(VALUE_MATE_IN_PLY_MAX, beta) - || v < std::min(VALUE_MATED_IN_PLY_MAX, beta)) + || v >= std::max(VALUE_MATE_IN_MAX_PLY, beta) + || v < std::min(VALUE_MATED_IN_MAX_PLY, beta)) && ( ((tte->type() & VALUE_TYPE_LOWER) && v >= beta) || ((tte->type() & VALUE_TYPE_UPPER) && v < beta)); @@ -1624,7 +1618,7 @@ split_point_start: // At split points actual search starts from here std::stringstream s; - if (abs(v) < VALUE_MATE_IN_PLY_MAX) + if (abs(v) < VALUE_MATE_IN_MAX_PLY) s << "cp " << v * 100 / int(PawnValueMidgame); else s << "mate " << (v > 0 ? VALUE_MATE - v + 1 : -VALUE_MATE - v) / 2; @@ -1701,9 +1695,9 @@ split_point_start: // At split points actual search starts from here std::stringstream s; - if (v >= VALUE_MATE_IN_PLY_MAX) + if (v >= VALUE_MATE_IN_MAX_PLY) s << "#" << (VALUE_MATE - v + 1) / 2; - else if (v <= VALUE_MATED_IN_PLY_MAX) + else if (v <= VALUE_MATED_IN_MAX_PLY) s << "-#" << (VALUE_MATE + v) / 2; else s << std::setprecision(2) << std::fixed << std::showpos @@ -1717,7 +1711,7 @@ split_point_start: // At split points actual search starts from here const int64_t K = 1000; const int64_t M = 1000000; - StateInfo state[PLY_MAX_PLUS_2], *st = state; + StateInfo state[MAX_PLY_PLUS_2], *st = state; Move* m = pv; string san, padding; size_t length; @@ -1815,7 +1809,7 @@ split_point_start: // At split points actual search starts from here void RootMove::extract_pv_from_tt(Position& pos) { - StateInfo state[PLY_MAX_PLUS_2], *st = state; + StateInfo state[MAX_PLY_PLUS_2], *st = state; TTEntry* tte; int ply = 1; Move m = pv[0]; @@ -1830,7 +1824,7 @@ split_point_start: // At split points actual search starts from here && tte->move() != MOVE_NONE && pos.is_pseudo_legal(tte->move()) && pos.pl_move_is_legal(tte->move(), pos.pinned_pieces()) - && ply < PLY_MAX + && ply < MAX_PLY && (!pos.is_draw() || ply < 2)) { pv.push_back(tte->move()); @@ -1849,7 +1843,7 @@ split_point_start: // At split points actual search starts from here void RootMove::insert_pv_in_tt(Position& pos) { - StateInfo state[PLY_MAX_PLUS_2], *st = state; + StateInfo state[MAX_PLY_PLUS_2], *st = state; TTEntry* tte; Key k; Value v, m = VALUE_NONE; @@ -1925,7 +1919,7 @@ void Thread::idle_loop(SplitPoint* sp) { assert(!do_terminate); // Copy split point position and search stack and call search() - Stack ss[PLY_MAX_PLUS_2]; + Stack ss[MAX_PLY_PLUS_2]; SplitPoint* tsp = splitPoint; Position pos(*tsp->pos, threadID); @@ -1967,11 +1961,11 @@ void Thread::idle_loop(SplitPoint* sp) { } -/// do_timer_event() is called by the timer thread when the timer triggers. It -/// is used to print debug info and, more important, to detect when we are out of +/// check_time() is called by the timer thread when the timer triggers. It is +/// used to print debug info and, more important, to detect when we are out of /// available time and so stop the search. -void do_timer_event() { +void check_time() { static int lastInfoTime; int e = elapsed_time(); @@ -1979,9 +1973,7 @@ void do_timer_event() { if (system_time() - lastInfoTime >= 1000 || !lastInfoTime) { lastInfoTime = system_time(); - - dbg_print_mean(); - dbg_print_hit_rate(); + dbg_print(); } if (Limits.ponder) @@ -1991,10 +1983,10 @@ void do_timer_event() { && !Signals.failedLowAtRoot && e > TimeMgr.available_time(); - bool noMoreTime = e > TimeMgr.maximum_time() + bool noMoreTime = e > TimeMgr.maximum_time() - 2 * TimerResolution || stillAtFirstMove; - if ( (Limits.useTimeManagement() && noMoreTime) + if ( (Limits.use_time_management() && noMoreTime) || (Limits.maxTime && e >= Limits.maxTime) /* missing nodes limit */ ) // FIXME Signals.stop = true;