- // 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);
-
- // Step extra. pv search
- // We do pv search for first moves (i < MultiPV)
- // and for fail high research (value > alpha)
- if (i < MultiPV || value > alpha)
- {
- // Aspiration window is disabled in multi-pv case
- if (MultiPV > 1)
- alpha = -VALUE_INFINITE;
-
- // Full depth PV search, done on first move or after a fail high
- value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, 1);
- }
- else
- {
- // Step 14. Reduced search
- // if the move fails high will be re-searched at full depth
- bool doFullDepthSearch = true;
-
- if ( depth >= 3 * ONE_PLY
- && !dangerous
- && !captureOrPromotion
- && !move_is_castle(move))
- {
- ss->reduction = reduction<PV>(depth, i - MultiPV + 2);
- if (ss->reduction)
- {
- assert(newDepth-ss->reduction >= ONE_PLY);
-
- // Reduced depth non-pv search using alpha as upperbound
- value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth-ss->reduction, 1);
- doFullDepthSearch = (value > alpha);
- }
- ss->reduction = DEPTH_ZERO; // Restore original reduction
- }
-
- // Step 15. Full depth search
- if (doFullDepthSearch)
- {
- // Full depth non-pv search using alpha as upperbound
- value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth, 1);
-
- // If we are above alpha then research at same depth but as PV
- // to get a correct score or eventually a fail high above beta.
- if (value > alpha)
- value = -search<PV>(pos, ss+1, -beta, -alpha, newDepth, 1);
- }
- }
-
- // Step 16. Undo move
- pos.undo_move(move);
-
- // Can we exit fail high loop ?
- if (AbortSearch || value < beta)
- break;
-
- // We are failing high and going to do a research. It's important to update
- // the score before research in case we run out of time while researching.
- ss->bestMove = move;
- rml[i].pv_score = value;
- rml[i].extract_pv_from_tt(pos);
-
- // Inform GUI that PV has changed
- cout << rml[i].pv_info_to_uci(pos, alpha, beta) << endl;
-
- // Prepare for a research after a fail high, each time with a wider window
- beta = Min(beta + AspirationDelta * (1 << researchCountFH), VALUE_INFINITE);
- researchCountFH++;
-
- } // End of fail high loop
-
- // Finished searching the move. If AbortSearch 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 (AbortSearch)
- break;
-
- // Remember searched nodes counts for this move
- rml[i].nodes += pos.nodes_searched() - nodes;
-
- assert(value >= -VALUE_INFINITE && value <= VALUE_INFINITE);
- assert(value < beta);
-
- // Step 17. Check for new best move
- if (value <= alpha && i >= MultiPV)
- rml[i].pv_score = -VALUE_INFINITE;
- else
- {
- // PV move or new best move!
-
- // Update PV
- ss->bestMove = move;
- rml[i].pv_score = value;
- rml[i].extract_pv_from_tt(pos);
-
- // We record how often the best move has been changed in each
- // iteration. This information is used for time managment: When
- // the best move changes frequently, we allocate some more time.
- if (MultiPV == 1 && i > 0)
- BestMoveChangesByIteration[Iteration]++;
-
- // Inform GUI that PV has changed, in case of multi-pv UCI protocol
- // requires we send all the PV lines properly sorted.
- rml.sort_multipv(i);
-
- for (int j = 0; j < Min(MultiPV, (int)rml.size()); j++)
- cout << rml[j].pv_info_to_uci(pos, alpha, beta, j) << endl;
-
- // Update alpha. In multi-pv we don't use aspiration window
- if (MultiPV == 1)
- {
- // Raise alpha to setup proper non-pv search upper bound
- if (value > alpha)
- alpha = value;
- }
- else // Set alpha equal to minimum score among the PV lines
- alpha = rml[Min(i, MultiPV - 1)].pv_score;
-
- } // PV move or new best move
-
- assert(alpha >= oldAlpha);
-
- AspirationFailLow = (alpha == oldAlpha);
-
- if (AspirationFailLow && StopOnPonderhit)
- StopOnPonderhit = false;
-
- } // Root moves loop
-
- // Can we exit fail low loop ?
- if (AbortSearch || !AspirationFailLow)
- break;
-
- // Prepare for a research after a fail low, each time with a wider window
- oldAlpha = alpha = Max(alpha - AspirationDelta * (1 << researchCountFL), -VALUE_INFINITE);
- researchCountFL++;
-
- } // Fail low loop
-
- // Sort the moves before to return
- rml.sort();
-
- // Write PV lines to transposition table, in case the relevant entries
- // have been overwritten during the search.
- for (int i = 0; i < MultiPV; i++)
- rml[i].insert_pv_in_tt(pos);
-
- return alpha;
- }
-
-