X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=bf33a136b6f8364ead77831d46e399ae4c0837f5;hp=a10e1180c344a3af45a23bf293386d27cc48ddbf;hb=b8930d0c267d9d01ea1f854122e663c34bf5fce2;hpb=02420d4670e54f41bce5bc6d53fb437b80f9d534 diff --git a/src/search.cpp b/src/search.cpp index a10e1180..bf33a136 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -155,21 +155,17 @@ void Search::init() { size_t Search::perft(Position& pos, Depth depth) { - // At the last ply just return the number of legal moves (leaf nodes) - if (depth == ONE_PLY) - return MoveList(pos).size(); - StateInfo st; size_t cnt = 0; CheckInfo ci(pos); + const bool leaf = depth == 2 * ONE_PLY; for (MoveList it(pos); *it; ++it) { pos.do_move(*it, st, ci, pos.move_gives_check(*it, ci)); - cnt += perft(pos, depth - ONE_PLY); + cnt += leaf ? MoveList(pos).size() : perft(pos, depth - ONE_PLY); pos.undo_move(*it); } - return cnt; } @@ -495,7 +491,7 @@ namespace { assert(PvNode || (alpha == beta - 1)); assert(depth > DEPTH_ZERO); - Move movesSearched[64]; + Move quietsSearched[64]; StateInfo st; const TTEntry *tte; SplitPoint* splitPoint; @@ -506,11 +502,11 @@ namespace { Value eval, nullValue, futilityValue; bool inCheck, givesCheck, pvMove, singularExtensionNode; bool captureOrPromotion, dangerous, doFullDepthSearch; - int moveCount, playedMoveCount; + int moveCount, quietCount; // Step 1. Initialize node Thread* thisThread = pos.this_thread(); - moveCount = playedMoveCount = 0; + moveCount = quietCount = 0; inCheck = pos.checkers(); if (SpNode) @@ -574,9 +570,9 @@ namespace { && tte && tte->depth() >= depth && ttValue != VALUE_NONE // Only in case of TT access race - && ( PvNode ? tte->type() == BOUND_EXACT - : ttValue >= beta ? (tte->type() & BOUND_LOWER) - : (tte->type() & BOUND_UPPER))) + && ( PvNode ? tte->bound() == BOUND_EXACT + : ttValue >= beta ? (tte->bound() & BOUND_LOWER) + : (tte->bound() & BOUND_UPPER))) { TT.refresh(tte); ss->currentMove = ttMove; // Can be MOVE_NONE @@ -605,8 +601,8 @@ namespace { // Can ttValue be used as a better position evaluation? if (ttValue != VALUE_NONE) - if ( ((tte->type() & BOUND_LOWER) && ttValue > eval) - || ((tte->type() & BOUND_UPPER) && ttValue < eval)) + if ( ((tte->bound() & BOUND_LOWER) && ttValue > eval) + || ((tte->bound() & BOUND_UPPER) && ttValue < eval)) eval = ttValue; } else @@ -618,10 +614,10 @@ namespace { // Update gain for the parent non-capture move given the static position // evaluation before and after the move. - if ( (move = (ss-1)->currentMove) != MOVE_NULL - && (ss-1)->staticEval != VALUE_NONE + if ( !pos.captured_piece_type() && ss->staticEval != VALUE_NONE - && !pos.captured_piece_type() + && (ss-1)->staticEval != VALUE_NONE + && (move = (ss-1)->currentMove) != MOVE_NULL && type_of(move) == NORMAL) { Square to = to_sq(move); @@ -726,7 +722,6 @@ namespace { && depth >= 5 * ONE_PLY && !inCheck && !ss->skipNullMove - && excludedMove == MOVE_NONE && abs(beta) < VALUE_MATE_IN_MAX_PLY) { Value rbeta = beta + 200; @@ -780,7 +775,7 @@ split_point_start: // At split points actual search starts from here && depth >= (PvNode ? 6 * ONE_PLY : 8 * ONE_PLY) && ttMove != MOVE_NONE && !excludedMove // Recursive singular search is not allowed - && (tte->type() & BOUND_LOWER) + && (tte->bound() & BOUND_LOWER) && tte->depth() >= depth - 3 * ONE_PLY; // Step 11. Loop through moves @@ -931,8 +926,8 @@ split_point_start: // At split points actual search starts from here pvMove = PvNode && moveCount == 1; ss->currentMove = move; - if (!SpNode && !captureOrPromotion && playedMoveCount < 64) - movesSearched[playedMoveCount++] = move; + if (!SpNode && !captureOrPromotion && quietCount < 64) + quietsSearched[quietCount++] = move; // Step 14. Make the move pos.do_move(move, st, ci, givesCheck); @@ -1083,43 +1078,37 @@ split_point_start: // At split points actual search starts from here // If we have pruned all the moves without searching return a fail-low score if (bestValue == -VALUE_INFINITE) - { - assert(!playedMoveCount); - bestValue = alpha; - } - if (bestValue >= beta) // Failed high + TT.store(posKey, value_to_tt(bestValue, ss->ply), + bestValue >= beta ? BOUND_LOWER : + PvNode && bestMove ? BOUND_EXACT : BOUND_UPPER, + depth, bestMove, ss->staticEval, ss->evalMargin); + + // Quiet best move: update killers, history and countermoves + if ( bestValue >= beta + && !pos.is_capture_or_promotion(bestMove) + && !inCheck) { - TT.store(posKey, value_to_tt(bestValue, ss->ply), BOUND_LOWER, depth, - bestMove, ss->staticEval, ss->evalMargin); - - if (!pos.is_capture_or_promotion(bestMove) && !inCheck) + if (ss->killers[0] != bestMove) { - if (bestMove != ss->killers[0]) - { - ss->killers[1] = ss->killers[0]; - ss->killers[0] = bestMove; - } - - // Increase history value of the cut-off move - Value bonus = Value(int(depth) * int(depth)); - History.update(pos.piece_moved(bestMove), to_sq(bestMove), bonus); - if (is_ok((ss-1)->currentMove)) - Countermoves.update(pos.piece_on(prevMoveSq), prevMoveSq, bestMove); + ss->killers[1] = ss->killers[0]; + ss->killers[0] = bestMove; + } - // Decrease history of all the other played non-capture moves - for (int i = 0; i < playedMoveCount - 1; i++) - { - Move m = movesSearched[i]; - History.update(pos.piece_moved(m), to_sq(m), -bonus); - } + // Increase history value of the cut-off move and decrease all the other + // played non-capture moves. + Value bonus = Value(int(depth) * int(depth)); + History.update(pos.piece_moved(bestMove), to_sq(bestMove), bonus); + for (int i = 0; i < quietCount - 1; i++) + { + Move m = quietsSearched[i]; + History.update(pos.piece_moved(m), to_sq(m), -bonus); } + + if (is_ok((ss-1)->currentMove)) + Countermoves.update(pos.piece_on(prevMoveSq), prevMoveSq, bestMove); } - else // Failed low or PV search - TT.store(posKey, value_to_tt(bestValue, ss->ply), - PvNode && bestMove != MOVE_NONE ? BOUND_EXACT : BOUND_UPPER, - depth, bestMove, ss->staticEval, ss->evalMargin); assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); @@ -1167,8 +1156,7 @@ split_point_start: // At split points actual search starts from here ttDepth = InCheck || depth >= DEPTH_QS_CHECKS ? DEPTH_QS_CHECKS : DEPTH_QS_NO_CHECKS; - // Transposition table lookup. At PV nodes, we don't use the TT for - // pruning, but only for move ordering. + // Transposition table lookup posKey = pos.key(); tte = TT.probe(posKey); ttMove = tte ? tte->move() : MOVE_NONE; @@ -1177,9 +1165,9 @@ split_point_start: // At split points actual search starts from here if ( tte && tte->depth() >= ttDepth && ttValue != VALUE_NONE // Only in case of TT access race - && ( PvNode ? tte->type() == BOUND_EXACT - : ttValue >= beta ? (tte->type() & BOUND_LOWER) - : (tte->type() & BOUND_UPPER))) + && ( PvNode ? tte->bound() == BOUND_EXACT + : ttValue >= beta ? (tte->bound() & BOUND_LOWER) + : (tte->bound() & BOUND_UPPER))) { ss->currentMove = ttMove; // Can be MOVE_NONE return ttValue; @@ -1589,7 +1577,7 @@ split_point_start: // At split points actual search starts from here void RootMove::extract_pv_from_tt(Position& pos) { StateInfo state[MAX_PLY_PLUS_2], *st = state; - TTEntry* tte; + const TTEntry* tte; int ply = 0; Move m = pv[0]; @@ -1622,7 +1610,7 @@ void RootMove::extract_pv_from_tt(Position& pos) { void RootMove::insert_pv_in_tt(Position& pos) { StateInfo state[MAX_PLY_PLUS_2], *st = state; - TTEntry* tte; + const TTEntry* tte; int ply = 0; do {