X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=933b403070c7b42689544fc962a19525e236bfb3;hp=f600876e98e69ddd9aee98ac6c45ee14c377ce2a;hb=06e0d48794d9872ef627e15d5edf3bbcb7ad1752;hpb=ce24a229df4ddc7a9870515b5b710f259dcd50e3 diff --git a/src/search.cpp b/src/search.cpp index f600876e..933b4030 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -49,42 +49,34 @@ namespace { const bool FakeSplit = false; // Different node types, used as template parameter - enum NodeType { Root, PV, NonPV, SplitPointPV, SplitPointNonPV }; + enum NodeType { Root, PV, NonPV, SplitPointRoot, SplitPointPV, SplitPointNonPV }; // RootMove struct is used for moves at the root of the tree. For each root - // move, we store two scores, a node count, and a PV (really a refutation - // in the case of moves which fail low). Value pv_score is normally set at - // -VALUE_INFINITE for all non-pv moves, while non_pv_score is computed - // according to the order in which moves are returned by MovePicker. + // move, we store a score, a node count, and a PV (really a refutation + // in the case of moves which fail low). Score is normally set at + // -VALUE_INFINITE for all non-pv moves. struct RootMove { - RootMove(); - RootMove(const RootMove& rm) { *this = rm; } - RootMove& operator=(const RootMove& rm); - // RootMove::operator<() is the comparison function used when // sorting the moves. A move m1 is considered to be better - // than a move m2 if it has an higher pv_score, or if it has - // equal pv_score but m1 has the higher non_pv_score. In this way - // we are guaranteed that PV moves are always sorted as first. - bool operator<(const RootMove& m) const { - return pv_score != m.pv_score ? pv_score < m.pv_score - : non_pv_score < m.non_pv_score; - } + // than a move m2 if it has an higher score + bool operator<(const RootMove& m) const { return score < m.score; } void extract_pv_from_tt(Position& pos); void insert_pv_in_tt(Position& pos); int64_t nodes; - Value pv_score; - Value non_pv_score; - Move pv[PLY_MAX_PLUS_2]; + Value score; + Value prevScore; + std::vector pv; }; // RootMoveList struct is mainly a std::vector of RootMove objects struct RootMoveList : public std::vector { + void init(Position& pos, Move searchMoves[]); - RootMove* find(const Move &m); + RootMove* find(const Move& m, int startIndex = 0); + int bestMoveChanges; }; @@ -167,7 +159,7 @@ namespace { RootMoveList Rml; // MultiPV mode - int MultiPV, UCIMultiPV; + int MultiPV, UCIMultiPV, MultiPVIteration; // Time management variables bool StopOnPonderhit, FirstRootMove, StopRequest, QuitRequest, AspirationFailLow; @@ -205,7 +197,7 @@ namespace { bool connected_moves(const Position& pos, Move m1, Move m2); Value value_to_tt(Value v, int ply); Value value_from_tt(Value v, int ply); - bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply); + bool can_return_tt(const TTEntry* tte, Depth depth, Value beta, int ply); bool connected_threat(const Position& pos, Move m, Move threat); Value refine_eval(const TTEntry* tte, Value defaultEval, int ply); void update_history(const Position& pos, Move move, Depth depth, Move movesSearched[], int moveCount); @@ -213,9 +205,9 @@ namespace { void do_skill_level(Move* best, Move* ponder); int current_search_time(int set = 0); - string score_to_uci(Value v, Value alpha, Value beta); + string score_to_uci(Value v, Value alpha = -VALUE_INFINITE, Value beta = VALUE_INFINITE); string speed_to_uci(int64_t nodes); - string pv_to_uci(Move pv[], int pvNum, bool chess960); + string pv_to_uci(const Move pv[], int pvNum, bool chess960); string pretty_pv(Position& pos, int depth, Value score, int time, Move pv[]); string depth_to_uci(Depth depth); void poll(const Position& pos); @@ -224,28 +216,22 @@ namespace { // MovePickerExt template class extends MovePicker and allows to choose at compile // time the proper moves source according to the type of node. In the default case // we simply create and use a standard MovePicker object. - template struct MovePickerExt : public MovePicker { + template struct MovePickerExt : public MovePicker { MovePickerExt(const Position& p, Move ttm, Depth d, const History& h, SearchStack* ss, Value b) : MovePicker(p, ttm, d, h, ss, b) {} }; // In case of a SpNode we use split point's shared MovePicker object as moves source - template<> struct MovePickerExt : public MovePickerExt { + template<> struct MovePickerExt : public MovePicker { MovePickerExt(const Position& p, Move ttm, Depth d, const History& h, SearchStack* ss, Value b) - : MovePickerExt(p, ttm, d, h, ss, b), mp(ss->sp->mp) {} + : MovePicker(p, ttm, d, h, ss, b), mp(ss->sp->mp) {} Move get_next_move() { return mp->get_next_move(); } MovePicker* mp; }; - template<> struct MovePickerExt : public MovePickerExt { - - MovePickerExt(const Position& p, Move ttm, Depth d, const History& h, SearchStack* ss, Value b) - : MovePickerExt(p, ttm, d, h, ss, b) {} - }; - // Overload operator<<() to make it easier to print moves in a coordinate // notation compatible with UCI protocol. std::ostream& operator<<(std::ostream& os, Move m) { @@ -525,7 +511,7 @@ namespace { H.clear(); *ponderMove = bestMove = easyMove = skillBest = skillPonder = MOVE_NONE; depth = aspirationDelta = 0; - alpha = -VALUE_INFINITE, beta = VALUE_INFINITE; + value = alpha = -VALUE_INFINITE, beta = VALUE_INFINITE; ss->currentMove = MOVE_NULL; // Hack to skip update_gains() // Moves to search are verified and copied @@ -543,71 +529,94 @@ namespace { // Iterative deepening loop until requested to stop or target depth reached while (!StopRequest && ++depth <= PLY_MAX && (!Limits.maxDepth || depth <= Limits.maxDepth)) { + // Save last iteration's scores, this needs to be done now, because in + // the following MultiPV loop Rml moves could be reordered. + for (size_t i = 0; i < Rml.size(); i++) + Rml[i].prevScore = Rml[i].score; + Rml.bestMoveChanges = 0; - // Calculate dynamic aspiration window based on previous iterations - if (MultiPV == 1 && depth >= 5 && abs(bestValues[depth - 1]) < VALUE_KNOWN_WIN) + // MultiPV iteration loop + for (MultiPVIteration = 0; MultiPVIteration < Min(MultiPV, (int)Rml.size()); MultiPVIteration++) { - int prevDelta1 = bestValues[depth - 1] - bestValues[depth - 2]; - int prevDelta2 = bestValues[depth - 2] - bestValues[depth - 3]; - - aspirationDelta = Min(Max(abs(prevDelta1) + abs(prevDelta2) / 2, 16), 24); - aspirationDelta = (aspirationDelta + 7) / 8 * 8; // Round to match grainSize + // Calculate dynamic aspiration window based on previous iterations + if (depth >= 5 && abs(Rml[MultiPVIteration].prevScore) < VALUE_KNOWN_WIN) + { + int prevDelta1 = bestValues[depth - 1] - bestValues[depth - 2]; + int prevDelta2 = bestValues[depth - 2] - bestValues[depth - 3]; - alpha = Max(bestValues[depth - 1] - aspirationDelta, -VALUE_INFINITE); - beta = Min(bestValues[depth - 1] + aspirationDelta, VALUE_INFINITE); - } + aspirationDelta = Min(Max(abs(prevDelta1) + abs(prevDelta2) / 2, 16), 24); + aspirationDelta = (aspirationDelta + 7) / 8 * 8; // Round to match grainSize - // Start with a small aspiration window and, in case of fail high/low, - // research with bigger window until not failing high/low anymore. - do { - // Search starting from ss+1 to allow calling update_gains() - value = search(pos, ss+1, alpha, beta, depth * ONE_PLY); - - // It is critical that sorting is done with a stable algorithm - // because all the values but the first are usually set to - // -VALUE_INFINITE and we want to keep the same order for all - // the moves but the new PV that goes to head. - sort(Rml.begin(), Rml.end()); - - // Write PV back to transposition table in case the relevant entries - // have been overwritten during the search. - for (int i = 0; i < Min(MultiPV, (int)Rml.size()); i++) - Rml[i].insert_pv_in_tt(pos); - - // Value cannot be trusted. Break out immediately! - if (StopRequest) - break; - - // Send full PV info to GUI if we are going to leave the loop or - // if we have a fail high/low and we are deep in the search. - if ((value > alpha && value < beta) || current_search_time() > 2000) - for (int i = 0; i < Min(UCIMultiPV, (int)Rml.size()); i++) - cout << "info" - << depth_to_uci(depth * ONE_PLY) - << score_to_uci(Rml[i].pv_score, alpha, beta) - << speed_to_uci(pos.nodes_searched()) - << pv_to_uci(Rml[i].pv, i + 1, pos.is_chess960()) << endl; - - // In case of failing high/low increase aspiration window and research, - // otherwise exit the fail high/low loop. - if (value >= beta) - { - beta = Min(beta + aspirationDelta, VALUE_INFINITE); - aspirationDelta += aspirationDelta / 2; + alpha = Max(Rml[MultiPVIteration].prevScore - aspirationDelta, -VALUE_INFINITE); + beta = Min(Rml[MultiPVIteration].prevScore + aspirationDelta, VALUE_INFINITE); } - else if (value <= alpha) + else { - AspirationFailLow = true; - StopOnPonderhit = false; - - alpha = Max(alpha - aspirationDelta, -VALUE_INFINITE); - aspirationDelta += aspirationDelta / 2; + alpha = -VALUE_INFINITE; + beta = VALUE_INFINITE; } - else - break; - } while (abs(value) < VALUE_KNOWN_WIN); + // Start with a small aspiration window and, in case of fail high/low, + // research with bigger window until not failing high/low anymore. + do { + // Search starting from ss+1 to allow referencing (ss-1). This is + // needed by update_gains() and ss copy when splitting at Root. + value = search(pos, ss+1, alpha, beta, depth * ONE_PLY); + + // It is critical that sorting is done with a stable algorithm + // because all the values but the first are usually set to + // -VALUE_INFINITE and we want to keep the same order for all + // the moves but the new PV that goes to head. + sort(Rml.begin() + MultiPVIteration, Rml.end()); + + // In case we have found an exact score reorder the PV moves + // before leaving the fail high/low loop, otherwise leave the + // last PV move in its position so to be searched again. + if (value > alpha && value < beta) + sort(Rml.begin(), Rml.begin() + MultiPVIteration); + + // Write PV back to transposition table in case the relevant entries + // have been overwritten during the search. + for (int i = 0; i <= MultiPVIteration; i++) + Rml[i].insert_pv_in_tt(pos); + + // Value cannot be trusted. Break out immediately! + if (StopRequest) + break; + + // Send full PV info to GUI if we are going to leave the loop or + // if we have a fail high/low and we are deep in the search. + if ((value > alpha && value < beta) || current_search_time() > 2000) + for (int i = 0; i < Min(UCIMultiPV, MultiPVIteration + 1); i++) + cout << "info" + << depth_to_uci(depth * ONE_PLY) + << (i == MultiPVIteration ? score_to_uci(Rml[i].score, alpha, beta) : + score_to_uci(Rml[i].score)) + << speed_to_uci(pos.nodes_searched()) + << pv_to_uci(&Rml[i].pv[0], i + 1, pos.is_chess960()) + << endl; + + // In case of failing high/low increase aspiration window and research, + // otherwise exit the fail high/low loop. + if (value >= beta) + { + beta = Min(beta + aspirationDelta, VALUE_INFINITE); + aspirationDelta += aspirationDelta / 2; + } + else if (value <= alpha) + { + AspirationFailLow = true; + StopOnPonderhit = false; + + alpha = Max(alpha - aspirationDelta, -VALUE_INFINITE); + aspirationDelta += aspirationDelta / 2; + } + else + break; + + } while (abs(value) < VALUE_KNOWN_WIN); + } // Collect info about search result bestMove = Rml[0].pv[0]; @@ -620,10 +629,10 @@ namespace { do_skill_level(&skillBest, &skillPonder); if (LogFile.is_open()) - LogFile << pretty_pv(pos, depth, value, current_search_time(), Rml[0].pv) << endl; + LogFile << pretty_pv(pos, depth, value, current_search_time(), &Rml[0].pv[0]) << endl; // Init easyMove after first iteration or drop if differs from the best move - if (depth == 1 && (Rml.size() == 1 || Rml[0].pv_score > Rml[1].pv_score + EasyMoveMargin)) + if (depth == 1 && (Rml.size() == 1 || Rml[0].score > Rml[1].score + EasyMoveMargin)) easyMove = bestMove; else if (bestMove != easyMove) easyMove = MOVE_NONE; @@ -685,9 +694,9 @@ namespace { template Value search(Position& pos, SearchStack* ss, Value alpha, Value beta, Depth depth) { - const bool PvNode = (NT == PV || NT == Root || NT == SplitPointPV); - const bool SpNode = (NT == SplitPointPV || NT == SplitPointNonPV); - const bool RootNode = (NT == Root); + const bool PvNode = (NT == PV || NT == Root || NT == SplitPointPV || NT == SplitPointRoot); + const bool SpNode = (NT == SplitPointPV || NT == SplitPointNonPV || NT == SplitPointRoot); + const bool RootNode = (NT == Root || NT == SplitPointRoot); assert(alpha >= -VALUE_INFINITE && alpha <= VALUE_INFINITE); assert(beta > alpha && beta <= VALUE_INFINITE); @@ -703,7 +712,7 @@ namespace { Depth ext, newDepth; ValueType vt; Value bestValue, value, oldAlpha; - Value refinedValue, nullValue, futilityBase, futilityValueScaled; // Non-PV specific + Value refinedValue, nullValue, futilityBase, futilityValue; bool isPvMove, inCheck, singularExtensionNode, givesCheck, captureOrPromotion, dangerous; int moveCount = 0, playedMoveCount = 0; Thread& thread = Threads[pos.thread()]; @@ -761,14 +770,14 @@ namespace { excludedMove = ss->excludedMove; posKey = excludedMove ? pos.get_exclusion_key() : pos.get_key(); tte = TT.probe(posKey); - ttMove = tte ? tte->move() : MOVE_NONE; + ttMove = RootNode ? Rml[MultiPVIteration].pv[0] : tte ? tte->move() : MOVE_NONE; // At PV nodes we check for exact scores, while at non-PV nodes we check for // a fail high/low. Biggest advantage at probing at PV nodes is to have a // smooth experience in analysis mode. We don't probe at Root nodes otherwise // we should also update RootMoveList to avoid bogus output. if (!RootNode && tte && (PvNode ? tte->depth() >= depth && tte->type() == VALUE_TYPE_EXACT - : ok_to_use_TT(tte, depth, beta, ss->ply))) + : can_return_tt(tte, depth, beta, ss->ply))) { TT.refresh(tte); ss->bestMove = ttMove; // Can be MOVE_NONE @@ -932,7 +941,7 @@ namespace { split_point_start: // At split points actual search starts from here // Initialize a MovePicker object for the current position - MovePickerExt mp(pos, RootNode ? Rml[0].pv[0] : ttMove, depth, H, ss, PvNode ? -VALUE_INFINITE : beta); + MovePickerExt mp(pos, ttMove, depth, H, ss, PvNode ? -VALUE_INFINITE : beta); CheckInfo ci(pos); ss->bestMove = MOVE_NONE; futilityBase = ss->eval + ss->evalMargin; @@ -960,6 +969,12 @@ split_point_start: // At split points actual search starts from here if (move == excludedMove) continue; + // At root obey the "searchmoves" option and skip moves not listed in Root Move List. + // Also in MultiPV mode we skip moves which already have got an exact score + // in previous MultiPV Iteration. Finally any illegal move is skipped here. + if (RootNode && !Rml.find(move, MultiPVIteration)) + continue; + // At PV and SpNode nodes we want all moves to be legal since the beginning if ((PvNode || SpNode) && !pos.pl_move_is_legal(move, ci.pinned)) continue; @@ -982,20 +997,21 @@ split_point_start: // At split points actual search starts from here // If it's time to send nodes info, do it here where we have the // correct accumulated node counts searched by each thread. - if (SendSearchedNodes) + if (!SpNode && SendSearchedNodes) { SendSearchedNodes = false; cout << "info" << speed_to_uci(pos.nodes_searched()) << endl; } // For long searches send current move info to GUI - if (current_search_time() > 2000) + if (pos.thread() == 0 && current_search_time() > 2000) cout << "info" << depth_to_uci(depth) - << " currmove " << move << " currmovenumber " << moveCount << endl; + << " currmove " << move + << " currmovenumber " << moveCount + MultiPVIteration << endl; } // At Root and at first iteration do a PV search on all the moves to score root moves - isPvMove = (PvNode && moveCount <= (!RootNode ? 1 : depth <= ONE_PLY ? MAX_MOVES : MultiPV)); + isPvMove = (PvNode && moveCount <= (RootNode && depth <= ONE_PLY ? MAX_MOVES : 1)); givesCheck = pos.move_gives_check(move, ci); captureOrPromotion = pos.move_is_capture_or_promotion(move); @@ -1054,19 +1070,19 @@ split_point_start: // At split points actual search starts from here // 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); - futilityValueScaled = futilityBase + futility_margin(predictedDepth, moveCount) - + H.gain(pos.piece_on(move_from(move)), move_to(move)); + futilityValue = futilityBase + futility_margin(predictedDepth, moveCount) + + H.gain(pos.piece_on(move_from(move)), move_to(move)); - if (futilityValueScaled < beta) + if (futilityValue < beta) { if (SpNode) { lock_grab(&(sp->lock)); - if (futilityValueScaled > sp->bestValue) - sp->bestValue = bestValue = futilityValueScaled; + if (futilityValue > sp->bestValue) + sp->bestValue = bestValue = futilityValue; } - else if (futilityValueScaled > bestValue) - bestValue = futilityValueScaled; + else if (futilityValue > bestValue) + bestValue = futilityValue; continue; } @@ -1155,74 +1171,65 @@ split_point_start: // At split points actual search starts from here alpha = sp->alpha; } - if (value > bestValue) + // Finished searching the move. If StopRequest 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 (RootNode && !StopRequest) { - bestValue = value; - ss->bestMove = move; - - if ( !RootNode - && PvNode - && value > alpha - && value < beta) // We want always alpha < beta - alpha = value; - - if (SpNode && !thread.cutoff_occurred()) - { - sp->bestValue = value; - sp->ss->bestMove = move; - sp->alpha = alpha; - sp->is_betaCutoff = (value >= beta); - } - } - - if (RootNode) - { - // Finished searching the move. If StopRequest 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 break out of the loop without updating the best - // move and/or PV. - if (StopRequest) - break; - // Remember searched nodes counts for this move - Rml.find(move)->nodes += pos.nodes_searched() - nodes; + RootMove* rm = Rml.find(move); + rm->nodes += pos.nodes_searched() - nodes; // PV move or new best move ? if (isPvMove || value > alpha) { // Update PV - Rml.find(move)->pv_score = value; - Rml.find(move)->extract_pv_from_tt(pos); + rm->score = value; + rm->extract_pv_from_tt(pos); // We record how often the best move has been changed in each // iteration. This information is used for time management: When // the best move changes frequently, we allocate some more time. if (!isPvMove && MultiPV == 1) Rml.bestMoveChanges++; - - // Update alpha. - if (value > alpha) - alpha = value; } else // All other moves but the PV are set to the lowest value, this // is not a problem when sorting becuase sort is stable and move // position in the list is preserved, just the PV is pushed up. - Rml.find(move)->pv_score = -VALUE_INFINITE; + rm->score = -VALUE_INFINITE; } // RootNode + if (value > bestValue) + { + bestValue = value; + ss->bestMove = move; + + if ( PvNode + && value > alpha + && value < beta) // We want always alpha < beta + alpha = value; + + if (SpNode && !thread.cutoff_occurred()) + { + sp->bestValue = value; + sp->ss->bestMove = move; + sp->alpha = alpha; + sp->is_betaCutoff = (value >= beta); + } + } + // Step 19. Check for split - if ( !RootNode - && !SpNode + if ( !SpNode && depth >= Threads.min_split_depth() && bestValue < beta && Threads.available_slave_exists(pos.thread()) && !StopRequest && !thread.cutoff_occurred()) - Threads.split(pos, ss, &alpha, beta, &bestValue, depth, - threatMove, moveCount, &mp, PvNode); + bestValue = Threads.split(pos, ss, alpha, beta, bestValue, depth, + threatMove, moveCount, &mp, NT); } // Step 20. Check for mate and stalemate @@ -1291,6 +1298,7 @@ split_point_start: // At split points actual search starts from here bool inCheck, enoughMaterial, givesCheck, evasionPrunable; const TTEntry* tte; Depth ttDepth; + ValueType vt; Value oldAlpha = alpha; ss->bestMove = ss->currentMove = MOVE_NONE; @@ -1311,7 +1319,7 @@ split_point_start: // At split points actual search starts from here tte = TT.probe(pos.get_key()); ttMove = (tte ? tte->move() : MOVE_NONE); - if (!PvNode && tte && ok_to_use_TT(tte, ttDepth, beta, ss->ply)) + if (!PvNode && tte && can_return_tt(tte, ttDepth, beta, ss->ply)) { ss->bestMove = ttMove; // Can be MOVE_NONE return value_from_tt(tte->value(), ss->ply); @@ -1361,7 +1369,7 @@ split_point_start: // At split points actual search starts from here CheckInfo ci(pos); // Loop through the moves until no moves remain or a beta cutoff occurs - while ( alpha < beta + while ( bestValue < beta && (move = mp.get_next_move()) != MOVE_NONE) { assert(move_is_ok(move)); @@ -1381,10 +1389,11 @@ split_point_start: // At split points actual search starts from here + piece_value_endgame(pos.piece_on(move_to(move))) + (move_is_ep(move) ? PawnValueEndgame : VALUE_ZERO); - if (futilityValue < alpha) + if (futilityValue < beta) { if (futilityValue > bestValue) bestValue = futilityValue; + continue; } @@ -1443,11 +1452,12 @@ split_point_start: // At split points actual search starts from here if (value > bestValue) { bestValue = value; - if (value > alpha) - { + ss->bestMove = move; + + if ( PvNode + && value > alpha + && value < beta) // We want always alpha < beta alpha = value; - ss->bestMove = move; - } } } @@ -1457,8 +1467,11 @@ split_point_start: // At split points actual search starts from here return value_mated_in(ss->ply); // Update transposition table - ValueType vt = (bestValue <= oldAlpha ? VALUE_TYPE_UPPER : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT); - TT.store(pos.get_key(), value_to_tt(bestValue, ss->ply), vt, ttDepth, ss->bestMove, ss->eval, evalMargin); + move = bestValue <= oldAlpha ? MOVE_NONE : ss->bestMove; + vt = bestValue <= oldAlpha ? VALUE_TYPE_UPPER + : bestValue >= beta ? VALUE_TYPE_LOWER : VALUE_TYPE_EXACT; + + TT.store(pos.get_key(), value_to_tt(bestValue, ss->ply), vt, ttDepth, move, ss->eval, evalMargin); assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); @@ -1646,10 +1659,10 @@ split_point_start: // At split points actual search starts from here } - // ok_to_use_TT() returns true if a transposition table score - // can be used at a given point in search. + // can_return_tt() returns true if a transposition table score + // can be used to cut-off at a given point in search. - bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply) { + bool can_return_tt(const TTEntry* tte, Depth depth, Value beta, int ply) { Value v = value_from_tt(tte->value(), ply); @@ -1768,7 +1781,7 @@ split_point_start: // At split points actual search starts from here // pv_to_uci() returns a string with information on the current PV line // formatted according to UCI specification. - string pv_to_uci(Move pv[], int pvNum, bool chess960) { + string pv_to_uci(const Move pv[], int pvNum, bool chess960) { std::stringstream s; @@ -1989,12 +2002,12 @@ split_point_start: // At split points actual search starts from here static RKISS rk; - // Rml list is already sorted by pv_score in descending order + // Rml list is already sorted by score in descending order int s; int max_s = -VALUE_INFINITE; int size = Min(MultiPV, (int)Rml.size()); - int max = Rml[0].pv_score; - int var = Min(max - Rml[size - 1].pv_score, PawnValueMidgame); + int max = Rml[0].score; + int var = Min(max - Rml[size - 1].score, PawnValueMidgame); int wk = 120 - 2 * SkillLevel; // PRNG sequence should be non deterministic @@ -2006,10 +2019,10 @@ split_point_start: // At split points actual search starts from here // then we choose the move with the resulting highest score. for (int i = 0; i < size; i++) { - s = Rml[i].pv_score; + s = Rml[i].score; // Don't allow crazy blunders even at very low skills - if (i > 0 && Rml[i-1].pv_score > s + EasyMoveMargin) + if (i > 0 && Rml[i-1].score > s + EasyMoveMargin) break; // This is our magical formula @@ -2027,27 +2040,6 @@ split_point_start: // At split points actual search starts from here /// RootMove and RootMoveList method's definitions - RootMove::RootMove() { - - nodes = 0; - pv_score = non_pv_score = -VALUE_INFINITE; - pv[0] = MOVE_NONE; - } - - RootMove& RootMove::operator=(const RootMove& rm) { - - const Move* src = rm.pv; - Move* dst = pv; - - // Avoid a costly full rm.pv[] copy - do *dst++ = *src; while (*src++ != MOVE_NONE); - - nodes = rm.nodes; - pv_score = rm.pv_score; - non_pv_score = rm.non_pv_score; - return *this; - } - void RootMoveList::init(Position& pos, Move searchMoves[]) { Move* sm; @@ -2065,22 +2057,21 @@ split_point_start: // At split points actual search starts from here continue; RootMove rm; - rm.pv[0] = ml.move(); - rm.pv[1] = MOVE_NONE; - rm.pv_score = -VALUE_INFINITE; + rm.pv.push_back(ml.move()); + rm.pv.push_back(MOVE_NONE); + rm.score = rm.prevScore = -VALUE_INFINITE; + rm.nodes = 0; push_back(rm); } } - RootMove* RootMoveList::find(const Move &m) { + RootMove* RootMoveList::find(const Move& m, int startIndex) { - for (int i = 0; i < int(size()); i++) - { - if ((*this)[i].pv[0] == m) - return &(*this)[i]; - } + for (size_t i = startIndex; i < size(); i++) + if ((*this)[i].pv[0] == m) + return &(*this)[i]; - return NULL; + return NULL; } // extract_pv_from_tt() builds a PV by adding moves from the transposition table. @@ -2093,10 +2084,13 @@ split_point_start: // At split points actual search starts from here StateInfo state[PLY_MAX_PLUS_2], *st = state; TTEntry* tte; int ply = 1; + Move m = pv[0]; - assert(pv[0] != MOVE_NONE && pos.move_is_pl(pv[0])); + assert(m != MOVE_NONE && pos.move_is_pl(m)); - pos.do_move(pv[0], *st++); + pv.clear(); + pv.push_back(m); + pos.do_move(m, *st++); while ( (tte = TT.probe(pos.get_key())) != NULL && tte->move() != MOVE_NONE @@ -2105,10 +2099,11 @@ split_point_start: // At split points actual search starts from here && ply < PLY_MAX && (!pos.is_draw() || ply < 2)) { - pv[ply] = tte->move(); - pos.do_move(pv[ply++], *st++); + pv.push_back(tte->move()); + pos.do_move(tte->move(), *st++); + ply++; } - pv[ply] = MOVE_NONE; + pv.push_back(MOVE_NONE); do pos.undo_move(pv[--ply]); while (ply); } @@ -2216,10 +2211,14 @@ void ThreadsManager::idle_loop(int threadID, SplitPoint* sp) { memcpy(ss, tsp->ss - 1, 4 * sizeof(SearchStack)); (ss+1)->sp = tsp; - if (tsp->pvNode) + if (tsp->nodeType == Root) + search(pos, ss+1, tsp->alpha, tsp->beta, tsp->depth); + else if (tsp->nodeType == PV) search(pos, ss+1, tsp->alpha, tsp->beta, tsp->depth); - else + else if (tsp->nodeType == NonPV) search(pos, ss+1, tsp->alpha, tsp->beta, tsp->depth); + else + assert(false); assert(threads[threadID].state == Thread::SEARCHING); @@ -2248,8 +2247,6 @@ void ThreadsManager::idle_loop(int threadID, SplitPoint* sp) { // In helpful master concept a master can help only a sub-tree, and // because here is all finished is not possible master is booked. assert(threads[threadID].state == Thread::AVAILABLE); - - threads[threadID].state = Thread::SEARCHING; return; } }