X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=b235a1e6384d98b56d86be13148334b43d43acb2;hp=c80a064dfde82ba15f1eb98550d9eda5ebf11107;hb=11b1a76f35108316ee37d9d7056f4d621305a7ed;hpb=239d7b3fd144d2b493bb47ea97a436cec8ae5990 diff --git a/src/search.cpp b/src/search.cpp index c80a064d..89ddfef6 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-2012 Marco Costalba, Joona Kiiski, Tord Romstad + Copyright (C) 2008-2013 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 @@ -21,12 +21,12 @@ #include #include #include +#include #include #include #include "book.h" #include "evaluate.h" -#include "history.h" #include "movegen.h" #include "movepick.h" #include "notation.h" @@ -67,7 +67,7 @@ namespace { // Futility lookup tables (initialized at startup) and their access functions Value FutilityMargins[16][64]; // [depth][moveNumber] - int FutilityMoveCounts[32]; // [depth] + int FutilityMoveCounts[2][32]; // [improving][depth] inline Value futility_margin(Depth d, int mn) { @@ -76,21 +76,23 @@ namespace { } // Reduction lookup tables (initialized at startup) and their access function - int8_t Reductions[2][64][64]; // [pv][depth][moveNumber] + int8_t Reductions[2][2][64][64]; // [pv][improving][depth][moveNumber] - template inline Depth reduction(Depth d, int mn) { + template inline Depth reduction(bool i, Depth d, int mn) { - return (Depth) Reductions[PvNode][std::min(int(d) / ONE_PLY, 63)][std::min(mn, 63)]; + return (Depth) Reductions[PvNode][i][std::min(int(d) / ONE_PLY, 63)][std::min(mn, 63)]; } size_t PVSize, PVIdx; TimeManager TimeMgr; int BestMoveChanges; Value DrawValue[COLOR_NB]; - History H; + 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); @@ -98,11 +100,13 @@ namespace { void id_loop(Position& pos); Value value_to_tt(Value v, int ply); Value value_from_tt(Value v, int ply); - bool check_is_dangerous(Position& pos, Move move, Value futilityBase, Value beta); - bool yields_to_threat(const Position& pos, Move move, Move threat); - bool prevents_threat(const Position& pos, Move move, Move threat); + bool check_is_dangerous(const Position& pos, Move move, Value futilityBase, Value beta); + bool allows(const Position& pos, Move first, Move second); + bool refutes(const Position& pos, Move first, Move second); string uci_pv(const Position& pos, int depth, Value alpha, Value beta); + class stop : public std::exception {}; + struct Skill { Skill(int l) : level(l), best(MOVE_NONE) {} ~Skill() { @@ -135,8 +139,14 @@ void Search::init() { { double pvRed = log(double(hd)) * log(double(mc)) / 3.0; double nonPVRed = 0.33 + log(double(hd)) * log(double(mc)) / 2.25; - Reductions[1][hd][mc] = (int8_t) ( pvRed >= 1.0 ? floor( pvRed * int(ONE_PLY)) : 0); - Reductions[0][hd][mc] = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed * int(ONE_PLY)) : 0); + Reductions[1][1][hd][mc] = (int8_t) ( pvRed >= 1.0 ? floor( pvRed * int(ONE_PLY)) : 0); + Reductions[0][1][hd][mc] = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed * int(ONE_PLY)) : 0); + + Reductions[1][0][hd][mc] = Reductions[1][1][hd][mc]; + Reductions[0][0][hd][mc] = Reductions[0][1][hd][mc]; + + if (Reductions[0][0][hd][mc] > 2 * ONE_PLY) + Reductions[0][0][hd][mc] += ONE_PLY; } // Init futility margins array @@ -145,33 +155,36 @@ 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[1][d] = int(3.001 + 0.3 * pow(double(d), 1.8)); + FutilityMoveCounts[0][d] = d < 5 ? FutilityMoveCounts[1][d] + : 3 * FutilityMoveCounts[1][d] / 4; + } } /// Search::perft() is our utility to verify move generation. All the leaf nodes /// up to the given depth are generated and counted and the sum returned. -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(); +static size_t perft(Position& pos, Depth depth) { StateInfo st; size_t cnt = 0; CheckInfo ci(pos); + const bool leaf = depth == 2 * ONE_PLY; - 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)); - cnt += perft(pos, depth - ONE_PLY); - pos.undo_move(ml.move()); + pos.do_move(*it, st, ci, pos.move_gives_check(*it, ci)); + cnt += leaf ? MoveList(pos).size() : ::perft(pos, depth - ONE_PLY); + pos.undo_move(*it); } - return cnt; } +size_t Search::perft(Position& pos, Depth depth) { + return depth > ONE_PLY ? ::perft(pos, depth) : MoveList(pos).size(); +} /// Search::think() is the external interface to Stockfish's search, and is /// called by the main thread when the program receives the UCI 'go' command. It @@ -182,19 +195,19 @@ void Search::think() { static PolyglotBook book; // Defined static to initialize the PRNG only once RootColor = RootPos.side_to_move(); - TimeMgr.init(Limits, RootPos.startpos_ply_counter(), RootColor); + TimeMgr.init(Limits, RootPos.game_ply(), RootColor); if (RootMoves.empty()) { RootMoves.push_back(MOVE_NONE); sync_cout << "info depth 0 score " - << score_to_uci(RootPos.in_check() ? -VALUE_MATE : VALUE_DRAW) + << score_to_uci(RootPos.checkers() ? -VALUE_MATE : VALUE_DRAW) << sync_endl; goto finalize; } - if (Options["OwnBook"] && !Limits.infinite) + if (Options["OwnBook"] && !Limits.infinite && !Limits.mate) { Move bookMove = book.probe(RootPos, Options["Book File"], Options["Best Book Move"]); @@ -208,14 +221,14 @@ void Search::think() { if (Options["Contempt Factor"] && !Options["UCI_AnalyseMode"]) { int cf = Options["Contempt Factor"] * PawnValueMg / 100; // From centipawns - cf = cf * MaterialTable::game_phase(RootPos) / PHASE_MIDGAME; // Scale down with phase + cf = cf * Material::game_phase(RootPos) / PHASE_MIDGAME; // Scale down with phase DrawValue[ RootColor] = VALUE_DRAW - Value(cf); DrawValue[~RootColor] = VALUE_DRAW + Value(cf); } else DrawValue[WHITE] = DrawValue[BLACK] = VALUE_DRAW; - if (Options["Use Search Log"]) + if (Options["Write Search Log"]) { Log log(Options["Search Log Filename"]); log << "\nSearching: " << RootPos.fen() @@ -227,24 +240,27 @@ void Search::think() { << std::endl; } - Threads.wake_up(); + // Reset the threads, still sleeping: will be wake up at split time + for (size_t i = 0; i < Threads.size(); i++) + Threads[i]->maxPly = 0; + + Threads.sleepWhileIdle = Options["Idle Threads Sleep"]; // Set best timer interval to avoid lagging under time pressure. Timer is // used to check for remaining available thinking time. - if (Limits.use_time_management()) - Threads.set_timer(std::min(100, std::max(TimeMgr.available_time() / 16, - TimerResolution))); - else if (Limits.nodes) - Threads.set_timer(2 * TimerResolution); - else - Threads.set_timer(100); + Threads.timer->msec = + Limits.use_time_management() ? std::min(100, std::max(TimeMgr.available_time() / 16, TimerResolution)) : + Limits.nodes ? 2 * TimerResolution + : 100; + + Threads.timer->notify_one(); // Wake up the recurring timer id_loop(RootPos); // Let's start searching ! - Threads.set_timer(0); // Stop timer - Threads.sleep(); + Threads.timer->msec = 0; // Stop the timer + Threads.sleepWhileIdle = true; // Send idle threads to sleep - if (Options["Use Search Log"]) + if (Options["Write Search Log"]) { Time::point elapsed = Time::now() - SearchTime + 1; @@ -261,11 +277,20 @@ 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, we shouldn't print the best - // move before we are told to do so. + // 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" + // command. We simply wait here until GUI sends one of those commands (that + // raise Signals.stop). if (!Signals.stop && (Limits.ponder || Limits.infinite)) - RootPos.this_thread()->wait_for_stop_or_ponderhit(); + { + Signals.stopOnPonderhit = true; + RootPos.this_thread()->wait_for(Signals.stop); + } // Best move could be MOVE_NONE when searching on a stalemate position sync_cout << "bestmove " << move_to_uci(RootMoves[0].pv[0], RootPos.is_chess960()) @@ -282,17 +307,21 @@ namespace { void id_loop(Position& pos) { - Stack ss[MAX_PLY_PLUS_2]; + Stack stack[MAX_PLY_PLUS_3], *ss = stack+2; // To allow referencing (ss-2) int depth, prevBestMoveChanges; Value bestValue, alpha, beta, delta; - bool bestMoveNeverChanged = true; - memset(ss, 0, 4 * sizeof(Stack)); + std::memset(ss-2, 0, 5 * sizeof(Stack)); + (ss-1)->currentMove = MOVE_NULL; // Hack to skip update gains + depth = BestMoveChanges = 0; - bestValue = delta = -VALUE_INFINITE; - ss->currentMove = MOVE_NULL; // Hack to skip update gains + bestValue = delta = alpha = -VALUE_INFINITE; + beta = VALUE_INFINITE; + TT.new_search(); - H.clear(); + History.clear(); + Gains.clear(); + Countermoves.clear(); PVSize = Options["MultiPV"]; Skill skill(Options["Skill Level"]); @@ -318,26 +347,21 @@ namespace { // MultiPV loop. We perform a full root search for each PV line for (PVIdx = 0; PVIdx < PVSize; PVIdx++) { - // Set aspiration window default width - if (depth >= 5 && abs(RootMoves[PVIdx].prevScore) < VALUE_KNOWN_WIN) + // Reset aspiration window starting size + if (depth >= 5) { delta = Value(16); - alpha = RootMoves[PVIdx].prevScore - delta; - beta = RootMoves[PVIdx].prevScore + delta; - } - else - { - alpha = -VALUE_INFINITE; - beta = VALUE_INFINITE; + alpha = std::max(RootMoves[PVIdx].prevScore - delta,-VALUE_INFINITE); + beta = std::min(RootMoves[PVIdx].prevScore + delta, VALUE_INFINITE); } // Start with a small aspiration window and, in case of fail high/low, // 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); + try { + bestValue = search(pos, ss, alpha, beta, depth * ONE_PLY, false); + } catch (stop&) {} // Bring to front the best move. It is critical that sorting is // done with a stable algorithm because all the values but the first @@ -345,7 +369,7 @@ namespace { // we want to keep the same order for all the moves but the new // PV that goes to the front. Note that in case of MultiPV search // the already searched PV lines are preserved. - sort(RootMoves.begin() + PVIdx, RootMoves.end()); + std::stable_sort(RootMoves.begin() + PVIdx, RootMoves.end()); // Write PV back to transposition table in case the relevant // entries have been overwritten during the search. @@ -358,56 +382,59 @@ namespace { if (Signals.stop) return; - // In case of failing high/low increase aspiration window and - // research, otherwise exit the loop. - if (bestValue > alpha && bestValue < beta) - break; - - // Give some update (without cluttering the UI) before to research - if (Time::now() - SearchTime > 3000) + // When failing high/low give some update (without cluttering + // the UI) before to research. + if ( (bestValue <= alpha || bestValue >= beta) + && Time::now() - SearchTime > 3000) sync_cout << uci_pv(pos, depth, alpha, beta) << sync_endl; - if (abs(bestValue) >= VALUE_KNOWN_WIN) + // In case of failing low/high increase aspiration window and + // research, otherwise exit the loop. + if (bestValue <= alpha) { - alpha = -VALUE_INFINITE; - beta = VALUE_INFINITE; + alpha = std::max(bestValue - delta, -VALUE_INFINITE); + + Signals.failedLowAtRoot = true; + Signals.stopOnPonderhit = false; } else if (bestValue >= beta) - { - beta += delta; - delta += delta / 2; - } + beta = std::min(bestValue + delta, VALUE_INFINITE); + else - { - Signals.failedLowAtRoot = true; - Signals.stopOnPonderhit = false; + break; - alpha -= delta; - delta += delta / 2; - } + delta += delta / 2; assert(alpha >= -VALUE_INFINITE && beta <= VALUE_INFINITE); } // Sort the PV lines searched so far and update the GUI - sort(RootMoves.begin(), RootMoves.begin() + PVIdx + 1); - sync_cout << uci_pv(pos, depth, alpha, beta) << sync_endl; + std::stable_sort(RootMoves.begin(), RootMoves.begin() + PVIdx + 1); + + if (PVIdx + 1 == PVSize || Time::now() - SearchTime > 3000) + sync_cout << uci_pv(pos, depth, alpha, beta) << sync_endl; } // Do we need to pick now the sub-optimal best move ? if (skill.enabled() && skill.time_to_pick(depth)) skill.pick_move(); - if (Options["Use Search Log"]) + if (Options["Write 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; } - // Filter out startup noise when monitoring best move stability - if (depth > 2 && BestMoveChanges) - bestMoveNeverChanged = false; + // Do we have found a "mate in x"? + if ( Limits.mate + && bestValue >= VALUE_MATE_IN_MAX_PLY + && VALUE_MATE - bestValue <= 2 * Limits.mate) + Signals.stop = true; // Do we have time for the next iteration? Can we stop searching now? if (Limits.use_time_management() && !Signals.stopOnPonderhit) @@ -428,15 +455,16 @@ namespace { if ( depth >= 12 && !stop && PVSize == 1 - && ( (bestMoveNeverChanged && pos.captured_piece_type()) - || Time::now() - SearchTime > (TimeMgr.available_time() * 40) / 100)) + && bestValue > VALUE_MATED_IN_MAX_PLY + && ( RootMoves.size() == 1 + || 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; @@ -464,7 +492,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); @@ -474,42 +502,43 @@ namespace { assert(PvNode || (alpha == beta - 1)); assert(depth > DEPTH_ZERO); - Move movesSearched[64]; + Move quietsSearched[64]; StateInfo st; const TTEntry *tte; - SplitPoint* sp; + SplitPoint* splitPoint; Key posKey; Move ttMove, move, excludedMove, bestMove, threatMove; Depth ext, newDepth; Value bestValue, value, ttValue; Value eval, nullValue, futilityValue; - bool inCheck, givesCheck, pvMove, singularExtensionNode; + bool inCheck, givesCheck, pvMove, singularExtensionNode, improving; bool captureOrPromotion, dangerous, doFullDepthSearch; - int moveCount, playedMoveCount; + int moveCount, quietCount; // Step 1. Initialize node Thread* thisThread = pos.this_thread(); - moveCount = playedMoveCount = 0; - inCheck = pos.in_check(); + inCheck = pos.checkers(); if (SpNode) { - sp = ss->sp; - bestMove = sp->bestMove; - threatMove = sp->threatMove; - bestValue = sp->bestValue; + splitPoint = ss->splitPoint; + bestMove = splitPoint->bestMove; + threatMove = splitPoint->threatMove; + bestValue = splitPoint->bestValue; tte = NULL; ttMove = excludedMove = MOVE_NONE; ttValue = VALUE_NONE; - assert(sp->bestValue > -VALUE_INFINITE && sp->moveCount > 0); + assert(splitPoint->bestValue > -VALUE_INFINITE && splitPoint->moveCount > 0); - goto split_point_start; + goto moves_loop; } + moveCount = quietCount = 0; 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; @@ -517,10 +546,13 @@ namespace { if (PvNode && thisThread->maxPly < ss->ply) thisThread->maxPly = ss->ply; + if (Signals.stop || thisThread->cutoff_occurred()) + throw stop(); + if (!RootNode) { // Step 2. Check for aborted search and immediate draw - if (Signals.stop || pos.is_draw() || ss->ply > MAX_PLY) + if (pos.is_draw() || ss->ply > MAX_PLY) return DrawValue[pos.side_to_move()]; // Step 3. Mate distance pruning. Even if we mate at the next move our score @@ -552,9 +584,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 @@ -572,25 +604,22 @@ namespace { // Step 5. Evaluate the position statically and update parent's gain statistics if (inCheck) + { ss->staticEval = ss->evalMargin = eval = VALUE_NONE; + goto moves_loop; + } else if (tte) { - // Following asserts are valid only in single thread condition because - // TT access is always racy and its contents cannot be trusted. - assert(tte->static_value() != VALUE_NONE || Threads.size() > 1); - assert(ttValue != VALUE_NONE || tte->type() == BOUND_NONE || Threads.size() > 1); - - ss->staticEval = eval = tte->static_value(); - ss->evalMargin = tte->static_value_margin(); - - if (eval == VALUE_NONE || ss->evalMargin == VALUE_NONE) // Due to a race + // Never assume anything on values stored in TT + if ( (ss->staticEval = eval = tte->eval_value()) == VALUE_NONE + ||(ss->evalMargin = tte->eval_margin()) == VALUE_NONE) eval = ss->staticEval = evaluate(pos, ss->evalMargin); // 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 @@ -602,20 +631,19 @@ 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); - H.update_gain(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) + // Step 6. Razoring (skipped when in check) if ( !PvNode && depth < 4 * ONE_PLY - && !inCheck && eval + razor_margin(depth) < beta && ttMove == MOVE_NONE && abs(beta) < VALUE_MATE_IN_MAX_PLY @@ -629,23 +657,22 @@ namespace { return v; } - // Step 7. Static null move pruning (is omitted in PV nodes) + // Step 7. Static null move pruning (skipped when in check) // We're betting that the opponent doesn't have a move that will reduce // the score by more than futility_margin(depth) if we do a null move. if ( !PvNode && !ss->skipNullMove && depth < 4 * ONE_PLY - && !inCheck - && eval - FutilityMargins[depth][0] >= beta + && 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 - FutilityMargins[depth][0]; + return eval - futility_margin(depth, (ss-1)->futilityMoveCount); // Step 8. Null move search with verification search (is omitted in PV nodes) if ( !PvNode && !ss->skipNullMove && depth > ONE_PLY - && !inCheck && eval >= beta && abs(beta) < VALUE_MATE_IN_MAX_PLY && pos.non_pawn_material(pos.side_to_move())) @@ -659,12 +686,12 @@ namespace { if (eval - PawnValueMg > beta) R += ONE_PLY; - pos.do_null_move(st); + 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.do_null_move(st); + pos.undo_null_move(); if (nullValue >= beta) { @@ -672,12 +699,12 @@ namespace { if (nullValue >= VALUE_MATE_IN_MAX_PLY) nullValue = beta; - if (depth < 6 * ONE_PLY) + if (depth < 12 * ONE_PLY) return nullValue; // 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) @@ -696,20 +723,18 @@ namespace { if ( depth < 5 * ONE_PLY && (ss-1)->reduction && threatMove != MOVE_NONE - && yields_to_threat(pos, (ss-1)->currentMove, threatMove)) - return beta - 1; + && allows(pos, (ss-1)->currentMove, threatMove)) + return alpha; } } - // Step 9. ProbCut (is omitted in PV nodes) + // Step 9. ProbCut (skipped when in check) // If we have a very good capture (i.e. SEE > seeValues[captured_piece_type]) // and a reduced search returns a value much above beta, we can (almost) safely // prune the previous move. if ( !PvNode && depth >= 5 * ONE_PLY - && !inCheck && !ss->skipNullMove - && excludedMove == MOVE_NONE && abs(beta) < VALUE_MATE_IN_MAX_PLY) { Value rbeta = beta + 200; @@ -719,7 +744,7 @@ namespace { assert((ss-1)->currentMove != MOVE_NONE); assert((ss-1)->currentMove != MOVE_NULL); - MovePicker mp(pos, ttMove, H, pos.captured_piece_type()); + MovePicker mp(pos, ttMove, History, pos.captured_piece_type()); CheckInfo ci(pos); while ((move = mp.next_move()) != MOVE_NONE) @@ -727,39 +752,47 @@ 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; } } - // Step 10. Internal iterative deepening + // Step 10. Internal iterative deepening (skipped when in check) if ( depth >= (PvNode ? 5 * ONE_PLY : 8 * ONE_PLY) && ttMove == MOVE_NONE - && (PvNode || (!inCheck && ss->staticEval + Value(256) >= beta))) + && (PvNode || ss->staticEval + Value(256) >= beta)) { - Depth d = (PvNode ? depth - 2 * ONE_PLY : depth / 2); + 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); ttMove = tte ? tte->move() : MOVE_NONE; } -split_point_start: // At split points actual search starts from here +moves_loop: // When in check and at SpNode search starts from here - MovePicker mp(pos, ttMove, depth, H, 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); CheckInfo ci(pos); value = bestValue; // Workaround a bogus 'uninitialized' warning under gcc + improving = ss->staticEval >= (ss-2)->staticEval + || ss->staticEval == VALUE_NONE + ||(ss-2)->staticEval == VALUE_NONE; + singularExtensionNode = !RootNode && !SpNode && 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 @@ -783,8 +816,8 @@ split_point_start: // At split points actual search starts from here if (!pos.pl_move_is_legal(move, ci.pinned)) continue; - moveCount = ++sp->moveCount; - sp->mutex.unlock(); + moveCount = ++splitPoint->moveCount; + splitPoint->mutex.unlock(); } else moveCount++; @@ -793,7 +826,7 @@ split_point_start: // At split points actual search starts from here { Signals.firstRootMove = (moveCount == 1); - if (thisThread == Threads.main_thread() && Time::now() - SearchTime > 2000) + if (thisThread == Threads.main() && Time::now() - SearchTime > 3000) sync_cout << "info depth " << depth / ONE_PLY << " currmove " << move_to_uci(move, pos.is_chess960()) << " currmovenumber " << moveCount + PVIdx << sync_endl; @@ -804,12 +837,7 @@ split_point_start: // At split points actual search starts from here givesCheck = pos.move_gives_check(move, ci); dangerous = givesCheck || pos.is_passed_pawn_push(move) - || type_of(move) == CASTLE - || ( captureOrPromotion // Entering a pawn endgame? - && type_of(pos.piece_on(to_sq(move))) != PAWN - && type_of(move) == NORMAL - && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK) - - PieceValue[MG][pos.piece_on(to_sq(move))] == VALUE_ZERO)); + || type_of(move) == CASTLE; // Step 12. Extend checks and, in PV nodes, also dangerous moves if (PvNode && dangerous) @@ -834,12 +862,12 @@ 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; if (value < rBeta) - ext = rBeta >= beta ? ONE_PLY + ONE_PLY / 2 : ONE_PLY; + ext = ONE_PLY; } // Update current move (this must be done after singular extension search) @@ -850,17 +878,16 @@ split_point_start: // At split points actual search starts from here && !captureOrPromotion && !inCheck && !dangerous - && move != ttMove - && (bestValue > VALUE_MATED_IN_MAX_PLY || ( bestValue == -VALUE_INFINITE - && alpha > VALUE_MATED_IN_MAX_PLY))) + /* && move != ttMove Already implicit in the next condition */ + && bestValue > VALUE_MATED_IN_MAX_PLY) { // Move count based pruning if ( depth < 16 * ONE_PLY - && moveCount >= FutilityMoveCounts[depth] - && (!threatMove || !prevents_threat(pos, move, threatMove))) + && moveCount >= FutilityMoveCounts[improving][depth] + && (!threatMove || !refutes(pos, move, threatMove))) { if (SpNode) - sp->mutex.lock(); + splitPoint->mutex.lock(); continue; } @@ -868,40 +895,51 @@ split_point_start: // At split points actual search starts from here // Value based pruning // We illogically ignore reduction condition depth >= 3*ONE_PLY for predicted depth, // but fixing this made program slightly weaker. - Depth predictedDepth = newDepth - reduction(depth, moveCount); + Depth predictedDepth = newDepth - reduction(improving, depth, moveCount); futilityValue = ss->staticEval + ss->evalMargin + futility_margin(predictedDepth, moveCount) - + H.gain(pos.piece_moved(move), to_sq(move)); + + Gains[pos.piece_moved(move)][to_sq(move)]; if (futilityValue < beta) { - if (SpNode) - sp->mutex.lock(); + bestValue = std::max(bestValue, futilityValue); + if (SpNode) + { + splitPoint->mutex.lock(); + if (bestValue > splitPoint->bestValue) + splitPoint->bestValue = bestValue; + } continue; } // Prune moves with negative SEE at low depths - if ( predictedDepth < 2 * ONE_PLY + if ( predictedDepth < 4 * ONE_PLY && pos.see_sign(move) < 0) { if (SpNode) - sp->mutex.lock(); + splitPoint->mutex.lock(); continue; } + + // We have not pruned the move that will be searched, but remember how + // 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 (!pos.pl_move_is_legal(move, ci.pinned)) + if (!RootNode && !SpNode && !pos.pl_move_is_legal(move, ci.pinned)) { moveCount--; continue; } - pvMove = PvNode ? moveCount == 1 : false; + 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); @@ -912,14 +950,23 @@ split_point_start: // At split points actual search starts from here && !pvMove && !captureOrPromotion && !dangerous - && ss->killers[0] != move - && ss->killers[1] != move) + && move != ttMove + && move != ss->killers[0] + && move != ss->killers[1]) { - ss->reduction = reduction(depth, moveCount); + ss->reduction = reduction(improving, 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); - alpha = SpNode ? sp->alpha : alpha; + 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; @@ -930,11 +977,13 @@ split_point_start: // At split points actual search starts from here // Step 16. Full depth search, when LMR is skipped or fails high if (doFullDepthSearch) { - alpha = SpNode ? sp->alpha : alpha; + if (SpNode) + alpha = splitPoint->alpha; + 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 @@ -944,7 +993,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); @@ -953,18 +1002,11 @@ split_point_start: // At split points actual search starts from here // Step 18. Check for new best move if (SpNode) { - sp->mutex.lock(); - bestValue = sp->bestValue; - alpha = sp->alpha; + splitPoint->mutex.lock(); + bestValue = splitPoint->bestValue; + alpha = splitPoint->alpha; } - // Finished searching the move. If Signals.stop is true, the search - // was aborted because the user interrupted the search or because we - // ran out of time. In this case, the return value of the search cannot - // be trusted, and we don't update the best move and/or PV. - if (Signals.stop || thisThread->cutoff_occurred()) - return value; // To avoid returning VALUE_INFINITE - if (RootNode) { RootMove& rm = *std::find(RootMoves.begin(), RootMoves.end(), move); @@ -990,22 +1032,21 @@ split_point_start: // At split points actual search starts from here if (value > bestValue) { - bestValue = value; - if (SpNode) sp->bestValue = value; + bestValue = SpNode ? splitPoint->bestValue = value : value; if (value > alpha) { - bestMove = move; - if (SpNode) sp->bestMove = move; + bestMove = SpNode ? splitPoint->bestMove = move : move; - if (PvNode && value < beta) - { - alpha = value; // Update alpha here! Always alpha < beta - if (SpNode) sp->alpha = value; - } - else // Fail high + if (PvNode && value < beta) // Update alpha! Always alpha < beta + alpha = SpNode ? splitPoint->alpha = value : value; + else { - if (SpNode) sp->cutoff = true; + assert(value >= beta); // Fail high + + if (SpNode) + splitPoint->cutoff = true; + break; } } @@ -1013,12 +1054,14 @@ split_point_start: // At split points actual search starts from here // Step 19. Check for splitting the search if ( !SpNode - && depth >= Threads.min_split_depth() - && bestValue < beta - && Threads.available_slave_exists(thisThread)) + && depth >= Threads.minimumSplitDepth + && Threads.available_slave(thisThread) + && thisThread->splitPointsSize < MAX_SPLITPOINTS_PER_THREAD) { - bestValue = Threads.split(pos, ss, alpha, beta, bestValue, &bestMove, - depth, threatMove, moveCount, mp, NT); + assert(bestValue < beta); + + thisThread->split(pos, ss, alpha, beta, &bestValue, &bestMove, + depth, threatMove, moveCount, &mp, NT, cutNode); if (bestValue >= beta) break; } @@ -1040,41 +1083,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)); - H.add(pos.piece_moved(bestMove), to_sq(bestMove), bonus); + 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]; - H.add(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); @@ -1092,7 +1131,7 @@ split_point_start: // At split points actual search starts from here const bool PvNode = (NT == PV); assert(NT == PV || NT == NonPV); - assert(InCheck == pos.in_check()); + assert(InCheck == !!pos.checkers()); assert(alpha >= -VALUE_INFINITE && alpha < beta && beta <= VALUE_INFINITE); assert(PvNode || (alpha == beta - 1)); assert(depth <= DEPTH_ZERO); @@ -1102,7 +1141,7 @@ split_point_start: // At split points actual search starts from here Key posKey; Move ttMove, move, bestMove; Value bestValue, value, ttValue, futilityValue, futilityBase, oldAlpha; - bool givesCheck, enoughMaterial, evasionPrunable, fromNull; + bool givesCheck, evasionPrunable; Depth ttDepth; // To flag BOUND_EXACT a node with eval above alpha and no available moves @@ -1111,30 +1150,29 @@ split_point_start: // At split points actual search starts from here ss->currentMove = bestMove = MOVE_NONE; ss->ply = (ss-1)->ply + 1; - fromNull = (ss-1)->currentMove == MOVE_NULL; // Check for an instant draw or maximum ply reached - if (pos.is_draw() || ss->ply > MAX_PLY) + if (pos.is_draw() || ss->ply > MAX_PLY) return DrawValue[pos.side_to_move()]; - // Transposition table lookup. At PV nodes, we don't use the TT for - // pruning, but only for move ordering. - posKey = pos.key(); - tte = TT.probe(posKey); - ttMove = tte ? tte->move() : MOVE_NONE; - ttValue = tte ? value_from_tt(tte->value(),ss->ply) : VALUE_NONE; - // Decide whether or not to include checks, this fixes also the type of // TT entry depth that we are going to use. Note that in qsearch we use // only two types of depth in TT: DEPTH_QS_CHECKS or DEPTH_QS_NO_CHECKS. ttDepth = InCheck || depth >= DEPTH_QS_CHECKS ? DEPTH_QS_CHECKS : DEPTH_QS_NO_CHECKS; + + // Transposition table lookup + posKey = pos.key(); + tte = TT.probe(posKey); + ttMove = tte ? tte->move() : MOVE_NONE; + ttValue = tte ? value_from_tt(tte->value(),ss->ply) : VALUE_NONE; + 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; @@ -1145,23 +1183,14 @@ split_point_start: // At split points actual search starts from here { ss->staticEval = ss->evalMargin = VALUE_NONE; bestValue = futilityBase = -VALUE_INFINITE; - enoughMaterial = false; } else { - if (fromNull) + if (tte) { - ss->staticEval = bestValue = -(ss-1)->staticEval; - ss->evalMargin = VALUE_ZERO; - } - else if (tte) - { - assert(tte->static_value() != VALUE_NONE || Threads.size() > 1); - - ss->staticEval = bestValue = tte->static_value(); - ss->evalMargin = tte->static_value_margin(); - - if (ss->staticEval == VALUE_NONE || ss->evalMargin == VALUE_NONE) // Due to a race + // Never assume anything on values stored in TT + if ( (ss->staticEval = bestValue = tte->eval_value()) == VALUE_NONE + ||(ss->evalMargin = tte->eval_margin()) == VALUE_NONE) ss->staticEval = bestValue = evaluate(pos, ss->evalMargin); } else @@ -1181,14 +1210,13 @@ split_point_start: // At split points actual search starts from here alpha = bestValue; futilityBase = ss->staticEval + ss->evalMargin + Value(128); - enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMg; } // Initialize a MovePicker object for the current position, and prepare // 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, 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 @@ -1202,9 +1230,7 @@ split_point_start: // At split points actual search starts from here if ( !PvNode && !InCheck && !givesCheck - && !fromNull && move != ttMove - && enoughMaterial && type_of(move) != PROMOTION && !pos.is_passed_pawn_push(move)) { @@ -1214,22 +1240,22 @@ split_point_start: // At split points actual search starts from here if (futilityValue < beta) { - if (futilityValue > bestValue) - bestValue = futilityValue; - + bestValue = std::max(bestValue, futilityValue); continue; } - // Prune moves with negative or equal SEE + // 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) <= 0) + && pos.see(move, beta - futilityBase) <= 0) + { + bestValue = std::max(bestValue, futilityBase); continue; + } } // Detect non-capture evasions that are candidate to be pruned - evasionPrunable = !PvNode - && InCheck + evasionPrunable = InCheck && bestValue > VALUE_MATED_IN_MAX_PLY && !pos.is_capture(move) && !pos.can_castle(pos.side_to_move()); @@ -1331,7 +1357,7 @@ split_point_start: // At split points actual search starts from here // check_is_dangerous() tests if a checking move can be pruned in qsearch() - bool check_is_dangerous(Position& pos, Move move, Value futilityBase, Value beta) + bool check_is_dangerous(const Position& pos, Move move, Value futilityBase, Value beta) { Piece pc = pos.piece_moved(move); Square from = from_sq(move); @@ -1365,39 +1391,40 @@ split_point_start: // At split points actual search starts from here } - // yields_to_threat() tests whether the move at previous ply yields to the so - // called threat move (the best move returned from a null search that fails - // low). Here 'yields to' means that the move somehow made the threat possible - // for instance if the moving piece is the same in both moves. + // allows() tests whether the 'first' move at previous ply somehow makes the + // 'second' move possible, for instance if the moving piece is the same in + // both moves. Normally the second move is the threat (the best move returned + // from a null search that fails low). - bool yields_to_threat(const Position& pos, Move move, Move threat) { + bool allows(const Position& pos, Move first, Move second) { - assert(is_ok(move)); - assert(is_ok(threat)); - assert(color_of(pos.piece_on(from_sq(threat))) == ~pos.side_to_move()); + assert(is_ok(first)); + assert(is_ok(second)); + assert(color_of(pos.piece_on(from_sq(second))) == ~pos.side_to_move()); + assert(color_of(pos.piece_on(to_sq(first))) == ~pos.side_to_move()); - Square mfrom = from_sq(move); - Square mto = to_sq(move); - Square tfrom = from_sq(threat); - Square tto = to_sq(threat); + Square m1from = from_sq(first); + Square m2from = from_sq(second); + Square m1to = to_sq(first); + Square m2to = to_sq(second); - // The piece is the same or threat's destination was vacated by the move - if (mto == tfrom || tto == mfrom) + // The piece is the same or second's destination was vacated by the first move + if (m1to == m2from || m2to == m1from) return true; - // Threat moves through the vacated square - if (between_bb(tfrom, tto) & mfrom) + // Second one moves through the square vacated by first one + if (between_bb(m2from, m2to) & m1from) return true; - // Threat's destination is defended by the move's piece - Bitboard matt = pos.attacks_from(pos.piece_on(mto), mto, pos.pieces() ^ tfrom); - if (matt & tto) + // Second's destination is defended by the first move's piece + Bitboard m1att = pos.attacks_from(pos.piece_on(m1to), m1to, pos.pieces() ^ m2from); + if (m1att & m2to) return true; - // Threat gives a discovered check through the move's checking piece - if (matt & pos.king_square(pos.side_to_move())) + // Second move gives a discovered check through the first's checking piece + if (m1att & pos.king_square(pos.side_to_move())) { - assert(between_bb(mto, pos.king_square(pos.side_to_move())) & tfrom); + assert(between_bb(m1to, pos.king_square(pos.side_to_move())) & m2from); return true; } @@ -1405,51 +1432,49 @@ split_point_start: // At split points actual search starts from here } - // prevents_threat() tests whether a move is able to defend against the so - // called threat move (the best move returned from a null search that fails - // low). In this case will not be pruned. + // refutes() tests whether a 'first' move is able to defend against a 'second' + // opponent's move. In this case will not be pruned. Normally the second move + // is the threat (the best move returned from a null search that fails low). - bool prevents_threat(const Position& pos, Move move, Move threat) { + bool refutes(const Position& pos, Move first, Move second) { - assert(is_ok(move)); - assert(is_ok(threat)); - assert(!pos.is_capture_or_promotion(move)); - assert(!pos.is_passed_pawn_push(move)); + assert(is_ok(first)); + assert(is_ok(second)); - Square mfrom = from_sq(move); - Square mto = to_sq(move); - Square tfrom = from_sq(threat); - Square tto = to_sq(threat); + Square m1from = from_sq(first); + Square m2from = from_sq(second); + Square m1to = to_sq(first); + Square m2to = to_sq(second); // Don't prune moves of the threatened piece - if (mfrom == tto) + if (m1from == m2to) return true; // If the threatened piece has value less than or equal to the value of the // threat piece, don't prune moves which defend it. - if ( pos.is_capture(threat) - && ( PieceValue[MG][pos.piece_on(tfrom)] >= PieceValue[MG][pos.piece_on(tto)] - || type_of(pos.piece_on(tfrom)) == KING)) + if ( pos.is_capture(second) + && ( PieceValue[MG][pos.piece_on(m2from)] >= PieceValue[MG][pos.piece_on(m2to)] + || type_of(pos.piece_on(m2from)) == KING)) { // Update occupancy as if the piece and the threat are moving - Bitboard occ = pos.pieces() ^ mfrom ^ mto ^ tfrom; - Piece piece = pos.piece_on(mfrom); + Bitboard occ = pos.pieces() ^ m1from ^ m1to ^ m2from; + Piece pc = pos.piece_on(m1from); // The moved piece attacks the square 'tto' ? - if (pos.attacks_from(piece, mto, occ) & tto) + 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>(tto, occ) & pos.pieces(color_of(piece), QUEEN, ROOK)) - | (attacks_bb(tto, 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(tto)))) + if (unlikely(xray) && (xray & ~pos.attacks_from(m2to))) return true; } // Don't prune safe moves which block the threat path - if ((between_bb(tfrom, tto) & mto) && pos.see_sign(move) >= 0) + if ((between_bb(m2from, m2to) & m1to) && pos.see_sign(first) >= 0) return true; return false; @@ -1505,13 +1530,13 @@ 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; for (size_t i = 0; i < Threads.size(); i++) - if (Threads[i].maxPly > selDepth) - selDepth = Threads[i].maxPly; + if (Threads[i]->maxPly > selDepth) + selDepth = Threads[i]->maxPly; for (size_t i = 0; i < uciPVSize; i++) { @@ -1530,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"; @@ -1552,8 +1577,8 @@ 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; + StateInfo state[MAX_PLY_PLUS_3], *st = state; + const TTEntry* tte; int ply = 0; Move m = pv[0]; @@ -1562,7 +1587,8 @@ void RootMove::extract_pv_from_tt(Position& pos) { do { pv.push_back(m); - assert(pos.move_is_legal(pv[ply])); + assert(MoveList(pos).contains(pv[ply])); + pos.do_move(pv[ply++], *st++); tte = TT.probe(pos.key()); @@ -1570,7 +1596,7 @@ void RootMove::extract_pv_from_tt(Position& pos) { && pos.is_pseudo_legal(m = tte->move()) // Local copy, TT could change && pos.pl_move_is_legal(m, pos.pinned_pieces()) && ply < MAX_PLY - && (!pos.is_draw() || ply < 2)); + && (!pos.is_draw() || ply < 2)); pv.push_back(MOVE_NONE); // Must be zero-terminating @@ -1584,25 +1610,18 @@ 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; + StateInfo state[MAX_PLY_PLUS_3], *st = state; + const TTEntry* tte; int ply = 0; - Value v, m; do { tte = TT.probe(pos.key()); if (!tte || tte->move() != pv[ply]) // Don't overwrite correct entries - { - if (pos.in_check()) - v = m = VALUE_NONE; - else - v = evaluate(pos, m); + TT.store(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, pv[ply], VALUE_NONE, VALUE_NONE); - TT.store(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, pv[ply], v, m); - } + assert(MoveList(pos).contains(pv[ply])); - assert(pos.move_is_legal(pv[ply])); pos.do_move(pv[ply++], *st++); } while (pv[ply] != MOVE_NONE); @@ -1615,33 +1634,29 @@ void RootMove::insert_pv_in_tt(Position& pos) { void Thread::idle_loop() { - // Pointer 'sp_master', if non-NULL, points to the active SplitPoint - // object for which the thread is the master. - const SplitPoint* sp_master = splitPointsCnt ? curSplitPoint : NULL; + // Pointer 'this_sp' is not null only if we are called from split(), and not + // at the thread creation. So it means we are the split point's master. + SplitPoint* this_sp = splitPointsSize ? activeSplitPoint : NULL; - assert(!sp_master || (sp_master->master == this && is_searching)); + assert(!this_sp || (this_sp->masterThread == this && searching)); - // If this thread is the master of a split point and all slaves have - // finished their work at this split point, return from the idle loop. - while (!sp_master || sp_master->slavesMask) + while (true) { - // If we are not searching, wait for a condition to be signaled - // instead of wasting CPU time polling for work. - while ( do_sleep - || do_exit - || (!is_searching && Threads.use_sleeping_threads())) + // If we are not searching, wait for a condition to be signaled instead of + // wasting CPU time polling for work. + while ((!searching && Threads.sleepWhileIdle) || exit) { - if (do_exit) + if (exit) { - assert(!sp_master); + assert(!this_sp); return; } - // Grab the lock to avoid races with Thread::wake_up() + // Grab the lock to avoid races with Thread::notify_one() mutex.lock(); - // If we are master and all slaves have finished don't go to sleep - if (sp_master && !sp_master->slavesMask) + // If we are master and all slaves have finished then exit idle_loop + if (this_sp && !this_sp->slavesMask) { mutex.unlock(); break; @@ -1649,62 +1664,73 @@ void Thread::idle_loop() { // Do sleep after retesting sleep conditions under lock protection, in // particular we need to avoid a deadlock in case a master thread has, - // in the meanwhile, allocated us and sent the wake_up() call before we - // had the chance to grab the lock. - if (do_sleep || !is_searching) + // in the meanwhile, allocated us and sent the notify_one() call before + // we had the chance to grab the lock. + if (!searching && !exit) sleepCondition.wait(mutex); mutex.unlock(); } // If this thread has been assigned work, launch a search - if (is_searching) + if (searching) { - assert(!do_sleep && !do_exit); + assert(!exit); Threads.mutex.lock(); - assert(is_searching); - SplitPoint* sp = curSplitPoint; + assert(searching); + assert(activeSplitPoint); + SplitPoint* sp = activeSplitPoint; Threads.mutex.unlock(); - Stack ss[MAX_PLY_PLUS_2]; + Stack stack[MAX_PLY_PLUS_3], *ss = stack+2; // To allow referencing (ss-2) Position pos(*sp->pos, this); - memcpy(ss, sp->ss - 1, 4 * sizeof(Stack)); - (ss+1)->sp = sp; + std::memcpy(ss-2, sp->ss-2, 5 * sizeof(Stack)); + ss->splitPoint = sp; sp->mutex.lock(); - assert(sp->activePositions[idx] == NULL); + assert(activePosition == NULL); - sp->activePositions[idx] = &pos; + activePosition = &pos; - if (sp->nodeType == Root) - search(pos, ss+1, sp->alpha, sp->beta, sp->depth); - else if (sp->nodeType == PV) - search(pos, ss+1, sp->alpha, sp->beta, sp->depth); - else if (sp->nodeType == NonPV) - search(pos, ss+1, sp->alpha, sp->beta, sp->depth); - else - assert(false); + try { + switch (sp->nodeType) { + case Root: + search(pos, ss, sp->alpha, sp->beta, sp->depth, sp->cutNode); + break; + case PV: + search(pos, ss, sp->alpha, sp->beta, sp->depth, sp->cutNode); + break; + case NonPV: + search(pos, ss, sp->alpha, sp->beta, sp->depth, sp->cutNode); + break; + default: + assert(false); + } - assert(is_searching); + assert(searching); + } + catch (stop&) { + sp->mutex.lock(); // Exception is thrown out of lock + } - is_searching = false; - sp->activePositions[idx] = NULL; + searching = false; + activePosition = NULL; sp->slavesMask &= ~(1ULL << idx); sp->nodes += pos.nodes_searched(); - // Wake up master thread so to allow it to return from the idle loop in - // case we are the last slave of the split point. - if ( Threads.use_sleeping_threads() - && this != sp->master + // Wake up master thread so to allow it to return from the idle loop + // in case we are the last slave of the split point. + if ( Threads.sleepWhileIdle + && this != sp->masterThread && !sp->slavesMask) { - assert(!sp->master->is_searching); - sp->master->wake_up(); + assert(!sp->masterThread->searching); + sp->masterThread->notify_one(); } // After releasing the lock we cannot access anymore any SplitPoint @@ -1713,6 +1739,17 @@ void Thread::idle_loop() { // unsafe because if we are exiting there is a chance are already freed. sp->mutex.unlock(); } + + // If this thread is the master of a split point and all slaves have finished + // their work at this split point, return from the idle loop. + if (this_sp && !this_sp->slavesMask) + { + this_sp->mutex.lock(); + bool finished = !this_sp->slavesMask; // Retest under lock protection + this_sp->mutex.unlock(); + if (finished) + return; + } } } @@ -1742,11 +1779,11 @@ void check_time() { nodes = RootPos.nodes_searched(); // Loop across all split points and sum accumulated SplitPoint nodes plus - // all the currently active slaves positions. + // all the currently active positions nodes. for (size_t i = 0; i < Threads.size(); i++) - for (int j = 0; j < Threads[i].splitPointsCnt; j++) + for (int j = 0; j < Threads[i]->splitPointsSize; j++) { - SplitPoint& sp = Threads[i].splitPoints[j]; + SplitPoint& sp = Threads[i]->splitPoints[j]; sp.mutex.lock(); @@ -1754,8 +1791,9 @@ void check_time() { Bitboard sm = sp.slavesMask; while (sm) { - Position* pos = sp.activePositions[pop_lsb(&sm)]; - nodes += pos ? pos->nodes_searched() : 0; + Position* pos = Threads[pop_lsb(&sm)]->activePosition; + if (pos) + nodes += pos->nodes_searched(); } sp.mutex.unlock();