X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=c018cbe3c49b7283d3d64de2f5ce235c79b74864;hp=6208da61b8bb0bec7f30fbaa835a02e518aee8b9;hb=7f519a246327e164056bbd3e77ed5a672618094d;hpb=1c42d153402be9eeed46986a392affee03e1de53 diff --git a/src/search.cpp b/src/search.cpp index 6208da61..c018cbe3 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -79,16 +79,9 @@ namespace { Move pv[PLY_MAX_PLUS_2]; }; - // RootMoveList struct is just a vector of RootMove objects, - // with an handful of methods above the standard ones. + // RootMoveList struct is mainly a std::vector of RootMove objects struct RootMoveList : public std::vector { - - typedef std::vector Base; - void init(Position& pos, Move searchMoves[]); - void sort() { insertion_sort(begin(), end()); } - void sort_first(int n) { insertion_sort(begin(), begin() + n); } - int bestMoveChanges; }; @@ -219,7 +212,7 @@ namespace { int current_search_time(int set = 0); std::string score_to_uci(Value v, Value alpha, Value beta); std::string speed_to_uci(int64_t nodes); - std::string pv_to_uci(Move pv[], int pvNum); + std::string pv_to_uci(Move pv[], int pvNum, bool chess960); std::string depth_to_uci(Depth depth); void poll(const Position& pos); void wait_for_stop_or_ponderhit(); @@ -300,7 +293,7 @@ namespace { if (moveIsCheck && pos.see_sign(m) >= 0) result += CheckExtension[PvNode]; - if (pos.type_of_piece_on(move_from(m)) == PAWN) + if (piece_type(pos.piece_on(move_from(m))) == PAWN) { Color c = pos.side_to_move(); if (relative_rank(c, move_to(m)) == RANK_7) @@ -316,9 +309,9 @@ namespace { } if ( captureOrPromotion - && pos.type_of_piece_on(move_to(m)) != PAWN + && piece_type(pos.piece_on(move_to(m))) != PAWN && ( pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK) - - pos.midgame_value_of_piece_on(move_to(m)) == VALUE_ZERO) + - piece_value_midgame(pos.piece_on(move_to(m))) == VALUE_ZERO) && !move_is_special(m)) { result += PawnEndgameExtension[PvNode]; @@ -363,27 +356,24 @@ void init_search() { int64_t perft(Position& pos, Depth depth) { - MoveStack mlist[MAX_MOVES]; StateInfo st; - Move m; int64_t sum = 0; // Generate all legal moves - MoveStack* last = generate(pos, mlist); + MoveList ml(pos); // If we are at the last ply we don't need to do and undo // the moves, just to count them. if (depth <= ONE_PLY) - return int(last - mlist); + return ml.size(); // Loop through all legal moves CheckInfo ci(pos); - for (MoveStack* cur = mlist; cur != last; cur++) + for ( ; !ml.end(); ++ml) { - m = cur->move; - pos.do_move(m, st, ci, pos.move_gives_check(m, ci)); + pos.do_move(ml.move(), st, ci, pos.move_gives_check(ml.move(), ci)); sum += perft(pos, depth - ONE_PLY); - pos.undo_move(m); + pos.undo_move(ml.move()); } return sum; } @@ -599,7 +589,7 @@ namespace { << 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) << endl; + << 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. @@ -643,12 +633,6 @@ namespace { // Check for some early stop condition if (!StopRequest && Limits.useTimeManagement()) { - // Stop search early when the last two iterations returned a mate score - if ( depth >= 5 - && abs(bestValues[depth]) >= VALUE_MATE_IN_PLY_MAX - && abs(bestValues[depth - 1]) >= VALUE_MATE_IN_PLY_MAX) - StopRequest = true; - // Stop search early if one move seems to be much better than the // others or if there is only a single legal move. Also in the latter // case we search up to some depth anyway to get a proper score. @@ -736,7 +720,14 @@ namespace { if (PvNode && thread.maxPly < ss->ply) thread.maxPly = ss->ply; - if (SpNode) + // Step 1. Initialize node and poll. Polling can abort search + if (!SpNode) + { + ss->currentMove = ss->bestMove = threatMove = (ss+1)->excludedMove = MOVE_NONE; + (ss+1)->skipNullMove = false; (ss+1)->reduction = DEPTH_ZERO; + (ss+2)->killers[0] = (ss+2)->killers[1] = MOVE_NONE; + } + else { sp = ss->sp; tte = NULL; @@ -745,11 +736,6 @@ namespace { goto split_point_start; } - // Step 1. Initialize node and poll. Polling can abort search - ss->currentMove = ss->bestMove = threatMove = (ss+1)->excludedMove = MOVE_NONE; - (ss+1)->skipNullMove = false; (ss+1)->reduction = DEPTH_ZERO; - (ss+2)->killers[0] = (ss+2)->killers[1] = MOVE_NONE; - if (pos.thread() == 0 && ++NodesSincePoll > NodesBetweenPolls) { NodesSincePoll = 0; @@ -776,7 +762,6 @@ namespace { // TT value, so we use a different position key in case of an excluded move. excludedMove = ss->excludedMove; posKey = excludedMove ? pos.get_exclusion_key() : pos.get_key(); - tte = TT.probe(posKey); ttMove = tte ? tte->move() : MOVE_NONE; @@ -916,7 +901,7 @@ namespace { assert(rdepth >= ONE_PLY); - MovePicker mp(pos, ttMove, H, Position::see_value(pos.captured_piece_type())); + MovePicker mp(pos, ttMove, H, pos.captured_piece_type()); CheckInfo ci(pos); while ((move = mp.get_next_move()) != MOVE_NONE) @@ -976,7 +961,7 @@ split_point_start: // At split points actual search starts from here if (move == excludedMove) continue; - // At PV and SpNode nodes we want the moves to be legal + // 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; @@ -1004,16 +989,16 @@ split_point_start: // At split points actual search starts from here cout << "info" << speed_to_uci(pos.nodes_searched()) << endl; } - // For long searches send to GUI current move + // For long searches send current move info to GUI if (current_search_time() > 2000) cout << "info" << depth_to_uci(depth) << " currmove " << move << " currmovenumber " << moveCount << endl; } // At Root and at first iteration do a PV search on all the moves to score root moves - isPvMove = (PvNode && moveCount <= (RootNode ? depth <= ONE_PLY ? MAX_MOVES : MultiPV : 1)); + isPvMove = (PvNode && moveCount <= (!RootNode ? 1 : depth <= ONE_PLY ? MAX_MOVES : MultiPV)); givesCheck = pos.move_gives_check(move, ci); - captureOrPromotion = pos.move_is_capture(move) || move_is_promotion(move); + captureOrPromotion = pos.move_is_capture_or_promotion(move); // Step 12. Decide the new search depth ext = extension(pos, move, captureOrPromotion, givesCheck, &dangerous); @@ -1107,13 +1092,12 @@ split_point_start: // At split points actual search starts from here } ss->currentMove = move; + if (!SpNode && !captureOrPromotion) + movesSearched[playedMoveCount++] = move; // Step 14. Make the move pos.do_move(move, st, ci, givesCheck); - if (!SpNode && !captureOrPromotion) - movesSearched[playedMoveCount++] = move; - // Step extra. pv search (only in PV nodes) // The first move in list is the expected PV if (isPvMove) @@ -1124,24 +1108,23 @@ split_point_start: // At split points actual search starts from here // Step 15. Reduced depth search // If the move fails high will be re-searched at full depth. bool doFullDepthSearch = true; - alpha = SpNode ? sp->alpha : alpha; if ( depth > 3 * ONE_PLY && !captureOrPromotion && !dangerous && !move_is_castle(move) && ss->killers[0] != move - && ss->killers[1] != move) + && ss->killers[1] != move + && (ss->reduction = reduction(depth, moveCount)) != DEPTH_ZERO) { - ss->reduction = reduction(depth, moveCount); - if (ss->reduction) - { - Depth d = newDepth - ss->reduction; - value = d < ONE_PLY ? -qsearch(pos, ss+1, -(alpha+1), -alpha, DEPTH_ZERO) - : - search(pos, ss+1, -(alpha+1), -alpha, d); - doFullDepthSearch = (value > alpha); - } - ss->reduction = DEPTH_ZERO; // Restore original reduction + Depth d = newDepth - ss->reduction; + alpha = SpNode ? sp->alpha : alpha; + + value = d < ONE_PLY ? -qsearch(pos, ss+1, -(alpha+1), -alpha, DEPTH_ZERO) + : - search(pos, ss+1, -(alpha+1), -alpha, d); + + ss->reduction = DEPTH_ZERO; + doFullDepthSearch = (value > alpha); } // Step 16. Full depth search @@ -1173,29 +1156,23 @@ split_point_start: // At split points actual search starts from here alpha = sp->alpha; } - if (value > bestValue && !(SpNode && thread.cutoff_occurred())) + if (value > bestValue) { bestValue = value; + ss->bestMove = move; - if (SpNode) - sp->bestValue = value; + if ( !RootNode + && PvNode + && value > alpha + && value < beta) // We want always alpha < beta + alpha = value; - if (!RootNode && value > alpha) + if (SpNode && !thread.cutoff_occurred()) { - if (PvNode && value < beta) // We want always alpha < beta - { - alpha = value; - - if (SpNode) - sp->alpha = value; - } - else if (SpNode) - sp->is_betaCutoff = true; - - ss->bestMove = move; - - if (SpNode) - sp->ss->bestMove = move; + sp->bestValue = value; + sp->ss->bestMove = move; + sp->alpha = alpha; + sp->is_betaCutoff = (value >= beta); } } @@ -1216,7 +1193,6 @@ split_point_start: // At split points actual search starts from here if (isPvMove || value > alpha) { // Update PV - ss->bestMove = move; mp.current().pv_score = value; mp.current().extract_pv_from_tt(pos); @@ -1230,7 +1206,7 @@ split_point_start: // At split points actual search starts from here // 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. - Rml.sort_first(moveCount); + sort(Rml.begin(), Rml.begin() + moveCount); // Update alpha. In multi-pv we don't use aspiration window, so set // alpha equal to minimum score among the PV lines searched so far. @@ -1279,8 +1255,7 @@ split_point_start: // At split points actual search starts from here // Update killers and history only for non capture moves that fails high if ( bestValue >= beta - && !pos.move_is_capture(move) - && !move_is_promotion(move)) + && !pos.move_is_capture_or_promotion(move)) { if (move != ss->killers[0]) { @@ -1413,7 +1388,7 @@ split_point_start: // At split points actual search starts from here && !pos.move_is_passed_pawn_push(move)) { futilityValue = futilityBase - + pos.endgame_value_of_piece_on(move_to(move)) + + piece_value_endgame(pos.piece_on(move_to(move))) + (move_is_ep(move) ? PawnValueEndgame : VALUE_ZERO); if (futilityValue < alpha) @@ -1450,8 +1425,7 @@ split_point_start: // At split points actual search starts from here && !inCheck && givesCheck && move != ttMove - && !pos.move_is_capture(move) - && !move_is_promotion(move) + && !pos.move_is_capture_or_promotion(move) && ss->eval + PawnValueMidgame / 4 < beta && !check_is_dangerous(pos, move, futilityBase, beta, &bestValue)) { @@ -1526,23 +1500,23 @@ split_point_start: // At split points actual search starts from here newAtt = pos.attacks_from(pc, to, occ); // Rule 1. Checks which give opponent's king at most one escape square are dangerous - b = kingAtt & ~pos.pieces_of_color(them) & ~newAtt & ~(1ULL << to); + b = kingAtt & ~pos.pieces(them) & ~newAtt & ~(1ULL << to); if (!(b && (b & (b - 1)))) return true; // Rule 2. Queen contact check is very dangerous - if ( type_of_piece(pc) == QUEEN + if ( piece_type(pc) == QUEEN && bit_is_set(kingAtt, to)) return true; // Rule 3. Creating new double threats with checks - b = pos.pieces_of_color(them) & newAtt & ~oldAtt & ~(1ULL << ksq); + b = pos.pieces(them) & newAtt & ~oldAtt & ~(1ULL << ksq); while (b) { victimSq = pop_1st_bit(&b); - futilityValue = futilityBase + pos.endgame_value_of_piece_on(victimSq); + futilityValue = futilityBase + piece_value_endgame(pos.piece_on(victimSq)); // Note that here we generate illegal "double move"! if ( futilityValue >= beta @@ -1568,7 +1542,8 @@ split_point_start: // At split points actual search starts from here bool connected_moves(const Position& pos, Move m1, Move m2) { Square f1, t1, f2, t2; - Piece p; + Piece p1, p2; + Square ksq; assert(m1 && move_is_ok(m1)); assert(m2 && move_is_ok(m2)); @@ -1586,26 +1561,24 @@ split_point_start: // At split points actual search starts from here return true; // Case 3: Moving through the vacated square - if ( piece_is_slider(pos.piece_on(f2)) + p2 = pos.piece_on(f2); + if ( piece_is_slider(p2) && bit_is_set(squares_between(f2, t2), f1)) return true; // Case 4: The destination square for m2 is defended by the moving piece in m1 - p = pos.piece_on(t1); - if (bit_is_set(pos.attacks_from(p, t1), t2)) + p1 = pos.piece_on(t1); + if (bit_is_set(pos.attacks_from(p1, t1), t2)) return true; // Case 5: Discovered check, checking piece is the piece moved in m1 - if ( piece_is_slider(p) - && bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), f2) - && !bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), t2)) + ksq = pos.king_square(pos.side_to_move()); + if ( piece_is_slider(p1) + && bit_is_set(squares_between(t1, ksq), f2)) { - // discovered_check_candidates() works also if the Position's side to - // move is the opposite of the checking piece. - Color them = opposite_color(pos.side_to_move()); - Bitboard dcCandidates = pos.discovered_check_candidates(them); - - if (bit_is_set(dcCandidates, f2)) + Bitboard occ = pos.occupied_squares(); + clear_bit(&occ, f2); + if (bit_is_set(pos.attacks_from(p1, t1, occ), ksq)) return true; } return false; @@ -1650,7 +1623,7 @@ split_point_start: // At split points actual search starts from here assert(move_is_ok(m)); assert(threat && move_is_ok(threat)); - assert(!pos.move_is_capture(m) && !move_is_promotion(m)); + assert(!pos.move_is_capture_or_promotion(m)); assert(!pos.move_is_passed_pawn_push(m)); Square mfrom, mto, tfrom, tto; @@ -1667,8 +1640,8 @@ split_point_start: // At split points actual search starts from here // Case 2: If the threatened piece has value less than or equal to the // value of the threatening piece, don't prune moves which defend it. if ( pos.move_is_capture(threat) - && ( pos.midgame_value_of_piece_on(tfrom) >= pos.midgame_value_of_piece_on(tto) - || pos.type_of_piece_on(tfrom) == KING) + && ( piece_value_midgame(pos.piece_on(tfrom)) >= piece_value_midgame(pos.piece_on(tto)) + || piece_type(pos.piece_on(tfrom)) == KING) && pos.move_attacks_square(m, tto)) return true; @@ -1805,11 +1778,11 @@ 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. - std::string pv_to_uci(Move pv[], int pvNum) { + std::string pv_to_uci(Move pv[], int pvNum, bool chess960) { std::stringstream s; - s << " multipv " << pvNum << " pv "; + s << " multipv " << pvNum << " pv " << set960(chess960); for ( ; *pv != MOVE_NONE; pv++) s << *pv << " "; @@ -2004,25 +1977,22 @@ split_point_start: // At split points actual search starts from here void RootMoveList::init(Position& pos, Move searchMoves[]) { - MoveStack mlist[MAX_MOVES]; Move* sm; - - clear(); bestMoveChanges = 0; + clear(); // Generate all legal moves and add them to RootMoveList - MoveStack* last = generate(pos, mlist); - for (MoveStack* cur = mlist; cur != last; cur++) + for (MoveList ml(pos); !ml.end(); ++ml) { - // If we have a searchMoves[] list then verify cur->move + // If we have a searchMoves[] list then verify the move // is in the list before to add it. - for (sm = searchMoves; *sm && *sm != cur->move; sm++) {} + for (sm = searchMoves; *sm && *sm != ml.move(); sm++) {} - if (searchMoves[0] && *sm != cur->move) + if (sm != searchMoves && *sm != ml.move()) continue; RootMove rm; - rm.pv[0] = cur->move; + rm.pv[0] = ml.move(); rm.pv[1] = MOVE_NONE; rm.pv_score = -VALUE_INFINITE; push_back(rm); @@ -2047,7 +2017,7 @@ split_point_start: // At split points actual search starts from here while ( (tte = TT.probe(pos.get_key())) != NULL && tte->move() != MOVE_NONE && pos.move_is_pl(tte->move()) - && pos.pl_move_is_legal(tte->move(), pos.pinned_pieces(pos.side_to_move())) + && pos.pl_move_is_legal(tte->move(), pos.pinned_pieces()) && ply < PLY_MAX && (!pos.is_draw() || ply < 2)) { @@ -2109,7 +2079,7 @@ split_point_start: // At split points actual search starts from here break; } - Rml.sort(); + sort(Rml.begin(), Rml.end()); } } // namespace