From: Marco Costalba Date: Fri, 20 Feb 2015 09:36:45 +0000 (+0100) Subject: Sync with master X-Git-Url: https://git.sesse.net/?p=stockfish;a=commitdiff_plain;h=40548c9153ea89c0b27b198efb443c5bb9b9c490;hp=-c Sync with master bench: 7911944 --- 40548c9153ea89c0b27b198efb443c5bb9b9c490 diff --combined src/evaluate.cpp index 9af22264,7ff7dfc1..6c46cb4b --- a/src/evaluate.cpp +++ b/src/evaluate.cpp @@@ -73,17 -73,18 +73,17 @@@ namespace namespace Tracing { - enum Terms { // First 8 entries are for PieceType + enum Term { // First 8 entries are for PieceType MATERIAL = 8, IMBALANCE, MOBILITY, THREAT, PASSED, SPACE, TOTAL, TERMS_NB }; Score scores[COLOR_NB][TERMS_NB]; - EvalInfo ei; - ScaleFactor sf; + + std::ostream& operator<<(std::ostream& os, Term idx); double to_cp(Value v); void write(int idx, Color c, Score s); void write(int idx, Score w, Score b = SCORE_ZERO); - void print(std::stringstream& ss, const char* name, int idx); std::string do_trace(const Position& pos); } @@@ -116,8 -117,8 +116,8 @@@ S( 25, 41), S( 25, 41), S(25, 41), S(25, 41) } }; - // Outpost[PieceType][Square] contains bonuses for knights and bishops outposts, - // indexed by piece type and square (from white's point of view). + // Outpost[Bishop/Knight][Square] contains bonuses for knights and bishops + // outposts, indexed by piece type and square (from white's point of view). const Value Outpost[][SQUARE_NB] = { {// A B C D E F G H V(0), V(0), V(0), V(0), V(0), V(0), V(0), V(0), // Knights @@@ -146,7 -147,7 +146,7 @@@ // ThreatenedByPawn[PieceType] contains a penalty according to which piece // type is attacked by an enemy pawn. - const Score ThreatenedByPawn[] = { + const Score ThreatenedByPawn[PIECE_TYPE_NB] = { S(0, 0), S(0, 0), S(87, 118), S(84, 122), S(114, 203), S(121, 217) }; @@@ -176,7 -177,7 +176,7 @@@ // by the space evaluation. In the middlegame, each side is given a bonus // based on how many squares inside this area are safe and available for // friendly minor pieces. - const Bitboard SpaceMask[] = { + const Bitboard SpaceMask[COLOR_NB] = { (FileCBB | FileDBB | FileEBB | FileFBB) & (Rank2BB | Rank3BB | Rank4BB), (FileCBB | FileDBB | FileEBB | FileFBB) & (Rank7BB | Rank6BB | Rank5BB) }; @@@ -187,7 -188,7 +187,7 @@@ // index to KingDanger[]. // // KingAttackWeights[PieceType] contains king attack weights by piece type - const int KingAttackWeights[] = { 0, 0, 7, 5, 4, 1 }; + const int KingAttackWeights[PIECE_TYPE_NB] = { 0, 0, 7, 5, 4, 1 }; // Bonuses for enemy's safe checks const int QueenContactCheck = 89; @@@ -213,12 -214,13 +213,12 @@@ template void init_eval_info(const Position& pos, EvalInfo& ei) { - const Color Them = (Us == WHITE ? BLACK : WHITE); + const Color Them = (Us == WHITE ? BLACK : WHITE); const Square Down = (Us == WHITE ? DELTA_S : DELTA_N); ei.pinnedPieces[Us] = pos.pinned_pieces(Us); - - Bitboard b = ei.attackedBy[Them][KING] = pos.attacks_from(pos.king_square(Them)); ei.attackedBy[Us][ALL_PIECES] = ei.attackedBy[Us][PAWN] = ei.pi->pawn_attacks(Us); + Bitboard b = ei.attackedBy[Them][KING] = pos.attacks_from(pos.king_square(Them)); // Init king safety tables only if we are going to use them if (pos.non_pawn_material(Us) >= QueenValueMg) @@@ -412,10 -414,10 +412,10 @@@ // attacked and undefended squares around our king and the quality of // the pawn shelter (current 'score' value). attackUnits = std::min(74, ei.kingAttackersCount[Them] * ei.kingAttackersWeight[Them]) - + 8 * ei.kingAdjacentZoneAttacksCount[Them] + + 8 * ei.kingAdjacentZoneAttacksCount[Them] + 25 * popcount(undefended) - + 11 * (ei.pinnedPieces[Us] != 0) - - mg_value(score) * 31 / 256 + + 11 * (ei.pinnedPieces[Us] != 0) + - mg_value(score) / 8 - !pos.count(Them) * 60; // Analyse the enemy's safe queen contact checks. Firstly, find the @@@ -802,7 -804,7 +802,7 @@@ v /= int(PHASE_MIDGAME); - // In case of tracing add all single evaluation contributions for both white and black + // In case of tracing add all single evaluation terms for both white and black if (Trace) { Tracing::write(Tracing::MATERIAL, pos.psq_score()); @@@ -813,37 -815,46 +813,37 @@@ Tracing::write(Tracing::SPACE, apply_weight(evaluate_space(pos, ei), Weights[Space]) , apply_weight(evaluate_space(pos, ei), Weights[Space])); Tracing::write(Tracing::TOTAL, score); - Tracing::ei = ei; - Tracing::sf = sf; } return (pos.side_to_move() == WHITE ? v : -v) + Eval::Tempo; } - // Tracing function definitions + // Tracing functions double Tracing::to_cp(Value v) { return double(v) / PawnValueEg; } void Tracing::write(int idx, Color c, Score s) { scores[c][idx] = s; } void Tracing::write(int idx, Score w, Score b) { - - write(idx, WHITE, w); - write(idx, BLACK, b); + scores[WHITE][idx] = w, scores[BLACK][idx] = b; } - void Tracing::print(std::stringstream& ss, const char* name, int idx) { - - Score wScore = scores[WHITE][idx]; - Score bScore = scores[BLACK][idx]; - - switch (idx) { - case MATERIAL: case IMBALANCE: case PAWN: case TOTAL: - ss << std::setw(15) << name << " | --- --- | --- --- | " - << std::setw(5) << to_cp(mg_value(wScore - bScore)) << " " - << std::setw(5) << to_cp(eg_value(wScore - bScore)) << " \n"; - break; - default: - ss << std::setw(15) << name << " | " << std::noshowpos - << std::setw(5) << to_cp(mg_value(wScore)) << " " - << std::setw(5) << to_cp(eg_value(wScore)) << " | " - << std::setw(5) << to_cp(mg_value(bScore)) << " " - << std::setw(5) << to_cp(eg_value(bScore)) << " | " - << std::setw(5) << to_cp(mg_value(wScore - bScore)) << " " - << std::setw(5) << to_cp(eg_value(wScore - bScore)) << " \n"; - } + std::ostream& Tracing::operator<<(std::ostream& os, Term t) { + + double wScore[] = { to_cp(mg_value(scores[WHITE][t])), to_cp(eg_value(scores[WHITE][t])) }; + double bScore[] = { to_cp(mg_value(scores[BLACK][t])), to_cp(eg_value(scores[BLACK][t])) }; + + if (t == MATERIAL || t == IMBALANCE || t == Term(PAWN) || t == TOTAL) + os << " --- --- | --- --- | "; + else + os << std::setw(5) << wScore[MG] << " " << std::setw(5) << wScore[EG] << " | " + << std::setw(5) << bScore[MG] << " " << std::setw(5) << bScore[EG] << " | "; + + os << std::setw(5) << wScore[MG] - bScore[MG] << " " + << std::setw(5) << wScore[EG] - bScore[EG] << " \n"; + + return os; } std::string Tracing::do_trace(const Position& pos) { @@@ -857,21 -868,23 +857,21 @@@ ss << std::showpoint << std::noshowpos << std::fixed << std::setprecision(2) << " Eval term | White | Black | Total \n" << " | MG EG | MG EG | MG EG \n" - << "----------------+-------------+-------------+-------------\n"; - - print(ss, "Material", MATERIAL); - print(ss, "Imbalance", IMBALANCE); - print(ss, "Pawns", PAWN); - print(ss, "Knights", KNIGHT); - print(ss, "Bishops", BISHOP); - print(ss, "Rooks", ROOK); - print(ss, "Queens", QUEEN); - print(ss, "Mobility", MOBILITY); - print(ss, "King safety", KING); - print(ss, "Threats", THREAT); - print(ss, "Passed pawns", PASSED); - print(ss, "Space", SPACE); - - ss << "----------------+-------------+-------------+-------------\n"; - print(ss, "Total", TOTAL); + << "----------------+-------------+-------------+-------------\n" + << " Material | " << Term(MATERIAL) + << " Imbalance | " << Term(IMBALANCE) + << " Pawns | " << Term(PAWN) + << " Knights | " << Term(KNIGHT) + << " Bishop | " << Term(BISHOP) + << " Rooks | " << Term(ROOK) + << " Queens | " << Term(QUEEN) + << " Mobility | " << Term(MOBILITY) + << " King safety | " << Term(KING) + << " Threats | " << Term(THREAT) + << " Passed pawns | " << Term(PASSED) + << " Space | " << Term(SPACE) + << "----------------+-------------+-------------+-------------\n" + << " Total | " << Term(TOTAL); ss << "\nTotal Evaluation: " << to_cp(v) << " (white side)\n"; diff --combined src/search.cpp index 9d7c1ef6,15b93a72..04d67afe --- a/src/search.cpp +++ b/src/search.cpp @@@ -66,29 -66,22 +66,29 @@@ namespace // Different node types, used as template parameter enum NodeType { Root, PV, NonPV }; - // Dynamic razoring margin based on depth + // Razoring and futility margin based on depth inline Value razor_margin(Depth d) { return Value(512 + 32 * d); } + inline Value futility_margin(Depth d) { return Value(200 * d); } - // Futility lookup tables (initialized at startup) and their access functions - int FutilityMoveCounts[2][16]; // [improving][depth] + // Futility and reductions lookup tables, initialized at startup + int FutilityMoveCounts[2][16]; // [improving][depth] + Depth Reductions[2][2][64][64]; // [pv][improving][depth][moveNumber] - inline Value futility_margin(Depth d) { - return Value(200 * d); + template inline Depth reduction(bool i, Depth d, int mn) { + return Reductions[PvNode][i][std::min(d, 63 * ONE_PLY)][std::min(mn, 63)]; } - // Reduction lookup tables (initialized at startup) and their access function - int8_t Reductions[2][2][64][64]; // [pv][improving][depth][moveNumber] + // Skill struct is used to implement strength limiting + struct Skill { + Skill(int l) : level(l) {} + bool enabled() const { return level < 20; } + bool time_to_pick(Depth depth) const { return depth / ONE_PLY == 1 + level; } + Move best_move(size_t multiPV) { return best ? best : pick_best(multiPV); } + Move pick_best(size_t multiPV); - template inline Depth reduction(bool i, Depth d, int mn) { - return (Depth) Reductions[PvNode][i][std::min(int(d), 63)][std::min(mn, 63)]; - } + int level; + Move best = MOVE_NONE; + }; size_t PVIdx; TimeManager TimeMgr; @@@ -109,6 -102,26 +109,6 @@@ Value value_from_tt(Value v, int ply); void update_pv(Move* pv, Move move, Move* childPv); void update_stats(const Position& pos, Stack* ss, Move move, Depth depth, Move* quiets, int quietsCnt); - string uci_pv(const Position& pos, Depth depth, Value alpha, Value beta); - - struct Skill { - Skill(int l, size_t rootSize) : level(l), - candidates(l < 20 ? std::min(4, (int)rootSize) : 0), - best(MOVE_NONE) {} - ~Skill() { - if (candidates) // Swap best PV line with the sub-optimal one - std::swap(RootMoves[0], *std::find(RootMoves.begin(), - RootMoves.end(), best ? best : pick_move())); - } - - size_t candidates_size() const { return candidates; } - bool time_to_pick(Depth depth) const { return depth / ONE_PLY == 1 + level; } - Move pick_move(); - - int level; - size_t candidates; - Move best; - }; } // namespace @@@ -117,23 -130,25 +117,23 @@@ void Search::init() { - // Init reductions array - for (int d = 1; d < 64; ++d) - for (int mc = 1; mc < 64; ++mc) - { - double pvRed = 0.00 + log(double(d)) * log(double(mc)) / 3.00; - double nonPVRed = 0.33 + log(double(d)) * log(double(mc)) / 2.25; + const double K[][2] = {{ 0.83, 2.25 }, { 0.50, 3.00 }}; - Reductions[1][1][d][mc] = int8_t( pvRed >= 1.0 ? pvRed + 0.5: 0); - Reductions[0][1][d][mc] = int8_t(nonPVRed >= 1.0 ? nonPVRed + 0.5: 0); + for (int pv = 0; pv <= 1; ++pv) + for (int imp = 0; imp <= 1; ++imp) + for (int d = 1; d < 64; ++d) + for (int mc = 1; mc < 64; ++mc) + { + double r = K[pv][0] + log(d) * log(mc) / K[pv][1]; - Reductions[1][0][d][mc] = Reductions[1][1][d][mc]; - Reductions[0][0][d][mc] = Reductions[0][1][d][mc]; + if (r >= 1.5) + Reductions[pv][imp][d][mc] = int(r) * ONE_PLY; - // Increase reduction when eval is not improving - if (Reductions[0][0][d][mc] >= 2) - Reductions[0][0][d][mc] += 1; - } + // Increase reduction when eval is not improving + if (!pv && !imp && Reductions[pv][imp][d][mc] >= 2 * ONE_PLY) + Reductions[pv][imp][d][mc] += ONE_PLY; + } - // Init futility move count array for (int d = 0; d < 16; ++d) { FutilityMoveCounts[0][d] = int(2.4 + 0.773 * pow(d + 0.00, 1.8)); @@@ -152,19 -167,19 +152,19 @@@ uint64_t Search::perft(Position& pos, D CheckInfo ci(pos); const bool leaf = (depth == 2 * ONE_PLY); - for (MoveList it(pos); *it; ++it) + for (const auto& m : MoveList(pos)) { if (Root && depth <= ONE_PLY) cnt = 1, nodes++; else { - pos.do_move(*it, st, pos.gives_check(*it, ci)); + pos.do_move(m, st, pos.gives_check(m, ci)); cnt = leaf ? MoveList(pos).size() : perft(pos, depth - ONE_PLY); nodes += cnt; - pos.undo_move(*it); + pos.undo_move(m); } if (Root) - sync_cout << UCI::move(*it, pos.is_chess960()) << ": " << cnt << sync_endl; + sync_cout << UCI::move(m, pos.is_chess960()) << ": " << cnt << sync_endl; } return nodes; } @@@ -199,7 -214,7 +199,7 @@@ void Search::think() if (RootMoves.empty()) { - RootMoves.push_back(MOVE_NONE); + RootMoves.push_back(RootMove(MOVE_NONE)); sync_cout << "info depth 0 score " << UCI::value(RootPos.checkers() ? -VALUE_MATE : VALUE_DRAW) << sync_endl; @@@ -237,8 -252,8 +237,8 @@@ } } - 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 @@@ -294,14 -309,11 +294,14 @@@ namespace Followupmoves.clear(); size_t multiPV = Options["MultiPV"]; - Skill skill(Options["Skill Level"], RootMoves.size()); + Skill skill(Options["Skill Level"]); - // Do we have to play with skill handicap? In this case enable MultiPV search - // that we will use behind the scenes to retrieve a set of possible moves. - multiPV = std::max(multiPV, skill.candidates_size()); + // When playing with strength handicap enable MultiPV search that we will + // use behind the scenes to retrieve a set of possible moves. + if (skill.enabled()) + multiPV = std::max(multiPV, (size_t)4); + + multiPV = std::min(multiPV, RootMoves.size()); // Iterative deepening loop until requested to stop or target depth reached while (++depth < DEPTH_MAX && !Signals.stop && (!Limits.depth || depth <= Limits.depth)) @@@ -311,11 -323,11 +311,11 @@@ // 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) + for (PVIdx = 0; PVIdx < multiPV && !Signals.stop; ++PVIdx) { // Reset aspiration window starting size if (depth >= 5 * ONE_PLY) @@@ -356,7 -368,7 +356,7 @@@ if ( multiPV == 1 && (bestValue <= alpha || bestValue >= beta) && Time::now() - SearchTime > 3000) - sync_cout << uci_pv(pos, depth, alpha, beta) << sync_endl; + sync_cout << UCI::pv(pos, depth, alpha, beta) << sync_endl; // In case of failing low/high increase aspiration window and // re-search, otherwise exit the loop. @@@ -388,13 -400,14 +388,13 @@@ sync_cout << "info nodes " << RootPos.nodes_searched() << " time " << Time::now() - SearchTime << sync_endl; - else if ( PVIdx + 1 == std::min(multiPV, RootMoves.size()) - || Time::now() - SearchTime > 3000) - sync_cout << uci_pv(pos, depth, alpha, beta) << sync_endl; + else if (PVIdx + 1 == multiPV || Time::now() - SearchTime > 3000) + sync_cout << UCI::pv(pos, depth, alpha, beta) << sync_endl; } - // If skill levels are enabled and time is up, pick a sub-optimal best move - if (skill.candidates_size() && skill.time_to_pick(depth)) - skill.pick_move(); + // If skill level is enabled and time is up, pick a sub-optimal best move + if (skill.enabled() && skill.time_to_pick(depth)) + skill.pick_best(multiPV); // Have we found a "mate in x"? if ( Limits.mate @@@ -423,11 -436,6 +423,11 @@@ } } } + + // If skill level is enabled, swap best PV line with the sub-optimal one + if (skill.enabled()) + std::swap(RootMoves[0], *std::find(RootMoves.begin(), + RootMoves.end(), skill.best_move(multiPV))); } @@@ -469,7 -477,7 +469,7 @@@ splitPoint = ss->splitPoint; bestMove = splitPoint->bestMove; bestValue = splitPoint->bestValue; - tte = NULL; + tte = nullptr; ttHit = false; ttMove = excludedMove = MOVE_NONE; ttValue = VALUE_NONE; @@@ -532,7 -540,7 +532,7 @@@ // 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; } @@@ -781,7 -789,7 +781,7 @@@ moves_loop: // When in check and at SpN } if (PvNode) - (ss+1)->pv = NULL; + (ss+1)->pv = nullptr; extension = DEPTH_ZERO; captureOrPromotion = pos.capture_or_promotion(move); @@@ -872,7 -880,7 +872,7 @@@ } // Speculative prefetch as early as possible - prefetch((char*)TT.first_entry(pos.key_after(move))); + prefetch(TT.first_entry(pos.key_after(move))); // Check for legality just before making the move if (!RootNode && !SpNode && !pos.legal(move, ci.pinned)) @@@ -1034,7 -1042,9 +1034,9 @@@ && 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); @@@ -1238,7 -1248,7 +1240,7 @@@ continue; // Speculative prefetch as early as possible - prefetch((char*)TT.first_entry(pos.key_after(move))); + prefetch(TT.first_entry(pos.key_after(move))); // Check for legality just before making the move if (!pos.legal(move, ci.pinned)) @@@ -1344,7 -1354,6 +1346,7 @@@ // played quiet moves. Value bonus = Value((depth / ONE_PLY) * (depth / ONE_PLY)); History.update(pos.moved_piece(move), to_sq(move), bonus); + for (int i = 0; i < quietsCnt; ++i) { Move m = quiets[i]; @@@ -1365,95 -1374,98 +1367,95 @@@ } - // When playing with a strength handicap, choose best move among the first 'candidates' - // RootMoves using a statistical rule dependent on 'level'. Idea by Heinz van Saanen. + // When playing with strength handicap, choose best move among a set of RootMoves + // using a statistical rule dependent on 'level'. Idea by Heinz van Saanen. - Move Skill::pick_move() { + Move Skill::pick_best(size_t multiPV) { // PRNG sequence should be non-deterministic, so we seed it with the time at init static PRNG rng(Time::now()); // RootMoves are already sorted by score in descending order - int variance = std::min(RootMoves[0].score - RootMoves[candidates - 1].score, PawnValueMg); + int variance = std::min(RootMoves[0].score - RootMoves[multiPV - 1].score, PawnValueMg); int weakness = 120 - 2 * level; int maxScore = -VALUE_INFINITE; - best = MOVE_NONE; // Choose best move. For each move score we add two terms both dependent on - // weakness. One deterministic and bigger for weaker moves, and one random, + // weakness. One deterministic and bigger for weaker levels, and one random, // then we choose the move with the resulting highest score. - for (size_t i = 0; i < candidates; ++i) + for (size_t i = 0; i < multiPV; ++i) { - int score = RootMoves[i].score; - // This is our magic formula - score += ( weakness * int(RootMoves[0].score - score) - + variance * (rng.rand() % weakness)) / 128; + int push = ( weakness * int(RootMoves[0].score - RootMoves[i].score) + + variance * (rng.rand() % weakness)) / 128; - if (score > maxScore) + if (RootMoves[i].score + push > maxScore) { - maxScore = score; + maxScore = RootMoves[i].score + push; best = RootMoves[i].pv[0]; } } return best; } +} // namespace - // uci_pv() formats PV information according to the UCI protocol. UCI - // requires that all (if any) unsearched PV lines are sent using a previous - // search score. - string uci_pv(const Position& pos, Depth depth, Value alpha, Value beta) { +/// UCI::pv() formats PV information according to the UCI protocol. UCI requires +/// that all (if any) unsearched PV lines are sent using a previous search score. - std::stringstream ss; - Time::point elapsed = Time::now() - SearchTime + 1; - size_t uciPVSize = std::min((size_t)Options["MultiPV"], RootMoves.size()); - int selDepth = 0; +string UCI::pv(const Position& pos, Depth depth, Value alpha, Value beta) { - for (size_t i = 0; i < Threads.size(); ++i) - if (Threads[i]->maxPly > selDepth) - selDepth = Threads[i]->maxPly; + std::stringstream ss; + Time::point elapsed = Time::now() - SearchTime + 1; + size_t multiPV = std::min((size_t)Options["MultiPV"], RootMoves.size()); + int selDepth = 0; - for (size_t i = 0; i < uciPVSize; ++i) - { - bool updated = (i <= PVIdx); + for (Thread* th : Threads) + if (th->maxPly > selDepth) + selDepth = th->maxPly; - if (depth == ONE_PLY && !updated) - continue; + for (size_t i = 0; i < multiPV; ++i) + { + bool updated = (i <= PVIdx); - Depth d = updated ? depth : depth - ONE_PLY; - Value v = updated ? RootMoves[i].score : RootMoves[i].previousScore; + if (depth == ONE_PLY && !updated) + continue; - bool tb = TB::RootInTB && abs(v) < VALUE_MATE - MAX_PLY; - v = tb ? TB::Score : v; + Depth d = updated ? depth : depth - ONE_PLY; + Value v = updated ? RootMoves[i].score : RootMoves[i].previousScore; - if (ss.rdbuf()->in_avail()) // Not at first line - ss << "\n"; + bool tb = TB::RootInTB && abs(v) < VALUE_MATE - MAX_PLY; + v = tb ? TB::Score : v; - ss << "info depth " << d / ONE_PLY - << " seldepth " << selDepth - << " multipv " << i + 1 - << " score " << UCI::value(v); + if (ss.rdbuf()->in_avail()) // Not at first line + ss << "\n"; - if (!tb && i == PVIdx) - ss << (v >= beta ? " lowerbound" : v <= alpha ? " upperbound" : ""); + ss << "info" + << " depth " << d / ONE_PLY + << " seldepth " << selDepth + << " multipv " << i + 1 + << " score " << UCI::value(v); - ss << " nodes " << pos.nodes_searched() - << " nps " << pos.nodes_searched() * 1000 / elapsed; + if (!tb && i == PVIdx) + ss << (v >= beta ? " lowerbound" : v <= alpha ? " upperbound" : ""); - if (elapsed > 1000) // Earlier makes little sense - ss << " hashfull " << TT.hashfull(); + ss << " nodes " << pos.nodes_searched() + << " nps " << pos.nodes_searched() * 1000 / elapsed; - ss << " tbhits " << TB::Hits - << " time " << elapsed - << " pv"; + if (elapsed > 1000) // Earlier makes little sense + ss << " hashfull " << TT.hashfull(); - for (size_t j = 0; j < RootMoves[i].pv.size(); ++j) - ss << " " << UCI::move(RootMoves[i].pv[j], pos.is_chess960()); - } + ss << " tbhits " << TB::Hits + << " time " << elapsed + << " pv"; - return ss.str(); + for (Move m : RootMoves[i].pv) + ss << " " << UCI::move(m, pos.is_chess960()); } -} // namespace + return ss.str(); +} /// RootMove::insert_pv_in_tt() is called at the end of a search iteration, and @@@ -1463,22 -1475,22 +1465,22 @@@ void RootMove::insert_pv_in_tt(Position& pos) { StateInfo state[MAX_PLY], *st = state; - size_t idx = 0; + bool ttHit; - for ( ; idx < pv.size(); ++idx) + for (Move m : pv) { - bool ttHit; - TTEntry* tte = TT.probe(pos.key(), ttHit); + assert(MoveList(pos).contains(m)); - 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()); + TTEntry* tte = TT.probe(pos.key(), ttHit); - assert(MoveList(pos).contains(pv[idx])); + if (!ttHit || tte->move() != m) // Don't overwrite correct entries + tte->save(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, m, VALUE_NONE, TT.generation()); - pos.do_move(pv[idx], *st++); + pos.do_move(m, *st++, pos.gives_check(m, CheckInfo(pos))); } - while (idx) pos.undo_move(pv[--idx]); + for (size_t i = pv.size(); i > 0; ) + pos.undo_move(pv[--i]); } @@@ -1487,25 -1499,22 +1489,25 @@@ /// 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) +bool RootMove::extract_ponder_from_tt(Position& pos) { StateInfo st; - bool found; + bool ttHit; 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.do_move(pv[0], st, pos.gives_check(pv[0], CheckInfo(pos))); + TTEntry* tte = TT.probe(pos.key(), ttHit); pos.undo_move(pv[0]); - pv.push_back(m); - return m; + + if (ttHit) + { + Move m = tte->move(); // Local copy to be SMP safe + if (MoveList(pos).contains(m)) + return pv.push_back(m), true; + } + + return false; } @@@ -1515,7 -1524,7 +1517,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)); @@@ -1539,7 -1548,7 +1541,7 @@@ sp->mutex.lock(); - assert(activePosition == NULL); + assert(activePosition == nullptr); activePosition = &pos; @@@ -1558,7 -1567,7 +1560,7 @@@ assert(searching); searching = false; - activePosition = NULL; + activePosition = nullptr; sp->slavesMask.reset(idx); sp->allSlavesSearching = false; sp->nodes += pos.nodes_searched(); @@@ -1579,50 -1588,80 +1581,77 @@@ // 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; ++ sp = size ? &Threads[i]->splitPoints[size - 1] : nullptr; + + 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] : nullptr; + assert(this != Threads[i]); + assert(!(this_sp && this_sp->slavesMask.none())); + assert(Threads.size() > 2); + + // Prefer to join to SP with few parents to reduce the probability + // that a cut-off occurs above us, and hence we waste our work. + 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() - 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); } } @@@ -1667,10 -1706,10 +1696,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 (size_t j = 0; j < Threads[i]->splitPointsSize; ++j) + for (Thread* th : Threads) - for (int i = 0; i < th->splitPointsSize; ++i) ++ for (size_t i = 0; i < th->splitPointsSize; ++i) { - SplitPoint& sp = Threads[i]->splitPoints[j]; + SplitPoint& sp = th->splitPoints[i]; sp.mutex.lock(); diff --combined src/thread.cpp index c25fc129,18870021..279d9cfe --- a/src/thread.cpp +++ b/src/thread.cpp @@@ -33,13 -33,19 +33,13 @@@ extern void check_time() namespace { - // start_routine() is the C function which is called when a new thread - // is launched. It is a wrapper to the virtual function idle_loop(). - - extern "C" { long start_routine(ThreadBase* th) { th->idle_loop(); return 0; } } - - // Helpers to launch a thread after creation and joining before delete. Must be // outside Thread c'tor and d'tor because the object must be fully initialized // when start_routine (and hence virtual idle_loop) is called and when joining. template T* new_thread() { T* th = new T(); - thread_create(th->handle, start_routine, th); // Will go to sleep + th->nativeThread = std::thread(&ThreadBase::idle_loop, th); // Will go to sleep return th; } @@@ -50,7 -56,7 +50,7 @@@ th->mutex.unlock(); th->notify_one(); - thread_join(th->handle); // Wait for thread termination + th->nativeThread.join(); // Wait for thread termination delete th; } @@@ -61,8 -67,9 +61,8 @@@ void ThreadBase::notify_one() { - mutex.lock(); + std::unique_lock(this->mutex); sleepCondition.notify_one(); - mutex.unlock(); } @@@ -70,8 -77,9 +70,8 @@@ void ThreadBase::wait_for(volatile const bool& condition) { - mutex.lock(); - while (!condition) sleepCondition.wait(mutex); - mutex.unlock(); + std::unique_lock lk(mutex); + sleepCondition.wait(lk, [&]{ return condition; }); } @@@ -81,9 -89,10 +81,10 @@@ Thread::Thread() /* : splitPoints() */ { // Initialization of non POD broken in MSVC searching = false; - maxPly = splitPointsSize = 0; + maxPly = 0; + splitPointsSize = 0; - activeSplitPoint = NULL; - activePosition = NULL; + activeSplitPoint = nullptr; + activePosition = nullptr; idx = Threads.size(); // Starts from 0 } @@@ -115,7 -124,7 +116,7 @@@ bool Thread::available_to(const Thread // Make a local copy to be sure it doesn't become zero under our feet while // testing next condition and so leading to an out of bounds access. - const int size = splitPointsSize; + const size_t size = splitPointsSize; // No split points means that the thread is available as a slave for any // other thread otherwise apply the "helpful master" concept if possible. @@@ -170,11 -179,12 +171,12 @@@ void Thread::split(Position& pos, Stack sp.allSlavesSearching = true; // Must be set under lock protection ++splitPointsSize; activeSplitPoint = &sp; - activePosition = NULL; + activePosition = nullptr; Thread* slave; - while ((slave = Threads.available_slave(this)) != nullptr) + while ( sp.slavesMask.count() < MAX_SLAVES_PER_SPLITPOINT - && (slave = Threads.available_slave(this)) != NULL) ++ && (slave = Threads.available_slave(this)) != nullptr) { sp.slavesMask.set(slave->idx); slave->activeSplitPoint = &sp; @@@ -223,12 -233,12 +225,12 @@@ void TimerThread::idle_loop() while (!exit) { - mutex.lock(); + std::unique_lock lk(mutex); if (!exit) - sleepCondition.wait_for(mutex, run ? Resolution : INT_MAX); + sleepCondition.wait_for(lk, std::chrono::milliseconds(run ? Resolution : INT_MAX)); - mutex.unlock(); + lk.unlock(); if (run) check_time(); @@@ -243,17 -253,17 +245,17 @@@ void MainThread::idle_loop() while (!exit) { - mutex.lock(); + std::unique_lock lk(mutex); thinking = false; while (!thinking && !exit) { Threads.sleepCondition.notify_one(); // Wake up the UI thread if needed - sleepCondition.wait(mutex); + sleepCondition.wait(lk); } - mutex.unlock(); + lk.unlock(); if (!exit) { @@@ -289,8 -299,8 +291,8 @@@ void ThreadPool::exit() delete_thread(timer); // As first because check_time() accesses threads data - for (iterator it = begin(); it != end(); ++it) - delete_thread(*it); + for (Thread* th : *this) + delete_thread(th); } @@@ -327,11 -337,11 +329,11 @@@ void ThreadPool::read_uci_options() Thread* ThreadPool::available_slave(const Thread* master) const { - for (const_iterator it = begin(); it != end(); ++it) - if ((*it)->available_to(master)) - return *it; + for (Thread* th : *this) + if (th->available_to(master)) + return th; - return NULL; + return nullptr; } @@@ -339,8 -349,10 +341,8 @@@ void ThreadPool::wait_for_think_finished() { - MainThread* th = main(); - th->mutex.lock(); - while (th->thinking) sleepCondition.wait(th->mutex); - th->mutex.unlock(); + std::unique_lock lk(main()->mutex); + sleepCondition.wait(lk, [&]{ return !main()->thinking; }); } @@@ -361,14 -373,14 +363,14 @@@ void ThreadPool::start_thinking(const P Limits = limits; if (states.get()) // If we don't set a new position, preserve current state { - SetupStates = states; // Ownership transfer here + SetupStates = std::move(states); // Ownership transfer here assert(!states.get()); } - for (MoveList it(pos); *it; ++it) + for (const auto& m : MoveList(pos)) if ( limits.searchmoves.empty() - || std::count(limits.searchmoves.begin(), limits.searchmoves.end(), *it)) - RootMoves.push_back(RootMove(*it)); + || std::count(limits.searchmoves.begin(), limits.searchmoves.end(), m)) + RootMoves.push_back(RootMove(m)); main()->thinking = true; main()->notify_one(); // Starts main thread diff --combined src/thread.h index 3f902dc1,04e9a370..54083d2e --- a/src/thread.h +++ b/src/thread.h @@@ -21,9 -21,6 +21,9 @@@ #define THREAD_H_INCLUDED #include +#include +#include +#include #include #include "material.h" @@@ -34,9 -31,39 +34,10 @@@ struct Thread; - const int MAX_THREADS = 128; - const int MAX_SPLITPOINTS_PER_THREAD = 8; + const size_t MAX_THREADS = 128; + const size_t MAX_SPLITPOINTS_PER_THREAD = 8; + const size_t MAX_SLAVES_PER_SPLITPOINT = 4; -/// Mutex and ConditionVariable struct are wrappers of the low level locking -/// machinery and are modeled after the corresponding C++11 classes. - -struct Mutex { - Mutex() { lock_init(l); } - ~Mutex() { lock_destroy(l); } - - void lock() { lock_grab(l); } - void unlock() { lock_release(l); } - -private: - friend struct ConditionVariable; - - Lock l; -}; - -struct ConditionVariable { - ConditionVariable() { cond_init(c); } - ~ConditionVariable() { cond_destroy(c); } - - void wait(Mutex& m) { cond_wait(c, m.l); } - void wait_for(Mutex& m, int ms) { timed_wait(c, m.l, ms); } - void notify_one() { cond_signal(c); } - -private: - WaitCondition c; -}; - - /// SplitPoint struct stores information shared by the threads searching in /// parallel below the same split point. It is populated at splitting time. @@@ -56,7 -83,7 +57,7 @@@ struct SplitPoint SplitPoint* parentSplitPoint; // Shared variable data - Mutex mutex; + std::mutex mutex; std::bitset slavesMask; volatile bool allSlavesSearching; volatile uint64_t nodes; @@@ -73,15 -100,16 +74,15 @@@ struct ThreadBase { - ThreadBase() : handle(NativeHandle()), exit(false) {} - virtual ~ThreadBase() {} + virtual ~ThreadBase() = default; virtual void idle_loop() = 0; void notify_one(); void wait_for(volatile const bool& b); - Mutex mutex; - ConditionVariable sleepCondition; - NativeHandle handle; - volatile bool exit; + std::thread nativeThread; + std::mutex mutex; + std::condition_variable sleepCondition; + volatile bool exit = false; }; @@@ -108,7 -136,7 +109,7 @@@ struct Thread : public ThreadBase size_t idx; int maxPly; SplitPoint* volatile activeSplitPoint; - volatile int splitPointsSize; + volatile size_t splitPointsSize; volatile bool searching; }; @@@ -117,17 -145,19 +118,17 @@@ /// special threads: the main one and the recurring timer. struct MainThread : public Thread { - MainThread() : thinking(true) {} // Avoid a race with start_thinking() virtual void idle_loop(); - volatile bool thinking; + volatile bool thinking = true; // Avoid a race with start_thinking() }; struct TimerThread : public ThreadBase { static const int Resolution = 5; // Millisec between two check_time() calls - TimerThread() : run(false) {} virtual void idle_loop(); - bool run; + bool run = false; }; @@@ -147,8 -177,8 +148,8 @@@ struct ThreadPool : public std::vector< void start_thinking(const Position&, const Search::LimitsType&, Search::StateStackPtr&); Depth minimumSplitDepth; - Mutex mutex; - ConditionVariable sleepCondition; + std::mutex mutex; + std::condition_variable sleepCondition; TimerThread* timer; };