X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=f7ddfa0481f2f32697400015c408b91bdf75abc0;hp=d073b7da31a2e14056bee54e2c4d45dbfd8b0ba7;hb=30075e4abcf0430cef78ae0b7823390013e75618;hpb=b50921fd5c3e1753adecfea77557ad1afece7641 diff --git a/src/search.cpp b/src/search.cpp index d073b7da..f7ddfa04 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -326,6 +326,37 @@ namespace { //// Functions //// + +/// perft() is our utility to verify move generation is bug free. All the +/// legal moves up to given depth are generated and counted and the sum returned. + +int perft(Position& pos, Depth depth) +{ + Move move; + MovePicker mp = MovePicker(pos, MOVE_NONE, depth, H); + Bitboard dcCandidates = pos.discovered_check_candidates(pos.side_to_move()); + int sum = 0; + + // If we are at the last ply we don't need to do and undo + // the moves, just to count them. + if (depth <= OnePly) // Replace with '<' to test also qsearch + { + while ((move = mp.get_next_move()) != MOVE_NONE) sum++; + return sum; + } + + // Loop through all legal moves + while ((move = mp.get_next_move()) != MOVE_NONE) + { + StateInfo st; + pos.do_move(move, st, dcCandidates); + sum += perft(pos, depth - OnePly); + pos.undo_move(move); + } + return sum; +} + + /// think() is the external interface to Stockfish's search, and is called when /// the program receives the UCI 'go' command. It initializes various /// search-related global variables, and calls root_search(). It returns false @@ -447,7 +478,7 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move, if (movesToGo == 1) { MaxSearchTime = myTime / 2; - AbsoluteMaxSearchTime = + AbsoluteMaxSearchTime = (myTime > 3000)? (myTime - 500) : ((myTime * 3) / 4); } else { MaxSearchTime = myTime / Min(movesToGo, 20); @@ -976,7 +1007,7 @@ namespace { std::cout << std::endl; if (UseLogFile) - LogFile << pretty_pv(pos, current_search_time(), Iteration, nodes_searched(), value, + LogFile << pretty_pv(pos, current_search_time(), Iteration, nodes_searched(), value, ((value >= beta)? VALUE_TYPE_LOWER : ((value <= alpha)? VALUE_TYPE_UPPER : VALUE_TYPE_EXACT)), ss[0].pv) @@ -1031,6 +1062,18 @@ namespace { assert(ply >= 0 && ply < PLY_MAX); assert(threadID >= 0 && threadID < ActiveThreads); + Move movesSearched[256]; + EvalInfo ei; + StateInfo st; + Bitboard dcCandidates; + const TTEntry* tte; + Move ttMove, move; + Depth ext, newDepth; + Value oldAlpha, value; + bool isCheck, mateThreat, singleReply, moveIsCheck, captureOrPromotion, dangerous; + int moveCount = 0; + Value bestValue = -VALUE_INFINITE; + if (depth < OnePly) return qsearch(pos, ss, alpha, beta, Depth(0), ply, threadID); @@ -1045,13 +1088,11 @@ namespace { if (pos.is_draw()) return VALUE_DRAW; - EvalInfo ei; - if (ply >= PLY_MAX - 1) return pos.is_check() ? quick_evaluate(pos) : evaluate(pos, ei, threadID); // Mate distance pruning - Value oldAlpha = alpha; + oldAlpha = alpha; alpha = Max(value_mated_in(ply), alpha); beta = Min(value_mate_in(ply+1), beta); if (alpha >= beta) @@ -1059,8 +1100,8 @@ namespace { // Transposition table lookup. At PV nodes, we don't use the TT for // pruning, but only for move ordering. - const TTEntry* tte = TT.retrieve(pos.get_key()); - Move ttMove = (tte ? tte->move() : MOVE_NONE); + 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 if (UseIIDAtPVNodes && ttMove == MOVE_NONE && depth >= 5*OnePly) @@ -1071,15 +1112,11 @@ namespace { // Initialize a MovePicker object for the current position, and prepare // to search all moves - Move move, movesSearched[256]; - int moveCount = 0; - Value value, bestValue = -VALUE_INFINITE; - Color us = pos.side_to_move(); - bool isCheck = pos.is_check(); - bool mateThreat = pos.has_mate_threat(opposite_color(us)); - + isCheck = pos.is_check(); + mateThreat = pos.has_mate_threat(opposite_color(pos.side_to_move())); + CheckInfo ci(pos); + dcCandidates = ci.dc; MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]); - Bitboard dcCandidates = mp.discovered_check_candidates(); // Loop through all legal moves until no moves remain or a beta cutoff // occurs. @@ -1089,19 +1126,17 @@ namespace { { assert(move_is_ok(move)); - bool singleReply = (isCheck && mp.number_of_evasions() == 1); - bool moveIsCheck = pos.move_is_check(move, dcCandidates); - bool captureOrPromotion = pos.move_is_capture_or_promotion(move); + singleReply = (isCheck && mp.number_of_evasions() == 1); + moveIsCheck = pos.move_is_check(move, dcCandidates); + captureOrPromotion = pos.move_is_capture_or_promotion(move); movesSearched[moveCount++] = ss[ply].currentMove = move; // Decide the new search depth - bool dangerous; - Depth ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, singleReply, mateThreat, &dangerous); - Depth newDepth = depth - OnePly + ext; + ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, singleReply, mateThreat, &dangerous); + newDepth = depth - OnePly + ext; // Make and search the move - StateInfo st; pos.do_move(move, st, dcCandidates); if (moveCount == 1) // The first move in list is the PV @@ -1196,13 +1231,13 @@ namespace { else if (bestValue >= beta) { BetaCounter.add(pos.side_to_move(), depth, threadID); - Move m = ss[ply].pv[ply]; - if (!pos.move_is_capture_or_promotion(m)) + move = ss[ply].pv[ply]; + if (!pos.move_is_capture_or_promotion(move)) { - update_history(pos, m, depth, movesSearched, moveCount); - update_killers(m, ss[ply]); + update_history(pos, move, depth, movesSearched, moveCount); + update_killers(move, ss[ply]); } - TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, m); + TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, move); } else TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EXACT, depth, ss[ply].pv[ply]); @@ -1220,6 +1255,19 @@ namespace { assert(ply >= 0 && ply < PLY_MAX); assert(threadID >= 0 && threadID < ActiveThreads); + Move movesSearched[256]; + EvalInfo ei; + StateInfo st; + Bitboard dcCandidates; + const TTEntry* tte; + Move ttMove, move; + Depth ext, newDepth; + Value approximateEval, nullValue, value, futilityValue; + bool isCheck, useFutilityPruning, singleReply, moveIsCheck, captureOrPromotion, dangerous; + bool mateThreat = false; + int moveCount = 0; + Value bestValue = -VALUE_INFINITE; + if (depth < OnePly) return qsearch(pos, ss, beta-1, beta, Depth(0), ply, threadID); @@ -1234,8 +1282,6 @@ namespace { if (pos.is_draw()) return VALUE_DRAW; - EvalInfo ei; - if (ply >= PLY_MAX - 1) return pos.is_check() ? quick_evaluate(pos) : evaluate(pos, ei, threadID); @@ -1247,8 +1293,8 @@ namespace { return beta - 1; // Transposition table lookup - const TTEntry* tte = TT.retrieve(pos.get_key()); - Move ttMove = (tte ? tte->move() : MOVE_NONE); + tte = TT.retrieve(pos.get_key()); + ttMove = (tte ? tte->move() : MOVE_NONE); if (tte && ok_to_use_TT(tte, depth, beta, ply)) { @@ -1256,9 +1302,8 @@ namespace { return value_from_tt(tte->value(), ply); } - Value approximateEval = quick_evaluate(pos); - bool mateThreat = false; - bool isCheck = pos.is_check(); + approximateEval = quick_evaluate(pos); + isCheck = pos.is_check(); // Null move search if ( allowNullmove @@ -1270,11 +1315,10 @@ namespace { { ss[ply].currentMove = MOVE_NULL; - StateInfo st; pos.do_null_move(st); int R = (depth >= 5 * OnePly ? 4 : 3); // Null move dynamic reduction - Value nullValue = -search(pos, ss, -(beta-1), depth-R*OnePly, ply+1, false, threadID); + nullValue = -search(pos, ss, -(beta-1), depth-R*OnePly, ply+1, false, threadID); pos.undo_null_move(); @@ -1328,14 +1372,10 @@ namespace { // Initialize a MovePicker object for the current position, and prepare // to search all moves. MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]); - - Move move, movesSearched[256]; - int moveCount = 0; - Value value, bestValue = -VALUE_INFINITE; - Bitboard dcCandidates = mp.discovered_check_candidates(); - Value futilityValue = VALUE_NONE; - bool useFutilityPruning = depth < SelectiveDepth - && !isCheck; + CheckInfo ci(pos); + dcCandidates = ci.dc; + futilityValue = VALUE_NONE; + useFutilityPruning = depth < SelectiveDepth && !isCheck; // Avoid calling evaluate() if we already have the score in TT if (tte && (tte->type() & VALUE_TYPE_EVAL)) @@ -1349,16 +1389,15 @@ namespace { { assert(move_is_ok(move)); - bool singleReply = (isCheck && mp.number_of_evasions() == 1); - bool moveIsCheck = pos.move_is_check(move, dcCandidates); - bool captureOrPromotion = pos.move_is_capture_or_promotion(move); + singleReply = (isCheck && mp.number_of_evasions() == 1); + moveIsCheck = pos.move_is_check(move, dcCandidates); + captureOrPromotion = pos.move_is_capture_or_promotion(move); movesSearched[moveCount++] = ss[ply].currentMove = move; // Decide the new search depth - bool dangerous; - Depth ext = extension(pos, move, false, captureOrPromotion, moveIsCheck, singleReply, mateThreat, &dangerous); - Depth newDepth = depth - OnePly + ext; + ext = extension(pos, move, false, captureOrPromotion, moveIsCheck, singleReply, mateThreat, &dangerous); + newDepth = depth - OnePly + ext; // Futility pruning if ( useFutilityPruning @@ -1388,7 +1427,6 @@ namespace { } // Make and search the move - StateInfo st; pos.do_move(move, st, dcCandidates); // Try to reduce non-pv search depth by one ply if move seems not problematic, @@ -1454,13 +1492,13 @@ namespace { else { BetaCounter.add(pos.side_to_move(), depth, threadID); - Move m = ss[ply].pv[ply]; - if (!pos.move_is_capture_or_promotion(m)) + move = ss[ply].pv[ply]; + if (!pos.move_is_capture_or_promotion(move)) { - update_history(pos, m, depth, movesSearched, moveCount); - update_killers(m, ss[ply]); + update_history(pos, move, depth, movesSearched, moveCount); + update_killers(move, ss[ply]); } - TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, m); + TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, move); } assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); @@ -1482,6 +1520,16 @@ namespace { assert(ply >= 0 && ply < PLY_MAX); assert(threadID >= 0 && threadID < ActiveThreads); + EvalInfo ei; + StateInfo st; + Bitboard dcCandidates; + Move ttMove, move; + Value staticValue, bestValue, value, futilityValue; + bool isCheck, enoughMaterial; + const TTEntry* tte = NULL; + int moveCount = 0; + bool pvNode = (beta - alpha != 1); + // Initialize, and make an early exit in case of an aborted search, // an instant draw, maximum ply reached, etc. init_node(ss, ply, threadID); @@ -1494,8 +1542,6 @@ namespace { return VALUE_DRAW; // Transposition table lookup, only when not in PV - TTEntry* tte = NULL; - bool pvNode = (beta - alpha != 1); if (!pvNode) { tte = TT.retrieve(pos.get_key()); @@ -1506,12 +1552,10 @@ namespace { return value_from_tt(tte->value(), ply); } } - Move ttMove = (tte ? tte->move() : MOVE_NONE); + ttMove = (tte ? tte->move() : MOVE_NONE); // Evaluate the position statically - EvalInfo ei; - Value staticValue; - bool isCheck = pos.is_check(); + isCheck = pos.is_check(); ei.futilityMargin = Value(0); // Manually initialize futilityMargin if (isCheck) @@ -1532,7 +1576,7 @@ namespace { // Initialize "stand pat score", and return it immediately if it is // at least beta. - Value bestValue = staticValue; + bestValue = staticValue; if (bestValue >= beta) { @@ -1550,11 +1594,9 @@ namespace { // to search the moves. Because the depth is <= 0 here, only captures, // queen promotions and checks (only if depth == 0) will be generated. MovePicker mp = MovePicker(pos, ttMove, depth, H); - Move move; - int moveCount = 0; - Bitboard dcCandidates = mp.discovered_check_candidates(); - Color us = pos.side_to_move(); - bool enoughMaterial = pos.non_pawn_material(us) > RookValueMidgame; + CheckInfo ci(pos); + dcCandidates = ci.dc; + enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMidgame; // Loop through the moves until no moves remain or a beta cutoff // occurs. @@ -1574,12 +1616,12 @@ namespace { && !pos.move_is_check(move, dcCandidates) && !pos.move_is_passed_pawn_push(move)) { - Value futilityValue = staticValue - + Max(pos.midgame_value_of_piece_on(move_to(move)), - pos.endgame_value_of_piece_on(move_to(move))) - + (move_is_ep(move) ? PawnValueEndgame : Value(0)) - + FutilityMarginQS - + ei.futilityMargin; + futilityValue = staticValue + + Max(pos.midgame_value_of_piece_on(move_to(move)), + pos.endgame_value_of_piece_on(move_to(move))) + + (move_is_ep(move) ? PawnValueEndgame : Value(0)) + + FutilityMarginQS + + ei.futilityMargin; if (futilityValue < alpha) { @@ -1596,10 +1638,9 @@ namespace { && pos.see_sign(move) < 0) continue; - // Make and search the move. - StateInfo st; + // Make and search the move pos.do_move(move, st, dcCandidates); - Value value = -qsearch(pos, ss, -beta, -alpha, depth-OnePly, ply+1, threadID); + value = -qsearch(pos, ss, -beta, -alpha, depth-OnePly, ply+1, threadID); pos.undo_move(move); assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); @@ -1624,7 +1665,7 @@ namespace { assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); // Update transposition table - Move m = ss[ply].pv[ply]; + move = ss[ply].pv[ply]; if (!pvNode) { // If bestValue isn't changed it means it is still the static evaluation of @@ -1635,12 +1676,12 @@ namespace { if (bestValue < beta) TT.store(pos.get_key(), value_to_tt(bestValue, ply), type, d, MOVE_NONE); else - TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, d, m); + TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, d, move); } // Update killers only for good check moves - if (alpha >= beta && !pos.move_is_capture_or_promotion(m)) - update_killers(m, ss[ply]); + if (alpha >= beta && !pos.move_is_capture_or_promotion(move)) + update_killers(move, ss[ply]); return bestValue; }