summaryrefslogtreecommitdiff
path: root/src/search.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/search.c')
-rwxr-xr-xsrc/search.c154
1 files changed, 102 insertions, 52 deletions
diff --git a/src/search.c b/src/search.c
index 4ea09b0..ce867b6 100755
--- a/src/search.c
+++ b/src/search.c
@@ -199,6 +199,7 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx,
}
DTEnterNode(ctx, uDepth, FALSE, iAlpha, iBeta);
iInitialAlpha = iAlpha;
+ pi->fPvNode = (iBeta != iAlpha + 1);
ASSERT((IS_CHECKING_MOVE(mvLast) && (TRUE == pi->fInCheck)) ||
(!IS_CHECKING_MOVE(mvLast) && (FALSE == pi->fInCheck)));
@@ -328,7 +329,7 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx,
goto end;
}
}
-
+
// Maybe increment positional extension level b/c of nullmove search
// or hash table results.
if (fThreat)
@@ -336,7 +337,7 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx,
iOrigExtend += THREE_QUARTERS_PLY;
INC(ctx->sCounters.extension.uMateThreat);
}
-
+
// Main search loop, try moves under this position. Before we get
// into the move loop, save the extensions merited by this
// position in the tree (pre-move) and the original search flags.
@@ -441,7 +442,7 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx,
(ctx->uPly >= 2) &&
(iOrigExtend == 0) &&
(ctx->sPlyInfo[ctx->uPly - 2].iExtensionAmount <= 0) &&
- (ValueOfMaterialInTroubleDespiteMove(pos, pos->uToMove)))
+ (ValueOfMaterialInTroubleDespiteMove(ctx, pos->uToMove)))
{
uFutilityMargin = (iAlpha - iRoughEval) / 2;
ASSERT(uFutilityMargin);
@@ -451,7 +452,7 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx,
// fall through
case TRY_GENERATED_MOVES:
- if (x < ctx->sMoveStack.uEnd[ctx->uPly])
+ if (x < ctx->sMoveStack.uEnd[ctx->uPly])
{
ASSERT(x >= ctx->sMoveStack.uBegin[ctx->uPly]);
if (uLegalMoves < SEARCH_SORT_LIMIT(ctx->uPly))
@@ -480,9 +481,12 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx,
ASSERT(SanityCheckMove(pos, mv));
#ifdef MP
- // Can we search the remaining moves in parallel?
- ASSERT((uDepth / ONE_PLY - 1) >= 0);
- ASSERT((uDepth / ONE_PLY - 1) < MAX_PLY_PER_SEARCH);
+ // Can we search the remaining moves in parallel? Note:
+ // uDepth can legitimately be < ONE_PLY here (fractional
+ // depth from a reduction) -- uDepth/ONE_PLY - 1 would
+ // underflow (ULONG) in that case, which is exactly why the
+ // uDepth >= ONE_PLY check below short-circuits before the
+ // g_fCanSplit[] indexing ever evaluates it.
if (((uLegalMoves >= 2)) &&
(0 != g_uNumHelpersAvailable) &&
(0 == uFutilityMargin) &&
@@ -568,20 +572,24 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx,
MAX(MAX_EXTEND_PER_LINE - pf->iCumulativeExtend, 0));
}
- // Decide whether or not to do history pruning
- if (TRUE == WeShouldDoHistoryPruning(iRoughEval,
- iAlpha,
- iBeta,
- ctx,
- uDepth,
- uLegalMoves,
- mv,
- (x - 1), // Note: x==0 if hash
- iExtend))
+ // Decide how much (if any) to reduce this move's depth --
+ // graded LMR.
{
- ASSERT(iExtend == 0);
- iExtend = -ONE_PLY;
- pi->iExtensionAmount = -ONE_PLY;
+ INT iLMR = GetLMRReduction(iRoughEval,
+ iAlpha,
+ iBeta,
+ ctx,
+ uDepth,
+ uLegalMoves,
+ mv,
+ (x - 1), // Note: x==0 if hash
+ iExtend);
+ if (iLMR < 0)
+ {
+ ASSERT(iExtend == 0);
+ iExtend = iLMR;
+ pi->iExtensionAmount = iLMR;
+ }
}
// Maybe even "futility prune" this move away.
@@ -623,7 +631,7 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx,
// Research deeper if history pruning failed
if ((iExtend < 0) && (iScore >= iBeta))
{
- uNextDepth += ONE_PLY;
+ uNextDepth -= iExtend; // undo the full reduction, whatever its magnitude
pi->iExtensionAmount = 0;
iScore = -Search(ctx, -iBeta, -iAlpha, uNextDepth);
}
@@ -651,12 +659,31 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx,
{
// Update history and killers list and store in
// the transposition table.
- UpdateDynamicMoveOrdering(ctx,
- uDepth,
- mv,
- iScore,
+ UpdateDynamicMoveOrdering(ctx,
+ uDepth,
+ mv,
+ iScore,
x);
StoreLowerBound(mv, pos, iScore, uDepth, fThreat);
+
+ // A fail-high capturing a non-pawn piece is
+ // search-proven evidence that piece was en
+ // prise -- but the victim belongs to the
+ // *other* side, i.e. whoever is to move at
+ // ctx->uPly - 1 (ply parity), not here --
+ // "despite the move you're about to make,
+ // this piece stays in trouble." Skip near
+ // mate: a fail-high there means the whole
+ // subtree is winning regardless of this
+ // particular piece, not that it was
+ // specifically hanging.
+ if (mv.pCaptured && !IS_PAWN(mv.pCaptured) &&
+ (iBeta < +NMATE))
+ {
+ ASSERT(ctx->uPly > 0);
+ RecordEnprisePieceAtPly(ctx, ctx->uPly - 1,
+ mv.cTo);
+ }
KEEP_TRACK_OF_FIRST_MOVE_FHs(uLegalMoves == 1);
ASSERT(SanityCheckMoves(ctx, x, VERIFY_BEFORE));
goto end;
@@ -1112,33 +1139,38 @@ QSearch(IN SEARCHER_THREAD_CONTEXT *ctx,
}
ASSERT(!InCheck(pos, pos->uToMove));
- // If we get here then side on move is not in check and this
- // position looks ok enough to allow him the option to stand pat
- // -or- we missed when we probed the dangerhash. Also remember
- // that this side has had the option to stand pat when searching
- // below this point. This also means the other side is not
- // allowed to generate checks on this side because even if it
- // discovers a mate, there's no force since a stand pat
- // opportunity exists right here.
- uLegalMoves = 0;
iEval = iBestScore = Eval(ctx, iAlpha, iBeta, &iPositional);
- if (iBestScore > iAlpha)
+
+ // If that Eval (above) was full (i.e. not lazy) it may have set
+ // en prise and trapped piece indicators. Likewise, other nodes
+ // at this depth may have set en prise piece hints. If these are
+ // set and valid, it means this is not a "quiet" position. If the
+ // side on the move has not been able to stand pat yet, don't let
+ // them now -- force them to play a move and recurse.
+ if (0 != ValueOfMaterialInTroubleDespiteMove(ctx, pos->uToMove))
+ {
+ iBestScore = iAlpha;
+ }
+ else
{
- iAlpha = iBestScore;
- ASSERT(ctx->sPlyInfo[ctx->uPly].PV[ctx->uPly].uMove == 0);
- ASSERT(pi->mvBest.uMove == 0);
- if (iBestScore >= iBeta)
+ if (iBestScore > iAlpha)
{
- goto end;
+ iAlpha = iBestScore;
+ ASSERT(ctx->sPlyInfo[ctx->uPly].PV[ctx->uPly].uMove == 0);
+ ASSERT(pi->mvBest.uMove == 0);
+ if (iBestScore >= iBeta)
+ {
+ goto end;
+ }
}
+ ctx->sSearchFlags.fCouldStandPat[pos->uToMove] = TRUE;
}
- ctx->sSearchFlags.fCouldStandPat[pos->uToMove] = TRUE;
- // He did not choose to stand pat here; we will be generating
- // moves and searching recursively. Compute a futility score:
- // any move less than this will not be searched because it will
- // just cause a lazy eval answer; is has no shot to bring the
- // score close enough to alpha to even consider.
+ // He did not choose to stand pat here or we did not allow it. We
+ // will be generating moves and searching recursively. Compute a
+ // futility score: any move less than this will not be searched
+ // because it will just cause a lazy eval answer; is has no shot
+ // to bring the score close enough to alpha to even consider.
//
// iEval + move_value + margin < alpha
// move_value < alpha - margin - iEval
@@ -1150,13 +1182,18 @@ QSearch(IN SEARCHER_THREAD_CONTEXT *ctx,
}
// We know we are not in check. If we are early in the qsearch,
- // and the other side has not yet been able to stand pat, and we
- // have material, generate checks here too.
- fIncludeChecks =
- ((pf->uQsearchDepth < pf->uQsearchCheckDepth) &&
- (pf->fCouldStandPat[FLIP(pos->uToMove)] == FALSE) &&
- (pos->uNonPawnMaterial[pos->uToMove] > (VALUE_KING + VALUE_BISHOP)));
+ // and the other side has not yet been able to stand pat yet, and
+ // we have material OR we have hanging pieces, generate checks
+ // here too. Checks are a "good way" to escape from "trouble".
+ fIncludeChecks = ((pf->uQsearchDepth < pf->uQsearchCheckDepth) &&
+ (((pf->fCouldStandPat[FLIP(pos->uToMove)] == FALSE) &&
+ (pos->uNonPawnMaterial[pos->uToMove] >
+ (VALUE_KING + VALUE_BISHOP))) ||
+ (FALSE == ctx->sSearchFlags.fCouldStandPat[pos->uToMove])));
+
GenerateMoves(ctx, NULLMOVE, _WhatToGen[fIncludeChecks]);
+
+ uLegalMoves = 0;
for (x = ctx->sMoveStack.uBegin[ctx->uPly];
x < ctx->sMoveStack.uEnd[ctx->uPly];
x++)
@@ -1217,6 +1254,19 @@ QSearch(IN SEARCHER_THREAD_CONTEXT *ctx,
{
if (iScore >= iBeta)
{
+ // A fail-high capturing a non-pawn piece is
+ // search-proven evidence that piece was en
+ // prise -- victim belongs to the mover at
+ // ctx->uPly - 1, not here (see the same
+ // reasoning in the main Search() fail-high
+ // branch). Skip near mate.
+ if (mv.pCaptured && !IS_PAWN(mv.pCaptured) &&
+ (iBeta < +NMATE))
+ {
+ ASSERT(ctx->uPly > 0);
+ RecordEnprisePieceAtPly(ctx, ctx->uPly - 1,
+ mv.cTo);
+ }
KEEP_TRACK_OF_FIRST_MOVE_FHs(uLegalMoves == 1);
ASSERT(iBestScore > -NMATE);
ASSERT(SanityCheckMoves(ctx, x, VERIFY_BEFORE));
generated by cgit v1.3 (git 2.53.0) at 2026-09-10 00:03:48 +0000