X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=a15f259e2b791df7014a51ac6089b8444860d081;hp=c774f08ab5e862013355b6bd82e0ee7998e498bf;hb=f7d8ea3866c26df10617e97513e906d1f5a5b833;hpb=14cf27e6f65787a1f9c8e4759ae0fcc218f37d2d diff --git a/src/search.cpp b/src/search.cpp index c774f08a..a15f259e 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 @@ -167,19 +167,19 @@ uint64_t Search::perft(Position& pos, Depth depth) { CheckInfo ci(pos); const bool leaf = (depth == 2 * ONE_PLY); - for (MoveList it(pos); *it; ++it) + for (const ExtMove& ms : MoveList(pos)) { if (Root && depth <= ONE_PLY) cnt = 1, nodes++; else { - pos.do_move(*it, st, ci, pos.gives_check(*it, ci)); + pos.do_move(ms.move, st, ci, pos.gives_check(ms.move, ci)); cnt = leaf ? MoveList(pos).size() : perft(pos, depth - ONE_PLY); nodes += cnt; - pos.undo_move(*it); + pos.undo_move(ms.move); } if (Root) - sync_cout << UCI::format_move(*it, pos.is_chess960()) << ": " << cnt << sync_endl; + sync_cout << UCI::move(ms.move, 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 @@ -252,8 +252,8 @@ void Search::think() { } } - for (size_t i = 0; i < Threads.size(); ++i) - Threads[i]->maxPly = 0; + for (Thread* th : Threads) + th->maxPly = 0; Threads.timer->run = true; Threads.timer->notify_one(); // Wake up the recurring timer @@ -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()); + std::cout << " ponder " << UCI::move(RootMoves[0].pv[1], RootPos.is_chess960()); std::cout << sync_endl; } @@ -323,8 +323,8 @@ namespace { // Save the last iteration's scores before first PV line is searched and // all the move scores except the (new) PV are set to -VALUE_INFINITE. - for (size_t i = 0; i < RootMoves.size(); ++i) - RootMoves[i].previousScore = RootMoves[i].score; + for (RootMove& rm : RootMoves) + rm.previousScore = rm.score; // MultiPV loop. We perform a full root search for each PV line for (PVIdx = 0; PVIdx < std::min(multiPV, RootMoves.size()) && !Signals.stop; ++PVIdx) @@ -458,13 +458,12 @@ namespace { Move pv[MAX_PLY+1], quietsSearched[64]; StateInfo st; TTEntry* tte; - bool ttHit; 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,7 +476,7 @@ namespace { splitPoint = ss->splitPoint; bestMove = splitPoint->bestMove; bestValue = splitPoint->bestValue; - tte = NULL; + tte = nullptr; ttHit = false; ttMove = excludedMove = MOVE_NONE; ttValue = VALUE_NONE; @@ -540,7 +539,7 @@ namespace { // If ttMove is quiet, update killers, history, counter move and followup move on TT hit if (ttValue >= beta && ttMove && !pos.capture_or_promotion(ttMove) && !inCheck) - update_stats(pos, ss, ttMove, depth, NULL, 0); + update_stats(pos, ss, ttMove, depth, nullptr, 0); return ttValue; } @@ -568,7 +567,7 @@ namespace { 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.get_generation()); + MOVE_NONE, VALUE_NONE, TT.generation()); return value; } @@ -585,7 +584,7 @@ namespace { 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? @@ -598,7 +597,7 @@ namespace { eval = ss->staticEval = (ss-1)->currentMove != MOVE_NULL ? evaluate(pos) : -(ss-1)->staticEval + 2 * Eval::Tempo; - tte->save(posKey, VALUE_NONE, BOUND_NONE, DEPTH_NONE, MOVE_NONE, ss->staticEval, TT.get_generation()); + tte->save(posKey, VALUE_NONE, BOUND_NONE, DEPTH_NONE, MOVE_NONE, ss->staticEval, TT.generation()); } if (ss->skipEarlyPruning) @@ -633,7 +632,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 @@ -651,7 +650,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; @@ -784,12 +783,12 @@ 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; } if (PvNode) - (ss+1)->pv = NULL; + (ss+1)->pv = nullptr; extension = DEPTH_ZERO; captureOrPromotion = pos.capture_or_promotion(move); @@ -830,9 +829,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 - && !captureOrPromotion + // Step 13. Pruning at shallow depth + if ( !captureOrPromotion && !inCheck && !dangerous && bestValue > VALUE_MATED_IN_MAX_PLY) @@ -907,7 +905,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]) @@ -917,7 +915,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); @@ -1084,7 +1082,7 @@ moves_loop: // When in check and at SpNode search starts from here tte->save(posKey, value_to_tt(bestValue, ss->ply), bestValue >= beta ? BOUND_LOWER : PvNode && bestMove ? BOUND_EXACT : BOUND_UPPER, - depth, bestMove, ss->staticEval, TT.get_generation()); + depth, bestMove, ss->staticEval, TT.generation()); assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); @@ -1110,11 +1108,10 @@ moves_loop: // When in check and at SpNode search starts from here Move pv[MAX_PLY+1]; StateInfo st; TTEntry* tte; - bool ttHit; Key posKey; Move ttMove, move, bestMove; Value bestValue, value, ttValue, futilityValue, futilityBase, oldAlpha; - bool givesCheck, evasionPrunable; + bool ttHit, givesCheck, evasionPrunable; Depth ttDepth; if (PvNode) @@ -1167,7 +1164,7 @@ moves_loop: // When in check and at SpNode search starts from here 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? @@ -1184,7 +1181,7 @@ moves_loop: // When in check and at SpNode search starts from here { if (!ttHit) tte->save(pos.key(), value_to_tt(bestValue, ss->ply), BOUND_LOWER, - DEPTH_NONE, MOVE_NONE, ss->staticEval, TT.get_generation()); + DEPTH_NONE, MOVE_NONE, ss->staticEval, TT.generation()); return bestValue; } @@ -1212,8 +1209,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)) @@ -1222,13 +1218,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; @@ -1242,8 +1238,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; @@ -1283,7 +1278,7 @@ moves_loop: // When in check and at SpNode search starts from here else // Fail high { tte->save(posKey, value_to_tt(value, ss->ply), BOUND_LOWER, - ttDepth, move, ss->staticEval, TT.get_generation()); + ttDepth, move, ss->staticEval, TT.generation()); return value; } @@ -1298,7 +1293,7 @@ moves_loop: // When in check and at SpNode search starts from here tte->save(posKey, value_to_tt(bestValue, ss->ply), PvNode && bestValue > oldAlpha ? BOUND_EXACT : BOUND_UPPER, - ttDepth, bestMove, ss->staticEval, TT.get_generation()); + ttDepth, bestMove, ss->staticEval, TT.generation()); assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); @@ -1425,9 +1420,9 @@ moves_loop: // When in check and at SpNode search starts from here 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; + for (Thread* th : Threads) + if (th->maxPly > selDepth) + selDepth = th->maxPly; for (size_t i = 0; i < uciPVSize; ++i) { @@ -1448,15 +1443,19 @@ 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() + << " 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 << " 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(); @@ -1480,7 +1479,7 @@ void RootMove::insert_pv_in_tt(Position& pos) { TTEntry* tte = TT.probe(pos.key(), ttHit); 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.get_generation()); + tte->save(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, pv[idx], VALUE_NONE, TT.generation()); assert(MoveList(pos).contains(pv[idx])); @@ -1497,7 +1496,7 @@ void Thread::idle_loop() { // Pointer 'this_sp' is not null only if we are called from split(), and not // at the thread creation. This means we are the split point's master. - SplitPoint* this_sp = splitPointsSize ? activeSplitPoint : NULL; + SplitPoint* this_sp = splitPointsSize ? activeSplitPoint : nullptr; assert(!this_sp || (this_sp->masterThread == this && searching)); @@ -1521,7 +1520,7 @@ void Thread::idle_loop() { sp->mutex.lock(); - assert(activePosition == NULL); + assert(activePosition == nullptr); activePosition = &pos; @@ -1540,7 +1539,7 @@ void Thread::idle_loop() { assert(searching); searching = false; - activePosition = NULL; + activePosition = nullptr; sp->slavesMask.reset(idx); sp->allSlavesSearching = false; sp->nodes += pos.nodes_searched(); @@ -1565,7 +1564,7 @@ void Thread::idle_loop() { for (size_t i = 0; i < Threads.size(); ++i) { const int size = Threads[i]->splitPointsSize; // Local copy - sp = size ? &Threads[i]->splitPoints[size - 1] : NULL; + sp = size ? &Threads[i]->splitPoints[size - 1] : nullptr; if ( sp && sp->allSlavesSearching @@ -1592,22 +1591,19 @@ void Thread::idle_loop() { } // Grab the lock to avoid races with Thread::notify_one() - mutex.lock(); + std::unique_lock lk(mutex); // If we are master and all slaves have finished then exit idle_loop if (this_sp && this_sp->slavesMask.none()) { assert(!searching); - mutex.unlock(); break; } // If we are not searching, wait for a condition to be signaled instead of // wasting CPU time polling for work. if (!searching && !exit) - sleepCondition.wait(mutex); - - mutex.unlock(); + sleepCondition.wait(lk); } } @@ -1652,10 +1648,10 @@ 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 (Thread* th : Threads) + for (int i = 0; i < th->splitPointsSize; ++i) { - SplitPoint& sp = Threads[i]->splitPoints[j]; + SplitPoint& sp = th->splitPoints[i]; sp.mutex.lock();