X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=6fd99763e46a0a007a82ba4c86b07f7cdd1462a0;hp=7f64cd9410ae3436ee55eba00e90216c92011e66;hb=0980f43ab06611c6eb0fb4c112551e9c40254a23;hpb=89b4ad6433fbe04acbd8e9f6f45ddf33ec2d7fd7 diff --git a/src/search.cpp b/src/search.cpp index 7f64cd94..6fd99763 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -1052,37 +1052,50 @@ namespace { if (depth < OnePly) return qsearch(pos, ss, alpha, beta, Depth(0), ply, threadID); - // Initialize, and make an early exit in case of an aborted search, - // an instant draw, maximum ply reached, etc. + // Step 1. Initialize node and poll + // Polling can abort search. init_node(ss, ply, threadID); - // After init_node() that calls poll() + // Step 2. Check for aborted search and immediate draw if (AbortSearch || TM.thread_should_stop(threadID)) return Value(0); if (pos.is_draw() || ply >= PLY_MAX - 1) return VALUE_DRAW; - // Mate distance pruning + // Step 3. Mate distance pruning oldAlpha = alpha; alpha = Max(value_mated_in(ply), alpha); beta = Min(value_mate_in(ply+1), beta); if (alpha >= beta) return alpha; - // Transposition table lookup. At PV nodes, we don't use the TT for - // pruning, but only for move ordering. This is to avoid problems in - // the following areas: + // Step 4. Transposition table lookup + // At PV nodes, we don't use the TT for pruning, but only for move ordering. + // This is to avoid problems in the following areas: // // * Repetition draw detection // * Fifty move rule detection // * Searching for a mate // * Printing of full PV line - // tte = TT.retrieve(pos.get_key()); ttMove = (tte ? tte->move() : MOVE_NONE); - // Go with internal iterative deepening if we don't have a TT move + // Step 5. Evaluate the position statically + // At PV nodes we do this only to update gain statistics + isCheck = pos.is_check(); + if (!isCheck) + { + EvalInfo ei; + ss[ply].eval = evaluate(pos, ei, threadID); + update_gains(pos, ss[ply - 1].currentMove, ss[ply - 1].eval, ss[ply].eval); + } + + // Step 6. Razoring (is omitted in PV nodes) + // Step 7. Static null move pruning (is omitted in PV nodes) + // Step 8. Null move search with verification search (is omitted in PV nodes) + + // Step 9. Internal iterative deepening if ( UseIIDAtPVNodes && depth >= 5*OnePly && ttMove == MOVE_NONE) @@ -1092,24 +1105,14 @@ namespace { tte = TT.retrieve(pos.get_key()); } - isCheck = pos.is_check(); - if (!isCheck) - { - // Update gain statistics of the previous move that lead - // us in this position. - EvalInfo ei; - ss[ply].eval = evaluate(pos, ei, threadID); - update_gains(pos, ss[ply - 1].currentMove, ss[ply - 1].eval, ss[ply].eval); - } + // Step 10. Loop through moves + // Loop through all legal moves until no moves remain or a beta cutoff occurs - // Initialize a MovePicker object for the current position, and prepare - // to search all moves + // Initialize a MovePicker object for the current position mateThreat = pos.has_mate_threat(opposite_color(pos.side_to_move())); - CheckInfo ci(pos); MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]); + CheckInfo ci(pos); - // Loop through all legal moves until no moves remain or a beta cutoff - // occurs. while ( alpha < beta && (move = mp.get_next_move()) != MOVE_NONE && !TM.thread_should_stop(threadID)) @@ -1331,16 +1334,19 @@ namespace { return v; //FIXME: Logically should be: return (v + 0x200 + 16 * depth); } - // Static null move pruning. We're betting that the opponent doesn't have - // a move that will reduce the score by more than FutilityMargins[int(depth)] - // if we do a null move. + // Step 7. Static null move pruning + // We're betting that the opponent doesn't have a move that will reduce + // the score by more than fuility_margin(depth) if we do a null move. if ( !isCheck && allowNullmove && depth < RazorDepth && staticValue - futility_margin(depth, 0) >= beta) return staticValue - futility_margin(depth, 0); - // Null move search + // Step 8. Null move search with verification search + // When we jump directly to qsearch() we do a null move only if static value is + // at least beta. Otherwise we do a null move if static value is not more than + // NullMoveMargin under beta. if ( allowNullmove && depth > OnePly && !isCheck @@ -1390,21 +1396,22 @@ namespace { } } - // Go with internal iterative deepening if we don't have a TT move + // Step 9. Internal iterative deepening if (UseIIDAtNonPVNodes && ttMove == MOVE_NONE && depth >= 8*OnePly && !isCheck && ss[ply].eval >= beta - IIDMargin) { - search(pos, ss, beta, Min(depth/2, depth-2*OnePly), ply, false, threadID); + search(pos, ss, beta, depth/2, ply, false, threadID); ttMove = ss[ply].pv[ply]; tte = TT.retrieve(posKey); } - // Initialize a MovePicker object for the current position, and prepare - // to search all moves. + // Step 10. Loop through moves + // Loop through all legal moves until no moves remain or a beta cutoff occurs + + // Initialize a MovePicker object for the current position MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]); CheckInfo ci(pos); - // Loop through all legal moves until no moves remain or a beta cutoff occurs while ( bestValue < beta && (move = mp.get_next_move()) != MOVE_NONE && !TM.thread_should_stop(threadID)) @@ -1418,7 +1425,7 @@ namespace { singleEvasion = (isCheck && mp.number_of_evasions() == 1); captureOrPromotion = pos.move_is_capture_or_promotion(move); - // Decide the new search depth + // Step 11. Decide the new search depth ext = extension(pos, move, false, captureOrPromotion, moveIsCheck, singleEvasion, mateThreat, &dangerous); // Singular extension search. We extend the TT move if its value is much better than @@ -1445,10 +1452,10 @@ namespace { newDepth = depth - OnePly + ext; - // Update current move + // Update current move (this must be done after singular extension search) movesSearched[moveCount++] = ss[ply].currentMove = move; - // Futility pruning + // Step 12. Futility pruning if ( !isCheck && !dangerous && !captureOrPromotion @@ -1474,10 +1481,10 @@ namespace { } } - // Make and search the move + // Step 13. Make the move pos.do_move(move, st, ci, moveIsCheck); - // Try to reduce non-pv search depth by one ply if move seems not problematic, + // Step 14. Reduced search // if the move fails high will be re-searched at full depth. bool doFullDepthSearch = true; @@ -1495,16 +1502,19 @@ namespace { } } - if (doFullDepthSearch) // Go with full depth non-pv search + // Step 15. Full depth search + if (doFullDepthSearch) { ss[ply].reduction = Depth(0); value = -search(pos, ss, -(beta-1), newDepth, ply+1, true, threadID); } + + // Step 16. Undo move pos.undo_move(move); assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); - // New best move? + // Step 17. Check for new best move if (value > bestValue) { bestValue = value; @@ -1515,7 +1525,7 @@ namespace { ss[ply].mateKiller = move; } - // Split? + // Step 18. Check for split if ( TM.active_threads() > 1 && bestValue < beta && depth >= MinimumSplitDepth @@ -1528,11 +1538,14 @@ namespace { break; } - // All legal moves have been searched. A special case: If there were + // Step 19. Check for mate and stalemate + // All legal moves have been searched and if there were // no legal moves, it must be mate or stalemate. + // If one move was excluded return fail low. if (!moveCount) return excludedMove ? beta - 1 : (pos.is_check() ? value_mated_in(ply) : VALUE_DRAW); + // Step 20. Update tables // If the search is not aborted, update the transposition table, // history counters, and killer moves. if (AbortSearch || TM.thread_should_stop(threadID))