X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=e4675df56ea35b75b39a14c9672e901310d3f6e5;hp=55533ddd9af8caba5ae9f009e407cd13d77f71fe;hb=925f97f4e761136c8a845d98f55303137fade589;hpb=6c592955e1f4a1dcbd1b139dc224573fd34fd0ce diff --git a/src/search.cpp b/src/search.cpp index 55533ddd..e4675df5 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -241,6 +241,9 @@ namespace { 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 ok_to_history(const Position &pos, Move m); + void update_history(const Position& pos, Move m, Depth depth, + Move movesSearched[], int moveCount); bool fail_high_ply_1(); int current_search_time(); @@ -339,7 +342,7 @@ void think(const Position &pos, bool infinite, bool ponder, int time, TT.set_size(get_option_value_int("Hash")); if(button_was_pressed("Clear Hash")) TT.clear(); - PonderingEnabled = get_option_value_int("Ponder"); + PonderingEnabled = get_option_value_bool("Ponder"); MultiPV = get_option_value_int("MultiPV"); CheckExtension[1] = Depth(get_option_value_int("Check Extension (PV nodes)")); @@ -932,7 +935,7 @@ namespace { else value = alpha + 1; // Just to trigger next condition - if (value > alpha) // Go with full depth non-pv search + if (value > alpha) // Go with full depth pv search { ss[ply].reduction = Depth(0); value = -search(pos, ss, -alpha, newDepth, ply+1, true, threadID); @@ -993,8 +996,7 @@ namespace { return (pos.is_check() ? value_mated_in(ply) : VALUE_DRAW); // 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 + // history counters, and killer moves. if (AbortSearch || thread_should_stop(threadID)) return bestValue; @@ -1004,21 +1006,14 @@ namespace { else if (bestValue >= beta) { Move m = ss[ply].pv[ply]; - if (pos.square_is_empty(move_to(m)) && !move_promotion(m) && !move_is_ep(m)) + if (ok_to_history(pos, m)) // Only non capture moves are considered { - for (int i = 0; i < moveCount - 1; i++) - if ( pos.square_is_empty(move_to(movesSearched[i])) - && !move_promotion(movesSearched[i]) - && !move_is_ep(movesSearched[i])) - 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; - } + update_history(pos, m, depth, movesSearched, moveCount); + if (m != ss[ply].killer1) + { + ss[ply].killer2 = ss[ply].killer1; + ss[ply].killer1 = m; + } } TT.store(pos, value_to_tt(bestValue, ply), depth, m, VALUE_TYPE_LOWER); } @@ -1255,8 +1250,7 @@ namespace { return (pos.is_check() ? value_mated_in(ply) : VALUE_DRAW); // 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 + // history counters, and killer moves. if (AbortSearch || thread_should_stop(threadID)) return bestValue; @@ -1265,16 +1259,9 @@ namespace { else { Move m = ss[ply].pv[ply]; - if (pos.square_is_empty(move_to(m)) && !move_promotion(m) && !move_is_ep(m)) + if (ok_to_history(pos, m)) // Only non capture moves are considered { - for (int i = 0; i < moveCount - 1; i++) - if ( pos.square_is_empty(move_to(movesSearched[i])) - && !move_promotion(movesSearched[i]) - && !move_is_ep(movesSearched[i])) - H.failure(pos.piece_on(move_from(movesSearched[i])), movesSearched[i]); - - H.success(pos.piece_on(move_from(m)), m, depth); - + update_history(pos, m, depth, movesSearched, moveCount); if (m != ss[ply].killer1) { ss[ply].killer2 = ss[ply].killer1; @@ -1312,6 +1299,11 @@ namespace { if (pos.is_draw()) return VALUE_DRAW; + // Transposition table lookup + const TTEntry* tte = TT.retrieve(pos); + if (tte && ok_to_use_TT(tte, depth, beta, ply)) + return value_from_tt(tte->value(), ply); + // Evaluate the position statically: Value staticValue = evaluate(pos, ei, threadID); @@ -1409,6 +1401,9 @@ namespace { assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); + // Update transposition table + TT.store(pos, value_to_tt(bestValue, ply), depth, MOVE_NONE, VALUE_TYPE_EXACT); + return bestValue; } @@ -1422,6 +1417,7 @@ namespace { // care of after we return from the split point. void sp_search(SplitPoint *sp, int threadID) { + assert(threadID >= 0 && threadID < ActiveThreads); assert(ActiveThreads > 1); @@ -1429,73 +1425,87 @@ namespace { SearchStack *ss = sp->sstack[threadID]; Value value; Move move; - int moveCount = sp->moves; bool isCheck = pos.is_check(); - bool useFutilityPruning = - UseFutilityPruning && sp->depth < SelectiveDepth && !isCheck; + bool useFutilityPruning = UseFutilityPruning + && sp->depth < SelectiveDepth + && !isCheck; + + while ( sp->bestValue < sp->beta + && !thread_should_stop(threadID) + && (move = sp->mp->get_next_move(sp->lock)) != MOVE_NONE) + { + assert(move_is_ok(move)); - while(sp->bestValue < sp->beta && !thread_should_stop(threadID) - && (move = sp->mp->get_next_move(sp->lock)) != MOVE_NONE) { - UndoInfo u; - Depth ext, newDepth; bool moveIsCheck = pos.move_is_check(move, sp->dcCandidates); bool moveIsCapture = pos.move_is_capture(move); bool moveIsPassedPawnPush = pos.move_is_passed_pawn_push(move); - assert(move_is_ok(move)); - lock_grab(&(sp->lock)); - sp->moves++; - moveCount = sp->moves; + int moveCount = ++sp->moves; lock_release(&(sp->lock)); ss[sp->ply].currentMove = move; // Decide the new search depth. - ext = extension(pos, move, false, moveIsCheck, false, false); - newDepth = sp->depth - OnePly + ext; + Depth ext = extension(pos, move, false, moveIsCheck, false, false); + Depth newDepth = sp->depth - OnePly + ext; // Prune? - if(useFutilityPruning && ext == Depth(0) && !moveIsCapture - && !moveIsPassedPawnPush && !move_promotion(move) - && moveCount >= 2 + int(sp->depth) - && ok_to_prune(pos, move, ss[sp->ply].threatMove, sp->depth)) + if ( useFutilityPruning + && ext == Depth(0) + && !moveIsCapture + && !moveIsPassedPawnPush + && !move_promotion(move) + && moveCount >= 2 + int(sp->depth) + && ok_to_prune(pos, move, ss[sp->ply].threatMove, sp->depth)) continue; // Make and search the move. + UndoInfo u; pos.do_move(move, u, sp->dcCandidates); - if(ext == Depth(0) && moveCount >= LMRNonPVMoves - && !moveIsCapture && !move_promotion(move) && !moveIsPassedPawnPush - && !move_is_castle(move) - && move != ss[sp->ply].killer1 && move != ss[sp->ply].killer2) { - ss[sp->ply].reduction = OnePly; - value = -search(pos, ss, -(sp->beta-1), newDepth - OnePly, sp->ply+1, - true, threadID); + + // Try to reduce non-pv search depth by one ply if move seems not problematic, + // if the move fails high will be re-searched at full depth. + if ( ext == Depth(0) + && moveCount >= LMRNonPVMoves + && !moveIsCapture + && !moveIsPassedPawnPush + && !move_promotion(move) + && !move_is_castle(move) + && move != ss[sp->ply].killer1 + && move != ss[sp->ply].killer2) + { + ss[sp->ply].reduction = OnePly; + value = -search(pos, ss, -(sp->beta-1), newDepth - OnePly, sp->ply+1, true, threadID); } else - value = sp->beta; - if(value >= sp->beta) { - ss[sp->ply].reduction = Depth(0); - value = -search(pos, ss, -(sp->beta - 1), newDepth, sp->ply+1, true, - threadID); + value = sp->beta; // Just to trigger next condition + + if (value >= sp->beta) // Go with full depth non-pv search + { + ss[sp->ply].reduction = Depth(0); + value = -search(pos, ss, -(sp->beta - 1), newDepth, sp->ply+1, true, threadID); } pos.undo_move(move, u); assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); - if(thread_should_stop(threadID)) - break; + if (thread_should_stop(threadID)) + break; // New best move? lock_grab(&(sp->lock)); - if(value > sp->bestValue && !thread_should_stop(threadID)) { - sp->bestValue = value; - if(sp->bestValue >= sp->beta) { - sp_update_pv(sp->parentSstack, ss, sp->ply); - for(int i = 0; i < ActiveThreads; i++) - if(i != threadID && (i == sp->master || sp->slaves[i])) - Threads[i].stop = true; - sp->finished = true; + if (value > sp->bestValue && !thread_should_stop(threadID)) + { + sp->bestValue = value; + if (sp->bestValue >= sp->beta) + { + sp_update_pv(sp->parentSstack, ss, sp->ply); + for (int i = 0; i < ActiveThreads; i++) + if (i != threadID && (i == sp->master || sp->slaves[i])) + Threads[i].stop = true; + + sp->finished = true; } } lock_release(&(sp->lock)); @@ -1505,10 +1515,10 @@ namespace { // If this is the master thread and we have been asked to stop because of // a beta cutoff higher up in the tree, stop all slave threads: - if(sp->master == threadID && thread_should_stop(threadID)) - for(int i = 0; i < ActiveThreads; i++) - if(sp->slaves[i]) - Threads[i].stop = true; + if (sp->master == threadID && thread_should_stop(threadID)) + for (int i = 0; i < ActiveThreads; i++) + if (sp->slaves[i]) + Threads[i].stop = true; sp->cpus--; sp->slaves[threadID] = 0; @@ -1526,6 +1536,7 @@ namespace { // after we return from the split point. void sp_search_pv(SplitPoint *sp, int threadID) { + assert(threadID >= 0 && threadID < ActiveThreads); assert(ActiveThreads > 1); @@ -1533,12 +1544,11 @@ namespace { SearchStack *ss = sp->sstack[threadID]; Value value; Move move; - int moveCount = sp->moves; - while(sp->alpha < sp->beta && !thread_should_stop(threadID) - && (move = sp->mp->get_next_move(sp->lock)) != MOVE_NONE) { - UndoInfo u; - Depth ext, newDepth; + while ( sp->alpha < sp->beta + && !thread_should_stop(threadID) + && (move = sp->mp->get_next_move(sp->lock)) != MOVE_NONE) + { bool moveIsCheck = pos.move_is_check(move, sp->dcCandidates); bool moveIsCapture = pos.move_is_capture(move); bool moveIsPassedPawnPush = pos.move_is_passed_pawn_push(move); @@ -1549,74 +1559,88 @@ namespace { PawnValueMidgame : pos.midgame_value_of_piece_on(move_to(move)); lock_grab(&(sp->lock)); - sp->moves++; - moveCount = sp->moves; + int moveCount = ++sp->moves; 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; + Depth ext = extension(pos, move, true, moveIsCheck, false, false); + Depth newDepth = sp->depth - OnePly + ext; // Make and search the move. + UndoInfo u; pos.do_move(move, u, sp->dcCandidates); - if(ext == Depth(0) && moveCount >= LMRPVMoves && !moveIsCapture - && !move_promotion(move) && !moveIsPassedPawnPush - && !move_is_castle(move) - && move != ss[sp->ply].killer1 && move != ss[sp->ply].killer2) { - ss[sp->ply].reduction = OnePly; - value = -search(pos, ss, -sp->alpha, newDepth - OnePly, sp->ply+1, - true, threadID); + + // Try to reduce non-pv search depth by one ply if move seems not problematic, + // if the move fails high will be re-searched at full depth. + if ( ext == Depth(0) + && moveCount >= LMRPVMoves + && !moveIsCapture + && !moveIsPassedPawnPush + && !move_promotion(move) + && !move_is_castle(move) + && move != ss[sp->ply].killer1 + && move != ss[sp->ply].killer2) + { + ss[sp->ply].reduction = OnePly; + value = -search(pos, ss, -sp->alpha, newDepth - OnePly, sp->ply+1, true, threadID); } else - value = sp->alpha + 1; - if(value > sp->alpha) { - ss[sp->ply].reduction = Depth(0); - value = -search(pos, ss, -sp->alpha, newDepth, sp->ply+1, true, - threadID); - if(value > sp->alpha && value < sp->beta) { - if(sp->ply == 1 && RootMoveNumber == 1) - // When the search fails high at ply 1 while searching the first - // move at the root, set the flag failHighPly1. This is used for - // time managment: We don't want to stop the search early in - // 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, -sp->beta, -sp->alpha, newDepth, - sp->ply+1, threadID); - Threads[threadID].failHighPly1 = false; + value = sp->alpha + 1; // Just to trigger next condition + + if (value > sp->alpha) // Go with full depth non-pv search + { + ss[sp->ply].reduction = Depth(0); + value = -search(pos, ss, -sp->alpha, newDepth, sp->ply+1, true, threadID); + + if (value > sp->alpha && value < sp->beta) + { + // When the search fails high at ply 1 while searching the first + // move at the root, set the flag failHighPly1. This is used for + // time managment: We don't want to stop the search early in + // such cases, because resolving the fail high at ply 1 could + // result in a big drop in score at the root. + if (sp->ply == 1 && RootMoveNumber == 1) + Threads[threadID].failHighPly1 = true; + + value = -search_pv(pos, ss, -sp->beta, -sp->alpha, newDepth, sp->ply+1, threadID); + Threads[threadID].failHighPly1 = false; } } pos.undo_move(move, u); assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); - if(thread_should_stop(threadID)) - break; + if (thread_should_stop(threadID)) + break; // New best move? lock_grab(&(sp->lock)); - if(value > sp->bestValue && !thread_should_stop(threadID)) { - sp->bestValue = value; - if(value > sp->alpha) { - sp->alpha = value; - sp_update_pv(sp->parentSstack, ss, sp->ply); - if(value == value_mate_in(sp->ply + 1)) - ss[sp->ply].mateKiller = move; - if(value >= sp->beta) { - for(int i = 0; i < ActiveThreads; i++) - if(i != threadID && (i == sp->master || sp->slaves[i])) - Threads[i].stop = true; - sp->finished = true; - } + if (value > sp->bestValue && !thread_should_stop(threadID)) + { + sp->bestValue = value; + if (value > sp->alpha) + { + sp->alpha = value; + sp_update_pv(sp->parentSstack, ss, sp->ply); + if (value == value_mate_in(sp->ply + 1)) + ss[sp->ply].mateKiller = move; + + if(value >= sp->beta) + { + for(int i = 0; i < ActiveThreads; i++) + if(i != threadID && (i == sp->master || sp->slaves[i])) + Threads[i].stop = true; + + sp->finished = true; + } } // If we are at ply 1, and we are searching the first root move at // ply 0, set the 'Problem' variable if the score has dropped a lot // (from the computer's point of view) since the previous iteration: - if(Iteration >= 2 && - -value <= ValueByIteration[Iteration-1] - ProblemMargin) - Problem = true; + if (Iteration >= 2 && -value <= ValueByIteration[Iteration-1] - ProblemMargin) + Problem = true; } lock_release(&(sp->lock)); } @@ -1625,10 +1649,10 @@ namespace { // If this is the master thread and we have been asked to stop because of // a beta cutoff higher up in the tree, stop all slave threads: - if(sp->master == threadID && thread_should_stop(threadID)) - for(int i = 0; i < ActiveThreads; i++) - if(sp->slaves[i]) - Threads[i].stop = true; + if (sp->master == threadID && thread_should_stop(threadID)) + for (int i = 0; i < ActiveThreads; i++) + if (sp->slaves[i]) + Threads[i].stop = true; sp->cpus--; sp->slaves[threadID] = 0; @@ -2044,6 +2068,30 @@ namespace { } + // ok_to_history() returns true if a move m can be stored + // in history. Should be a non capturing move. + + bool ok_to_history(const Position& pos, Move m) { + + return pos.square_is_empty(move_to(m)) + && !move_promotion(m) + && !move_is_ep(m); + } + + + // update_history() registers a good move that produced a beta-cutoff + // in history and marks as failures all the other moves of that ply. + + void update_history(const Position& pos, Move m, Depth depth, + Move movesSearched[], int moveCount) { + + H.success(pos.piece_on(move_from(m)), m, depth); + + for (int i = 0; i < moveCount - 1; i++) + if (ok_to_history(pos, movesSearched[i]) && m != movesSearched[i]) + H.failure(pos.piece_on(move_from(movesSearched[i])), movesSearched[i]); + } + // 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. @@ -2087,7 +2135,7 @@ namespace { if(data) { char input[256]; if(fgets(input, 255, stdin) == NULL) - strcpy(input, "quit\n"); + strncpy(input, "quit\n", 5); if(strncmp(input, "quit", 4) == 0) { AbortSearch = true; PonderSearch = false;