X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=12ed75997dfaa500beccd424ef2d86529444bc1b;hp=135f7808d1778768a4e5d3dd0737373e9010745b;hb=950c8436edc50857b83eb3e0cbaca06407764655;hpb=5943600a890cef1e83235d08b248e686c95c77d1 diff --git a/src/search.cpp b/src/search.cpp index 135f7808..12ed7599 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-2014 Marco Costalba, Joona Kiiski, Tord Romstad + Copyright (C) 2008-2015 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 @@ -20,7 +20,7 @@ #include #include #include -#include +#include // For std::memset #include #include @@ -173,13 +173,13 @@ uint64_t Search::perft(Position& pos, Depth depth) { cnt = 1, nodes++; else { - pos.do_move(*it, st, ci, pos.gives_check(*it, ci)); + pos.do_move(*it, st, pos.gives_check(*it, ci)); cnt = leaf ? MoveList(pos).size() : perft(pos, depth - ONE_PLY); nodes += cnt; pos.undo_move(*it); } if (Root) - sync_cout << UCI::format_move(*it, pos.is_chess960()) << ": " << cnt << sync_endl; + sync_cout << UCI::move(*it, pos.is_chess960()) << ": " << cnt << sync_endl; } return nodes; } @@ -193,7 +193,7 @@ template uint64_t Search::perft(Position& pos, Depth depth); void Search::think() { - TimeMgr.init(Limits, RootPos.game_ply(), RootPos.side_to_move()); + TimeMgr.init(Limits, RootPos.side_to_move(), RootPos.game_ply()); int contempt = Options["Contempt"] * PawnValueEg / 100; // From centipawns DrawValue[ RootPos.side_to_move()] = VALUE_DRAW - Value(contempt); @@ -216,7 +216,7 @@ void Search::think() { { RootMoves.push_back(MOVE_NONE); sync_cout << "info depth 0 score " - << UCI::format_value(RootPos.checkers() ? -VALUE_MATE : VALUE_DRAW) + << UCI::value(RootPos.checkers() ? -VALUE_MATE : VALUE_DRAW) << sync_endl; } else @@ -274,10 +274,10 @@ void Search::think() { RootPos.this_thread()->wait_for(Signals.stop); } - sync_cout << "bestmove " << UCI::format_move(RootMoves[0].pv[0], RootPos.is_chess960()); + sync_cout << "bestmove " << UCI::move(RootMoves[0].pv[0], RootPos.is_chess960()); - if (RootMoves[0].pv.size() > 1) - std::cout << " ponder " << UCI::format_move(RootMoves[0].pv[1], RootPos.is_chess960()); + if (RootMoves[0].pv.size() > 1 || RootMoves[0].extract_ponder_from_tt(RootPos)) + std::cout << " ponder " << UCI::move(RootMoves[0].pv[1], RootPos.is_chess960()); std::cout << sync_endl; } @@ -365,7 +365,8 @@ namespace { // When failing high/low give some update (without cluttering // the UI) before a re-search. - if ( (bestValue <= alpha || bestValue >= beta) + if ( multiPV == 1 + && (bestValue <= alpha || bestValue >= beta) && Time::now() - SearchTime > 3000) sync_cout << uci_pv(pos, depth, alpha, beta) << sync_endl; @@ -457,13 +458,13 @@ namespace { Move pv[MAX_PLY+1], quietsSearched[64]; StateInfo st; - const TTEntry *tte; + TTEntry* tte; SplitPoint* splitPoint; Key posKey; Move ttMove, move, excludedMove, bestMove; Depth extension, newDepth, predictedDepth; Value bestValue, value, ttValue, eval, nullValue, futilityValue; - bool inCheck, givesCheck, singularExtensionNode, improving; + bool ttHit, inCheck, givesCheck, singularExtensionNode, improving; bool captureOrPromotion, dangerous, doFullDepthSearch; int moveCount, quietCount; @@ -477,6 +478,7 @@ namespace { bestMove = splitPoint->bestMove; bestValue = splitPoint->bestValue; tte = NULL; + ttHit = false; ttMove = excludedMove = MOVE_NONE; ttValue = VALUE_NONE; @@ -522,13 +524,13 @@ namespace { // TT value, so we use a different position key in case of an excluded move. excludedMove = ss->excludedMove; posKey = excludedMove ? pos.exclusion_key() : pos.key(); - tte = TT.probe(posKey); - ss->ttMove = ttMove = RootNode ? RootMoves[PVIdx].pv[0] : tte ? tte->move() : MOVE_NONE; - ttValue = tte ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE; + tte = TT.probe(posKey, ttHit); + ss->ttMove = ttMove = RootNode ? RootMoves[PVIdx].pv[0] : ttHit ? tte->move() : MOVE_NONE; + ttValue = ttHit ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE; // At non-PV nodes we check for a fail high/low. We don't probe at PV nodes if ( !PvNode - && tte + && ttHit && tte->depth() >= depth && ttValue != VALUE_NONE // Only in case of TT access race && (ttValue >= beta ? (tte->bound() & BOUND_LOWER) @@ -564,9 +566,9 @@ namespace { : v > drawScore ? VALUE_MATE - MAX_PLY - ss->ply : VALUE_DRAW + 2 * v * drawScore; - TT.store(posKey, value_to_tt(value, ss->ply), BOUND_EXACT, - std::min(DEPTH_MAX - ONE_PLY, depth + 6 * ONE_PLY), - MOVE_NONE, VALUE_NONE); + tte->save(posKey, value_to_tt(value, ss->ply), BOUND_EXACT, + std::min(DEPTH_MAX - ONE_PLY, depth + 6 * ONE_PLY), + MOVE_NONE, VALUE_NONE, TT.generation()); return value; } @@ -580,10 +582,10 @@ namespace { goto moves_loop; } - else if (tte) + else if (ttHit) { // Never assume anything on values stored in TT - if ((ss->staticEval = eval = tte->eval_value()) == VALUE_NONE) + if ((ss->staticEval = eval = tte->eval()) == VALUE_NONE) eval = ss->staticEval = evaluate(pos); // Can ttValue be used as a better position evaluation? @@ -596,7 +598,7 @@ namespace { eval = ss->staticEval = (ss-1)->currentMove != MOVE_NULL ? evaluate(pos) : -(ss-1)->staticEval + 2 * Eval::Tempo; - TT.store(posKey, VALUE_NONE, BOUND_NONE, DEPTH_NONE, MOVE_NONE, ss->staticEval); + tte->save(posKey, VALUE_NONE, BOUND_NONE, DEPTH_NONE, MOVE_NONE, ss->staticEval, TT.generation()); } if (ss->skipEarlyPruning) @@ -631,7 +633,7 @@ namespace { } // Step 7. Futility pruning: child node (skipped when in check) - if ( !PvNode + if ( !RootNode && depth < 7 * ONE_PLY && eval - futility_margin(depth) >= beta && eval < VALUE_KNOWN_WIN // Do not return unproven wins @@ -649,7 +651,7 @@ namespace { assert(eval - beta >= 0); // Null move dynamic reduction based on depth and value - Depth R = (3 + depth / 4 + std::min((eval - beta) / PawnValueMg, 3)) * ONE_PLY; + Depth R = ((823 + 67 * depth) / 256 + std::min((eval - beta) / PawnValueMg, 3)) * ONE_PLY; pos.do_null_move(st); (ss+1)->skipEarlyPruning = true; @@ -700,7 +702,7 @@ namespace { if (pos.legal(move, ci.pinned)) { ss->currentMove = move; - pos.do_move(move, st, ci, pos.gives_check(move, ci)); + pos.do_move(move, st, pos.gives_check(move, ci)); value = -search(pos, ss+1, -rbeta, -rbeta+1, rdepth, !cutNode); pos.undo_move(move); if (value >= rbeta) @@ -718,8 +720,8 @@ namespace { search(pos, ss, alpha, beta, d / 2, true); ss->skipEarlyPruning = false; - tte = TT.probe(posKey); - ttMove = tte ? tte->move() : MOVE_NONE; + tte = TT.probe(posKey, ttHit); + ttMove = ttHit ? tte->move() : MOVE_NONE; } moves_loop: // When in check and at SpNode search starts from here @@ -782,7 +784,7 @@ moves_loop: // When in check and at SpNode search starts from here if (thisThread == Threads.main() && Time::now() - SearchTime > 3000) sync_cout << "info depth " << depth / ONE_PLY - << " currmove " << UCI::format_move(move, pos.is_chess960()) + << " currmove " << UCI::move(move, pos.is_chess960()) << " currmovenumber " << moveCount + PVIdx << sync_endl; } @@ -828,8 +830,8 @@ moves_loop: // When in check and at SpNode search starts from here // Update the current move (this must be done after singular extension search) newDepth = depth - ONE_PLY + extension; - // Step 13. Pruning at shallow depth (exclude PV nodes) - if ( !PvNode + // Step 13. Pruning at shallow depth + if ( !RootNode && !captureOrPromotion && !inCheck && !dangerous @@ -892,7 +894,7 @@ moves_loop: // When in check and at SpNode search starts from here quietsSearched[quietCount++] = move; // Step 14. Make the move - pos.do_move(move, st, ci, givesCheck); + pos.do_move(move, st, givesCheck); // Step 15. Reduced depth search (LMR). If the move fails high it will be // re-searched at full depth. @@ -905,7 +907,7 @@ moves_loop: // When in check and at SpNode search starts from here ss->reduction = reduction(improving, depth, moveCount); if ( (!PvNode && cutNode) - || History[pos.piece_on(to_sq(move))][to_sq(move)] < 0) + || History[pos.piece_on(to_sq(move))][to_sq(move)] < VALUE_ZERO) ss->reduction += ONE_PLY; if (move == countermoves[0] || move == countermoves[1]) @@ -915,7 +917,7 @@ moves_loop: // When in check and at SpNode search starts from here if ( ss->reduction && type_of(move) == NORMAL && type_of(pos.piece_on(to_sq(move))) != PAWN - && pos.see(make_move(to_sq(move), from_sq(move))) < 0) + && pos.see(make_move(to_sq(move), from_sq(move))) < VALUE_ZERO) ss->reduction = std::max(DEPTH_ZERO, ss->reduction - ONE_PLY); Depth d = std::max(newDepth - ss->reduction, ONE_PLY); @@ -1040,7 +1042,9 @@ moves_loop: // When in check and at SpNode search starts from here && Threads.size() >= 2 && depth >= Threads.minimumSplitDepth && ( !thisThread->activeSplitPoint - || !thisThread->activeSplitPoint->allSlavesSearching) + || !thisThread->activeSplitPoint->allSlavesSearching + || ( Threads.size() > MAX_SLAVES_PER_SPLITPOINT + && thisThread->activeSplitPoint->slavesMask.count() == MAX_SLAVES_PER_SPLITPOINT)) && thisThread->splitPointsSize < MAX_SPLITPOINTS_PER_THREAD) { assert(bestValue > -VALUE_INFINITE && bestValue < beta); @@ -1079,10 +1083,10 @@ moves_loop: // When in check and at SpNode search starts from here else if (bestValue >= beta && !pos.capture_or_promotion(bestMove) && !inCheck) update_stats(pos, ss, bestMove, depth, quietsSearched, quietCount - 1); - TT.store(posKey, value_to_tt(bestValue, ss->ply), - bestValue >= beta ? BOUND_LOWER : - PvNode && bestMove ? BOUND_EXACT : BOUND_UPPER, - depth, bestMove, ss->staticEval); + tte->save(posKey, value_to_tt(bestValue, ss->ply), + bestValue >= beta ? BOUND_LOWER : + PvNode && bestMove ? BOUND_EXACT : BOUND_UPPER, + depth, bestMove, ss->staticEval, TT.generation()); assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); @@ -1107,11 +1111,11 @@ moves_loop: // When in check and at SpNode search starts from here Move pv[MAX_PLY+1]; StateInfo st; - const TTEntry* tte; + TTEntry* tte; Key posKey; Move ttMove, move, bestMove; Value bestValue, value, ttValue, futilityValue, futilityBase, oldAlpha; - bool givesCheck, evasionPrunable; + bool ttHit, givesCheck, evasionPrunable; Depth ttDepth; if (PvNode) @@ -1138,12 +1142,12 @@ moves_loop: // When in check and at SpNode search starts from here // 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; + tte = TT.probe(posKey, ttHit); + ttMove = ttHit ? tte->move() : MOVE_NONE; + ttValue = ttHit ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE; if ( !PvNode - && tte + && ttHit && tte->depth() >= ttDepth && ttValue != VALUE_NONE // Only in case of TT access race && (ttValue >= beta ? (tte->bound() & BOUND_LOWER) @@ -1161,10 +1165,10 @@ moves_loop: // When in check and at SpNode search starts from here } else { - if (tte) + if (ttHit) { // Never assume anything on values stored in TT - if ((ss->staticEval = bestValue = tte->eval_value()) == VALUE_NONE) + if ((ss->staticEval = bestValue = tte->eval()) == VALUE_NONE) ss->staticEval = bestValue = evaluate(pos); // Can ttValue be used as a better position evaluation? @@ -1179,9 +1183,9 @@ moves_loop: // When in check and at SpNode search starts from here // Stand pat. Return immediately if static value is at least beta if (bestValue >= beta) { - if (!tte) - TT.store(pos.key(), value_to_tt(bestValue, ss->ply), BOUND_LOWER, - DEPTH_NONE, MOVE_NONE, ss->staticEval); + if (!ttHit) + tte->save(pos.key(), value_to_tt(bestValue, ss->ply), BOUND_LOWER, + DEPTH_NONE, MOVE_NONE, ss->staticEval, TT.generation()); return bestValue; } @@ -1209,8 +1213,7 @@ moves_loop: // When in check and at SpNode search starts from here : pos.gives_check(move, ci); // Futility pruning - if ( !PvNode - && !InCheck + if ( !InCheck && !givesCheck && futilityBase > -VALUE_KNOWN_WIN && !pos.advanced_pawn_push(move)) @@ -1219,13 +1222,13 @@ moves_loop: // When in check and at SpNode search starts from here futilityValue = futilityBase + PieceValue[EG][pos.piece_on(to_sq(move))]; - if (futilityValue < beta) + if (futilityValue <= alpha) { bestValue = std::max(bestValue, futilityValue); continue; } - if (futilityBase < beta && pos.see(move) <= VALUE_ZERO) + if (futilityBase <= alpha && pos.see(move) <= VALUE_ZERO) { bestValue = std::max(bestValue, futilityBase); continue; @@ -1239,8 +1242,7 @@ moves_loop: // When in check and at SpNode search starts from here && !pos.can_castle(pos.side_to_move()); // Don't search moves with negative SEE values - if ( !PvNode - && (!InCheck || evasionPrunable) + if ( (!InCheck || evasionPrunable) && type_of(move) != PROMOTION && pos.see_sign(move) < VALUE_ZERO) continue; @@ -1255,7 +1257,7 @@ moves_loop: // When in check and at SpNode search starts from here ss->currentMove = move; // Make and search the move - pos.do_move(move, st, ci, givesCheck); + pos.do_move(move, st, givesCheck); value = givesCheck ? -qsearch(pos, ss+1, -beta, -alpha, depth - ONE_PLY) : -qsearch(pos, ss+1, -beta, -alpha, depth - ONE_PLY); pos.undo_move(move); @@ -1279,8 +1281,8 @@ moves_loop: // When in check and at SpNode search starts from here } else // Fail high { - TT.store(posKey, value_to_tt(value, ss->ply), BOUND_LOWER, - ttDepth, move, ss->staticEval); + tte->save(posKey, value_to_tt(value, ss->ply), BOUND_LOWER, + ttDepth, move, ss->staticEval, TT.generation()); return value; } @@ -1293,9 +1295,9 @@ moves_loop: // When in check and at SpNode search starts from here if (InCheck && bestValue == -VALUE_INFINITE) return mated_in(ss->ply); // Plies to mate from the root - TT.store(posKey, value_to_tt(bestValue, ss->ply), - PvNode && bestValue > oldAlpha ? BOUND_EXACT : BOUND_UPPER, - ttDepth, bestMove, ss->staticEval); + tte->save(posKey, value_to_tt(bestValue, ss->ply), + PvNode && bestValue > oldAlpha ? BOUND_EXACT : BOUND_UPPER, + ttDepth, bestMove, ss->staticEval, TT.generation()); assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); @@ -1393,10 +1395,6 @@ moves_loop: // When in check and at SpNode search starts from here { int score = RootMoves[i].score; - // Don't allow crazy blunders even at very low skills - if (i > 0 && RootMoves[i - 1].score > score + 2 * PawnValueMg) - break; - // This is our magic formula score += ( weakness * int(RootMoves[0].score - score) + variance * (rng.rand() % weakness)) / 128; @@ -1445,15 +1443,23 @@ moves_loop: // When in check and at SpNode search starts from here ss << "info depth " << d / ONE_PLY << " seldepth " << selDepth << " multipv " << i + 1 - << " score " << ((!tb && i == PVIdx) ? UCI::format_value(v, alpha, beta) : UCI::format_value(v)) - << " nodes " << pos.nodes_searched() - << " nps " << pos.nodes_searched() * 1000 / elapsed - << " tbhits " << TB::Hits + << " score " << UCI::value(v); + + if (!tb && i == PVIdx) + ss << (v >= beta ? " lowerbound" : v <= alpha ? " upperbound" : ""); + + ss << " nodes " << pos.nodes_searched() + << " nps " << pos.nodes_searched() * 1000 / elapsed; + + if (elapsed > 1000) // Earlier makes little sense + ss << " hashfull " << TT.hashfull(); + + ss << " tbhits " << TB::Hits << " time " << elapsed << " pv"; for (size_t j = 0; j < RootMoves[i].pv.size(); ++j) - ss << " " << UCI::format_move(RootMoves[i].pv[j], pos.is_chess960()); + ss << " " << UCI::move(RootMoves[i].pv[j], pos.is_chess960()); } return ss.str(); @@ -1469,15 +1475,15 @@ moves_loop: // When in check and at SpNode search starts from here void RootMove::insert_pv_in_tt(Position& pos) { StateInfo state[MAX_PLY], *st = state; - const TTEntry* tte; size_t idx = 0; for ( ; idx < pv.size(); ++idx) { - tte = TT.probe(pos.key()); + bool ttHit; + TTEntry* tte = TT.probe(pos.key(), ttHit); - if (!tte || tte->move() != pv[idx]) // Don't overwrite correct entries - TT.store(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, pv[idx], VALUE_NONE); + if (!ttHit || tte->move() != pv[idx]) // Don't overwrite correct entries + tte->save(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, pv[idx], VALUE_NONE, TT.generation()); assert(MoveList(pos).contains(pv[idx])); @@ -1488,6 +1494,30 @@ void RootMove::insert_pv_in_tt(Position& pos) { } +/// RootMove::extract_ponder_from_tt() is called in case we have no ponder move before +/// exiting the search, for instance in case we stop the search during a fail high at +/// root. We try hard to have a ponder move to return to the GUI, otherwise in case of +/// 'ponder on' we have nothing to think on. + +Move RootMove::extract_ponder_from_tt(Position& pos) +{ + StateInfo st; + bool found; + + assert(pv.size() == 1); + + pos.do_move(pv[0], st); + TTEntry* tte = TT.probe(pos.key(), found); + Move m = found ? tte->move() : MOVE_NONE; + if (!MoveList(pos).contains(m)) + m = MOVE_NONE; + + pos.undo_move(pv[0]); + pv.push_back(m); + return m; +} + + /// Thread::idle_loop() is where the thread is parked when it has no work to do void Thread::idle_loop() { @@ -1558,34 +1588,59 @@ void Thread::idle_loop() { // Try to late join to another split point if none of its slaves has // already finished. - if (Threads.size() > 2) - for (size_t i = 0; i < Threads.size(); ++i) + SplitPoint* bestSp = NULL; + Thread* bestThread = NULL; + int bestScore = INT_MAX; + + for (size_t i = 0; i < Threads.size(); ++i) + { + const size_t size = Threads[i]->splitPointsSize; // Local copy + sp = size ? &Threads[i]->splitPoints[size - 1] : NULL; + + if ( sp + && sp->allSlavesSearching + && sp->slavesMask.count() < MAX_SLAVES_PER_SPLITPOINT + && available_to(Threads[i])) { - const int size = Threads[i]->splitPointsSize; // Local copy - sp = size ? &Threads[i]->splitPoints[size - 1] : NULL; + assert(this != Threads[i]); + assert(!(this_sp && this_sp->slavesMask.none())); + + // Compute the recursive split points chain size + int level = -1; + for (SplitPoint* spp = Threads[i]->activeSplitPoint; spp; spp = spp->parentSplitPoint) + level++; - if ( sp - && sp->allSlavesSearching - && available_to(Threads[i])) + int score = level * 256 * 256 + (int)sp->slavesMask.count() * 256 - sp->depth * 1; + + if (score < bestScore) { - // Recheck the conditions under lock protection - Threads.mutex.lock(); - sp->mutex.lock(); - - if ( sp->allSlavesSearching - && available_to(Threads[i])) - { - sp->slavesMask.set(idx); - activeSplitPoint = sp; - searching = true; - } - - sp->mutex.unlock(); - Threads.mutex.unlock(); - - break; // Just a single attempt + bestSp = sp; + bestThread = Threads[i]; + bestScore = score; } } + } + + if (bestSp) + { + sp = bestSp; + + // Recheck the conditions under lock protection + Threads.mutex.lock(); + sp->mutex.lock(); + + if ( sp->allSlavesSearching + && sp->slavesMask.count() < MAX_SLAVES_PER_SPLITPOINT + && available_to(bestThread)) + { + sp->slavesMask.set(idx); + activeSplitPoint = sp; + searching = true; + } + + sp->mutex.unlock(); + Threads.mutex.unlock(); + } } // Grab the lock to avoid races with Thread::notify_one() @@ -1650,7 +1705,7 @@ void check_time() { // Loop across all split points and sum accumulated SplitPoint nodes plus // all the currently active positions nodes. for (size_t i = 0; i < Threads.size(); ++i) - for (int j = 0; j < Threads[i]->splitPointsSize; ++j) + for (size_t j = 0; j < Threads[i]->splitPointsSize; ++j) { SplitPoint& sp = Threads[i]->splitPoints[j];