X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=2779bf8c83dfb27fb8d0c05822ecef8f9017add0;hp=4c33d263dc6aa42f2deb812b299bec99a943367d;hb=a230dc14045691667ffce46619de60497edceb88;hpb=9ec12da028948744317db3feaf11e90441e7fe9c diff --git a/src/search.cpp b/src/search.cpp index 4c33d263..2779bf8c 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -6,12 +6,12 @@ it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. - + Glaurung is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. - + You should have received a copy of the GNU General Public License along with this program. If not, see . */ @@ -51,10 +51,11 @@ namespace { // root move, we store a score, a node count, and a PV (really a refutation // in the case of moves which fail low). - class RootMove { + struct RootMove { - public: RootMove(); + bool operator<(const RootMove&); // used to sort + Move move; Value score; int64_t nodes, cumulativeNodes; @@ -75,14 +76,13 @@ namespace { void set_move_nodes(int moveNum, int64_t nodes); void set_move_pv(int moveNum, const Move pv[]); Move get_move_pv(int moveNum, int i) const; - int64_t get_move_cumulative_nodes(int moveNum); + int64_t get_move_cumulative_nodes(int moveNum) const; int move_count() const; Move scan_for_easy_move() const; void sort(); void sort_multipv(int n); private: - static bool compare_root_moves(const RootMove &rm1, const RootMove &rm2); static const int MaxRootMoves = 500; RootMove moves[MaxRootMoves]; int count; @@ -240,6 +240,7 @@ namespace { bool singleReply, bool mateThreat); bool ok_to_do_nullmove(const Position &pos); bool ok_to_prune(const Position &pos, Move m, Move threat, Depth d); + bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply); bool fail_high_ply_1(); int current_search_time(); @@ -266,7 +267,7 @@ namespace { #else DWORD WINAPI init_thread(LPVOID threadID); #endif - + } @@ -353,7 +354,7 @@ void think(const Position &pos, bool infinite, bool ponder, int time, Depth(get_option_value_int("Pawn Push to 7th Extension (non-PV nodes)")); PassedPawnExtension[1] = Depth(get_option_value_int("Passed Pawn Extension (PV nodes)")); - PassedPawnExtension[0] = + PassedPawnExtension[0] = Depth(get_option_value_int("Passed Pawn Extension (non-PV nodes)")); PawnEndgameExtension[1] = Depth(get_option_value_int("Pawn Endgame Extension (PV nodes)")); @@ -396,7 +397,7 @@ void think(const Position &pos, bool infinite, bool ponder, int time, get_option_value_int("Maximum Number of Threads per Split Point"); read_weights(pos.side_to_move()); - + int newActiveThreads = get_option_value_int("Threads"); if(newActiveThreads != ActiveThreads) { ActiveThreads = newActiveThreads; @@ -458,11 +459,11 @@ void think(const Position &pos, bool infinite, bool ponder, int time, // We're ready to start thinking. Call the iterative deepening loop // function: - id_loop(pos, searchMoves); + id_loop(pos, searchMoves);; if(UseLogFile) LogFile.close(); - + if(Quit) { OpeningBook.close(); stop_threads(); @@ -492,7 +493,7 @@ void init_threads() { lock_init(&IOLock, NULL); init_split_point_stack(); - + #if !defined(_MSC_VER) pthread_mutex_init(&WaitLock, NULL); pthread_cond_init(&WaitCond, NULL); @@ -645,7 +646,7 @@ namespace { } } - // Write PV to transposition table, in case the relevant entries have + // Write PV to transposition table, in case the relevant entries have // been overwritten during the search: TT.insert_pv(p, ss[0].pv); @@ -712,7 +713,7 @@ namespace { if(current_search_time() >= 1000) std::cout << "info currmove " << move << " currmovenumber " << i + 1 << std::endl; - + // Decide search depth for this move: ext = extension(pos, move, true, pos.move_is_check(move), false, false); newDepth = (Iteration-2)*OnePly + ext + InitialDepth; @@ -734,7 +735,7 @@ namespace { else { value = -search(pos, ss, -alpha, newDepth, 1, true, 0); if(value > alpha) { - // Fail high! Set the boolean variable FailHigh to true, and + // Fail high! Set the boolean variable FailHigh to true, and // re-search the move with a big window. The variable FailHigh is // used for time managment: We try to avoid aborting the search // prematurely during a fail high research. @@ -753,7 +754,7 @@ namespace { if(AbortSearch) break; - // Remember the node count for this move. The node counts are used to + // Remember the node count for this move. The node counts are used to // sort the root moves at the next iteration. rml.set_move_nodes(i, nodes_searched() - nodes); @@ -770,7 +771,7 @@ namespace { rml.set_move_pv(i, ss[0].pv); if(MultiPV == 1) { - // We record how often the best move has been changed in each + // 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(i > 0) @@ -858,15 +859,12 @@ namespace { return alpha; // Transposition table lookup. At PV nodes, we don't use the TT for - // pruning, but only for move ordering. - Value ttValue; - Depth ttDepth; - Move ttMove = MOVE_NONE; - ValueType ttValueType; + // pruning, but only for move ordering. + const TTEntry* tte = TT.retrieve(pos); - TT.retrieve(pos, &ttValue, &ttDepth, &ttMove, &ttValueType); + Move ttMove = (tte ? tte->move() : MOVE_NONE); - // Internal iterative deepening. + // Go with internal iterative deepening if we don't have a TT move. if(UseIIDAtPVNodes && ttMove == MOVE_NONE && depth >= 5*OnePly) { search_pv(pos, ss, alpha, beta, depth-2*OnePly, ply, threadID); ttMove = ss[ply].pv[ply]; @@ -894,7 +892,7 @@ namespace { bool moveIsCheck = pos.move_is_check(move, dcCandidates); bool moveIsCapture = pos.move_is_capture(move); bool moveIsPassedPawnPush = pos.move_is_passed_pawn_push(move); - + assert(move_is_ok(move)); movesSearched[moveCount++] = ss[ply].currentMove = move; @@ -907,8 +905,8 @@ namespace { // Make and search the move. pos.do_move(move, u, dcCandidates); - - if(moveCount == 1) + + if(moveCount == 1) value = -search_pv(pos, ss, -beta, -alpha, newDepth, ply+1, threadID); else { if(depth >= 2*OnePly && ext == Depth(0) && moveCount >= LMRPVMoves @@ -916,7 +914,7 @@ namespace { && !moveIsPassedPawnPush && !move_is_castle(move) && move != ss[ply].killer1 && move != ss[ply].killer2) { ss[ply].reduction = OnePly; - value = -search(pos, ss, -alpha, newDepth-OnePly, ply+1, true, + value = -search(pos, ss, -alpha, newDepth-OnePly, ply+1, true, threadID); } else value = alpha + 1; @@ -931,7 +929,7 @@ namespace { // such cases, because resolving the fail high at ply 1 could // result in a big drop in score at the root. Threads[threadID].failHighPly1 = true; - value = -search_pv(pos, ss, -beta, -alpha, newDepth, ply+1, + value = -search_pv(pos, ss, -beta, -alpha, newDepth, ply+1, threadID); Threads[threadID].failHighPly1 = false; } @@ -940,7 +938,7 @@ namespace { pos.undo_move(move, u); assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); - + // New best move? if(value > bestValue) { bestValue = value; @@ -976,7 +974,7 @@ namespace { return VALUE_DRAW; } - // If the search is not aborted, update the transposition table, + // If the search is not aborted, update the transposition table, // history counters, and killer moves. This code is somewhat messy, // and definitely needs to be cleaned up. FIXME if(!AbortSearch && !thread_should_stop(threadID)) { @@ -995,7 +993,7 @@ namespace { movesSearched[i]); H.success(pos.piece_on(move_from(m)), m, depth); - + if(m != ss[ply].killer1) { ss[ply].killer2 = ss[ply].killer1; ss[ply].killer1 = m; @@ -1010,7 +1008,7 @@ namespace { return bestValue; } - + // search() is the search function for zero-width nodes. @@ -1045,24 +1043,14 @@ namespace { return beta-1; // Transposition table lookup - bool ttFound; - Value ttValue; - Depth ttDepth; - Move ttMove = MOVE_NONE; - ValueType ttValueType; - - ttFound = TT.retrieve(pos, &ttValue, &ttDepth, &ttMove, &ttValueType); - if(ttFound) { - ttValue = value_from_tt(ttValue, ply); - if(ttDepth >= depth - || ttValue >= Max(value_mate_in(100), beta) - || ttValue < Min(value_mated_in(100), beta)) { - if((is_lower_bound(ttValueType) && ttValue >= beta) || - (is_upper_bound(ttValueType) && ttValue < beta)) { - ss[ply].currentMove = ttMove; - return ttValue; - } - } + const TTEntry* tte = TT.retrieve(pos); + + Move ttMove = (tte ? tte->move() : MOVE_NONE); + + if (tte && ok_to_use_TT(tte, depth, beta, ply)) + { + ss[ply].currentMove = ttMove; // can be MOVE_NONE ? + return value_from_tt(tte->value(), ply); } Value approximateEval = quick_evaluate(pos); @@ -1152,7 +1140,7 @@ namespace { // Futility pruning if(useFutilityPruning && ext == Depth(0) && !moveIsCapture && !moveIsPassedPawnPush && !move_promotion(move)) { - + if(moveCount >= 2 + int(depth) && ok_to_prune(pos, move, ss[ply].threatMove, depth)) continue; @@ -1171,7 +1159,7 @@ namespace { // Make and search the move. pos.do_move(move, u, dcCandidates); - + if(depth >= 2*OnePly && ext == Depth(0) && moveCount >= LMRNonPVMoves && !moveIsCapture && !move_promotion(move) && !moveIsPassedPawnPush && !move_is_castle(move) @@ -1189,7 +1177,7 @@ namespace { pos.undo_move(move, u); assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); - + // New best move? if(value > bestValue) { bestValue = value; @@ -1226,7 +1214,7 @@ namespace { VALUE_TYPE_UPPER); else { Move m = ss[ply].pv[ply]; - + if(pos.square_is_empty(move_to(m)) && !move_promotion(m) && !move_is_ep(m)) { for(int i = 0; i < moveCount - 1; i++) @@ -1236,7 +1224,7 @@ namespace { H.failure(pos.piece_on(move_from(movesSearched[i])), movesSearched[i]); H.success(pos.piece_on(move_from(m)), m, depth); - + if(m != ss[ply].killer1) { ss[ply].killer2 = ss[ply].killer1; ss[ply].killer1 = m; @@ -1248,7 +1236,7 @@ namespace { return bestValue; } - + // qsearch() is the quiescence search function, which is called by the main // search function when the remaining depth is zero (or, to be more precise, @@ -1265,7 +1253,7 @@ namespace { assert(ply >= 0 && ply < PLY_MAX); assert(threadID >= 0 && threadID < ActiveThreads); - // Initialize, and make an early exit in case of an aborted search, + // Initialize, and make an early exit in case of an aborted search, // an instant draw, maximum ply reached, etc. if(AbortSearch || thread_should_stop(threadID)) return Value(0); @@ -1302,7 +1290,7 @@ namespace { Bitboard dcCandidates = mp.discovered_check_candidates(); bool isCheck = pos.is_check(); - // Loop through the moves until no moves remain or a beta cutoff + // Loop through the moves until no moves remain or a beta cutoff // occurs. while(alpha < beta && ((move = mp.get_next_move()) != MOVE_NONE)) { UndoInfo u; @@ -1315,18 +1303,18 @@ namespace { ss[ply].currentMove = move; // Futility pruning - if(UseQSearchFutilityPruning && !isCheck && !moveIsCheck && - !move_promotion(move) && !moveIsPassedPawnPush && + if(UseQSearchFutilityPruning && !isCheck && !moveIsCheck && + !move_promotion(move) && !moveIsPassedPawnPush && beta - alpha == 1 && pos.non_pawn_material(pos.side_to_move()) > RookValueMidgame) { Value futilityValue = - staticValue + staticValue + Max(pos.midgame_value_of_piece_on(move_to(move)), pos.endgame_value_of_piece_on(move_to(move))) + FutilityMargin0 + ei.futilityMargin; if(futilityValue < alpha) { - if(futilityValue > bestValue) + if(futilityValue > bestValue) bestValue = futilityValue; continue; } @@ -1357,7 +1345,7 @@ namespace { } // All legal moves have been searched. A special case: If we're in check - // and no legal moves were found, it is checkmate: + // and no legal moves were found, it is checkmate: if(pos.is_check() && moveCount == 0) // Mate! return value_mated_in(ply); @@ -1374,11 +1362,11 @@ namespace { // splitting, we don't have to repeat all this work in sp_search(). We // also don't need to store anything to the hash table here: This is taken // care of after we return from the split point. - + void sp_search(SplitPoint *sp, int threadID) { assert(threadID >= 0 && threadID < ActiveThreads); assert(ActiveThreads > 1); - + Position pos = Position(sp->pos); SearchStack *ss = sp->sstack[threadID]; Value value; @@ -1439,7 +1427,7 @@ namespace { if(thread_should_stop(threadID)) break; - + // New best move? lock_grab(&(sp->lock)); if(value > sp->bestValue && !thread_should_stop(threadID)) { @@ -1478,11 +1466,11 @@ namespace { // don't have to repeat all this work in sp_search_pv(). We also don't // need to store anything to the hash table here: This is taken care of // after we return from the split point. - + void sp_search_pv(SplitPoint *sp, int threadID) { assert(threadID >= 0 && threadID < ActiveThreads); assert(ActiveThreads > 1); - + Position pos = Position(sp->pos); SearchStack *ss = sp->sstack[threadID]; Value value; @@ -1508,7 +1496,7 @@ namespace { lock_release(&(sp->lock)); ss[sp->ply].currentMove = move; - + // Decide the new search depth. ext = extension(pos, move, true, moveIsCheck, false, false); newDepth = sp->depth - OnePly + ext; @@ -1548,7 +1536,7 @@ namespace { if(thread_should_stop(threadID)) break; - + // New best move? lock_grab(&(sp->lock)); if(value > sp->bestValue && !thread_should_stop(threadID)) { @@ -1588,8 +1576,22 @@ namespace { sp->slaves[threadID] = 0; lock_release(&(sp->lock)); - } + } + + // ok_to_use_TT() returns true if a transposition table score + // can be used at a given point in search. + bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply) { + + Value v = value_from_tt(tte->value(), ply); + + return ( tte->depth() >= depth + || v >= Max(value_mate_in(100), beta) + || v < Min(value_mated_in(100), beta)) + + && ( (is_lower_bound(tte->type()) && v >= beta) + || (is_upper_bound(tte->type()) && v < beta)); + } /// The RootMove class @@ -1598,7 +1600,19 @@ namespace { RootMove::RootMove() { nodes = cumulativeNodes = 0ULL; } - + + // RootMove::operator<() is the comparison function used when + // sorting the moves. A move m1 is considered to be better + // than a move m2 if it has a higher score, or if the moves + // have equal score but m1 has the higher node count. + + bool RootMove::operator<(const RootMove& m) { + + if (score != m.score) + return (score < m.score); + + return nodes <= m.nodes; + } /// The RootMoveList class @@ -1627,7 +1641,7 @@ namespace { SearchStack ss[PLY_MAX_PLUS_2]; moves[count].move = mlist[i].move; - moves[count].nodes = 0ULL; + moves[count].nodes = 0ULL; pos.do_move(moves[count].move, u); moves[count].score = -qsearch(pos, ss, -VALUE_INFINITE, VALUE_INFINITE, Depth(0), 1, 0); @@ -1643,19 +1657,19 @@ namespace { // Simple accessor methods for the RootMoveList class - Move RootMoveList::get_move(int moveNum) const { + inline Move RootMoveList::get_move(int moveNum) const { return moves[moveNum].move; } - Value RootMoveList::get_move_score(int moveNum) const { + inline Value RootMoveList::get_move_score(int moveNum) const { return moves[moveNum].score; } - void RootMoveList::set_move_score(int moveNum, Value score) { + inline void RootMoveList::set_move_score(int moveNum, Value score) { moves[moveNum].score = score; } - - void RootMoveList::set_move_nodes(int moveNum, int64_t nodes) { + + inline void RootMoveList::set_move_nodes(int moveNum, int64_t nodes) { moves[moveNum].nodes = nodes; moves[moveNum].cumulativeNodes += nodes; } @@ -1667,15 +1681,15 @@ namespace { moves[moveNum].pv[j] = MOVE_NONE; } - Move RootMoveList::get_move_pv(int moveNum, int i) const { + inline Move RootMoveList::get_move_pv(int moveNum, int i) const { return moves[moveNum].pv[i]; } - int64_t RootMoveList::get_move_cumulative_nodes(int moveNum) { + inline int64_t RootMoveList::get_move_cumulative_nodes(int moveNum) const { return moves[moveNum].cumulativeNodes; } - - int RootMoveList::move_count() const { + + inline int RootMoveList::move_count() const { return count; } @@ -1690,58 +1704,44 @@ namespace { Move RootMoveList::scan_for_easy_move() const { - Value bestMoveValue = this->get_move_score(0); - for(int i = 1; i < this->move_count(); i++) - if(this->get_move_score(i) >= bestMoveValue - EasyMoveMargin) - return MOVE_NONE; - return this->get_move(0); - } + assert(count); + + if (count == 1) + return get_move(0); + // moves are sorted so just consider the best and the second one + if (get_move_score(0) > get_move_score(1) + EasyMoveMargin) + return get_move(0); + + return MOVE_NONE; + } // RootMoveList::sort() sorts the root move list at the beginning of a new // iteration. - void RootMoveList::sort() { - for(int i = 1; i < count; i++) { - RootMove rm = moves[i]; - int j; - for(j = i; j > 0 && compare_root_moves(moves[j-1], rm); j--) - moves[j] = moves[j-1]; - moves[j] = rm; - } + inline void RootMoveList::sort() { + + sort_multipv(count - 1); // all items } // RootMoveList::sort_multipv() sorts the first few moves in the root move - // list by their scores and depths. It is used to order the different PVs + // list by their scores and depths. It is used to order the different PVs // correctly in MultiPV mode. void RootMoveList::sort_multipv(int n) { - for(int i = 1; i <= n; i++) { + + for (int i = 1; i <= n; i++) + { RootMove rm = moves[i]; int j; - for(j = i; j > 0 && moves[j-1].score < rm.score; j--) - moves[j] = moves[j-1]; + for (j = i; j > 0 && moves[j-1] < rm; j--) + moves[j] = moves[j-1]; moves[j] = rm; } } - // RootMoveList::compare_root_moves() is the comparison function used by - // RootMoveList::sort when sorting the moves. A move m1 is considered to - // be better than a move m2 if it has a higher score, or if the moves have - // equal score but m1 has the higher node count. - - bool RootMoveList::compare_root_moves(const RootMove &rm1, - const RootMove &rm2) { - - if (rm1.score != rm2.score) - return (rm1.score < rm2.score); - - return rm1.nodes <= rm2.nodes; - } - - // init_search_stack() initializes a search stack at the beginning of a // new search from the root. @@ -1794,7 +1794,7 @@ namespace { // update_pv() is called whenever a search returns a value > alpha. It // updates the PV in the SearchStack object corresponding to the current // node. - + void update_pv(SearchStack ss[], int ply) { assert(ply >= 0 && ply < PLY_MAX); @@ -1885,8 +1885,8 @@ namespace { return false; } - - + + // extension() decides whether a move should be searched with normal depth, // or with extended depth. Certain classes of moves (checking moves, in // particular) are searched with bigger depth than ordinary moves. @@ -1972,7 +1972,7 @@ namespace { // Case 4: Don't prune moves with good history. if(!H.ok_to_prune(pos.piece_on(move_from(m)), m, d)) return false; - + // Case 5: If the moving piece in the threatened move is a slider, don't // prune safe moves which block its ray. if(!PruneBlockingMoves && threat != MOVE_NONE @@ -1982,12 +1982,12 @@ namespace { return true; } - + // fail_high_ply_1() checks if some thread is currently resolving a fail // high at ply 1 at the node below the first root node. This information // is used for time managment. - + bool fail_high_ply_1() { for(int i = 0; i < ActiveThreads; i++) if(Threads[i].failHighPly1) @@ -2040,7 +2040,7 @@ namespace { else if(strncmp(input, "ponderhit", 9) == 0) ponderhit(); } - + // Print search information if(t < 1000) lastInfoTime = 0; @@ -2054,7 +2054,7 @@ namespace { std::cout << "info nodes " << nodes_searched() << " nps " << nps() << " time " << t << " hashfull " << TT.full() << std::endl; lock_release(&IOLock); - if(ShowCurrentLine) + if(ShowCurrentLine) Threads[0].printCurrentLine = true; } @@ -2096,7 +2096,7 @@ namespace { // print_current_line() prints the current line of search for a given // thread. Called when the UCI option UCI_ShowCurrLine is 'true'. - + void print_current_line(SearchStack ss[], int ply, int threadID) { assert(ply >= 0 && ply < PLY_MAX); assert(threadID >= 0 && threadID < ActiveThreads); @@ -2121,14 +2121,14 @@ namespace { // "bestmove" before the GUI sends it a "stop" or "ponderhit" command. // We simply wait here until one of these commands is sent, and return, // after which the bestmove and pondermove will be printed (in id_loop()). - + void wait_for_stop_or_ponderhit() { std::string command; while(true) { if(!std::getline(std::cin, command)) command = "quit"; - + if(command == "quit") { OpeningBook.close(); stop_threads(); @@ -2140,7 +2140,7 @@ namespace { } } - + // idle_loop() is where the threads are parked when they have no work to do. // The parameter "waitSp", if non-NULL, is a pointer to an active SplitPoint // object for which the current thread is the master. @@ -2148,7 +2148,7 @@ namespace { void idle_loop(int threadID, SplitPoint *waitSp) { assert(threadID >= 0 && threadID < THREAD_MAX); - Threads[threadID].running = true; + Threads[threadID].running = true; while(true) { if(AllThreadsShouldExit && threadID != 0) @@ -2206,7 +2206,7 @@ namespace { for(int i = 0; i < THREAD_MAX; i++) for(int j = 0; j < MaxActiveSplitPoints; j++) lock_destroy(&(SplitPointStack[i][j].lock)); - } + } // thread_should_stop() checks whether the thread with a given threadID has @@ -2216,7 +2216,7 @@ namespace { bool thread_should_stop(int threadID) { assert(threadID >= 0 && threadID < ActiveThreads); - + SplitPoint *sp; if(Threads[threadID].stop) @@ -2229,7 +2229,7 @@ namespace { return true; } return false; - } + } // thread_is_available() checks whether the thread with threadID "slave" is @@ -2244,7 +2244,7 @@ namespace { assert(slave >= 0 && slave < ActiveThreads); assert(master >= 0 && master < ActiveThreads); assert(ActiveThreads > 1); - + if(!Threads[slave].idle || slave == master) return false; @@ -2263,14 +2263,14 @@ namespace { return false; } - + // idle_thread_exists() tries to find an idle thread which is available as // a slave for the thread with threadID "master". bool idle_thread_exists(int master) { assert(master >= 0 && master < ActiveThreads); assert(ActiveThreads > 1); - + for(int i = 0; i < ActiveThreads; i++) if(thread_is_available(i, master)) return true; @@ -2408,20 +2408,20 @@ namespace { #endif } } - + // init_thread() is the function which is called when a new thread is // launched. It simply calls the idle_loop() function with the supplied // threadID. There are two versions of this function; one for POSIX threads // and one for Windows threads. - + #if !defined(_MSC_VER) void *init_thread(void *threadID) { idle_loop(*(int *)threadID, NULL); return NULL; } - + #else DWORD WINAPI init_thread(LPVOID threadID) {