X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=94b34389178f0f18119d010bea23c8bdebf3d06e;hp=092f7d73ed084be2a4a6881890d23a429e072523;hb=a1f9bf19d9aa542fd5109a4ce997eac8122568d4;hpb=e5077dc11e8047eb8ce32a166a73e433a7e19b15 diff --git a/src/search.cpp b/src/search.cpp index 092f7d73..94b34389 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; }; @@ -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; } @@ -403,7 +393,7 @@ bool think(Position& pos, const SearchLimits& limits, Move searchMoves[]) { NodesSincePoll = 0; current_search_time(get_system_time()); Limits = limits; - TimeMgr.init(Limits, pos.full_moves()); + TimeMgr.init(Limits, pos.startpos_ply_counter()); // Set output steram in normal or chess960 mode cout << set960(pos.is_chess960()); @@ -736,7 +726,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 +742,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 +768,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; @@ -976,7 +967,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,14 +995,14 @@ 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_or_promotion(move); @@ -1107,13 +1098,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 +1114,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 +1162,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 +1199,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 +1212,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. @@ -1566,7 +1548,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)); @@ -1584,26 +1567,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; @@ -2002,25 +1983,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); @@ -2045,7 +2023,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)) { @@ -2107,7 +2085,7 @@ split_point_start: // At split points actual search starts from here break; } - Rml.sort(); + sort(Rml.begin(), Rml.end()); } } // namespace