- // root_search() is the function which searches the root node. It is
- // similar to search_pv except that it prints some information to the
- // standard output and handles the fail low/high loops.
-
- Value root_search(Position& pos, SearchStack* ss, Value alpha,
- Value beta, Depth depth, RootMoveList& rml) {
- StateInfo st;
- CheckInfo ci(pos);
- int64_t nodes;
- Move move;
- Depth ext, newDepth;
- Value value, oldAlpha;
- bool isCheck, moveIsCheck, captureOrPromotion, dangerous;
- int researchCountFH, researchCountFL;
-
- researchCountFH = researchCountFL = 0;
- oldAlpha = alpha;
- isCheck = pos.is_check();
-
- // Step 1. Initialize node (polling is omitted at root)
- ss->currentMove = ss->bestMove = MOVE_NONE;
-
- // Step 2. Check for aborted search (omitted at root)
- // Step 3. Mate distance pruning (omitted at root)
- // Step 4. Transposition table lookup (omitted at root)
-
- // Step 5. Evaluate the position statically
- // At root we do this only to get reference value for child nodes
- ss->evalMargin = VALUE_NONE;
- ss->eval = isCheck ? VALUE_NONE : evaluate(pos, ss->evalMargin);
-
- // Step 6. Razoring (omitted at root)
- // Step 7. Static null move pruning (omitted at root)
- // Step 8. Null move search with verification search (omitted at root)
- // Step 9. Internal iterative deepening (omitted at root)
-
- // Step extra. Fail low loop
- // We start with small aspiration window and in case of fail low, we research
- // with bigger window until we are not failing low anymore.
- while (1)
- {
- // Sort the moves before to (re)search
- rml.set_non_pv_scores(pos);
- rml.sort();
-
- // Step 10. Loop through all moves in the root move list
- for (int i = 0; i < (int)rml.size() && !AbortSearch; i++)
- {
- // This is used by time management
- FirstRootMove = (i == 0);
-
- // Save the current node count before the move is searched
- nodes = pos.nodes_searched();
-
- // Pick the next root move, and print the move and the move number to
- // the standard output.
- move = ss->currentMove = rml[i].pv[0];
-
- if (current_search_time() >= 1000)
- cout << "info currmove " << move
- << " currmovenumber " << i + 1 << endl;
-
- moveIsCheck = pos.move_is_check(move);
- captureOrPromotion = pos.move_is_capture_or_promotion(move);
-
- // Step 11. Decide the new search depth
- ext = extension<PV>(pos, move, captureOrPromotion, moveIsCheck, false, false, &dangerous);
- newDepth = depth + ext;
-
- // Step 12. Futility pruning (omitted at root)
-
- // Step extra. Fail high loop
- // If move fails high, we research with bigger window until we are not failing
- // high anymore.
- value = -VALUE_INFINITE;
-
- while (1)
- {
- // Step 13. Make the move
- pos.do_move(move, st, ci, moveIsCheck);
+ // 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<Root>(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<RootMove>(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<RootMove>(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;