I'll analyze the current Stockfish search code to find an opportunity for improvement, following the suggested workflow.
Let me first understand what example number 15 does:
Example 15 targets the full depth search when LMR (Late Move Reductions) is skipped. It adds a reduction for PV nodes in this specific context:
The change adds if (PvNode) r++; which increases the reduction for PV nodes when LMR is skipped. This is counterintuitive at first glance because PV nodes are typically searched more deeply, not less. But the context is when LMR is skipped - meaning this is for moves that would normally get reduced but for some reason aren't (likely because they're promising moves). The patch is saying: "Even though we're not applying LMR to this move (which would normally reduce it), let's still apply a small reduction because it's not the first move."
This seems to be a fine-tuning of the balance between searching the best moves deeply enough while not wasting time on moves that aren't quite as good as the TT move but still get full-depth searches.
Let me look at the corresponding section in the current code to find an opportunity for improvement:
This code is handling the case where LMR is skipped (i.e., we're doing a full-depth search) but it's not the PV node's first move. It increases the reduction if the TT move is not present, and then adjusts the search depth based on how large the expected reduction r is.
Let me analyze this section more deeply to find potential improvements:
- The current code applies a significant reduction (
r += 1139) if there's no TT move. This is because without a good move from the TT, the move ordering is likely worse, so the move is less likely to be good. - Then it adjusts the search depth with
newDepth - (r > 3200) - (r > 4600 && newDepth > 2). This means:- If r > 3200, reduce depth by 1
- If r > 4600 and newDepth > 2, reduce depth by an additional 1 (total 2)
This is interesting because it's applying a depth reduction even in the "full-depth" search case. The rationale is that if the expected reduction r is very high, it means this move is likely not very good, so we can afford to search it slightly less deeply.
Now, let's think about potential improvements:
- The thresholds 3200 and 4600 seem somewhat arbitrary. Maybe they could be made more dynamic based on depth or other factors.
- The current code doesn't differentiate between PV nodes and non-PV nodes in this specific context, except for the condition that brought us here (
!PvNode || moveCount > 1). But there might be opportunities to adjust reductions differently based on node type. - The current code doesn't consider the move's history score or other move-specific information when deciding how much to reduce.
- The condition
newDepth > 2seems reasonable to prevent reducing to zero or negative depth, but maybe it could be more nuanced.
Looking more broadly at the search.cpp file and the provided notes, I notice an important insight from the notes:
"Applying aggressive LMR at very low depths (e.g., starting from depth 2) can be surprisingly effective, potentially leading to deeper selective searches in key lines."
Also:
"LMR is far more effective at cut nodes compared to PV nodes."
This suggests that even for moves that would normally get full-depth searches (because LMR was skipped), we might still want to apply some reduction, especially if we're at low depths.
Let me also consider the context of the code. This is for moves where LMR was skipped, which typically means they're promising moves (like captures, checks, killer moves, etc.). But even among these promising moves, some are more promising than others.
Looking at the code right before this section, I see:
This is the LMR section that handles most moves. The section we're interested in (example 15's target) handles the cases where LMR was skipped - typically for the first few moves that are considered most promising.
Now, let me think about a potential improvement. One idea that comes to mind is to apply a small reduction even for these "full-depth" searches when we're at very low depths. The rationale is that at low depths, the search is very fast, and we can afford to search more moves, but we don't need to search each move as deeply as we would at higher depths.
From the notes:
"Applying aggressive LMR at very low depths (e.g., starting from depth 2) can be surprisingly effective, potentially leading to deeper selective searches in key lines."
So, for low depth positions, even moves that would normally get full-depth searches could be slightly reduced.
Let me look at how depth is handled in the current code. We have:
This reduces depth by 1 if r > 3200, and by an additional 1 if r > 4600 and newDepth > 2.
What if we also reduced depth for very low depths, even if r isn't that high? For example, at depth 1 or 2, we might want to be more aggressive with reductions to search more moves.
However, I need to be careful. At very low depths, reducing depth further might mean going to depth 0, which would trigger quiescence search. This could be good or bad depending on the position.
Let me check the code for when depth <= 0:
So reducing to depth 0 would trigger quiescence search, which is appropriate.
Another idea: the current code applies a large reduction (r += 1139) if there's no TT move. But maybe this reduction should be scaled based on depth. At higher depths, not having a TT move might be more problematic (because move ordering is more critical), while at lower depths it might matter less.
Let me look at how other parts of the code handle depth-dependent reductions. In the LMR section, I see:
Here, reductions are adjusted based on various factors, but not directly based on depth (except through the quietMoveStreak, which relates to depth indirectly).
However, I notice that the LMR formula itself is depth-dependent:
So reductions are scaled by depth.
Let me think about how to apply this insight to the "full-depth" search section. Maybe the reduction when there's no TT move should be scaled by depth. At higher depths, not having a TT move is more problematic (because the search is more sensitive to move ordering), so the reduction should be larger. At lower depths, it matters less.
Currently:
What if we made this depth-dependent? For example:
But MAX_PLY is 245, and depth is typically much smaller. This might not be the right scaling.
Alternatively, we could use the existing reductions array:
But this seems complicated and might not be well-tuned.
Another approach: look at how other depth-dependent reductions are handled. In the LMR section, I see:
This is a small adjustment based on correctionValue.
Maybe a better approach is to apply a small reduction for all moves in this category when depth is low, regardless of other factors. The rationale is that at low depths, we can afford to be more aggressive with search reductions because the search is fast and we want to cover more ground.
Let me check the current behavior at low depths. The condition for this section is:
So for non-PV nodes or for moves after the first in PV nodes.
At low depths (say depth <= 4), maybe we should reduce the search depth by 1 for all these moves, to search more moves but slightly less deeply.
This would be similar to the existing logic:
But instead of depending on r, it would depend on depth.
So something like:
This would reduce depth by 1 for all moves in this category when depth <= 4.
But let's be more precise. The existing code already reduces depth in some cases. We want to be careful not to over-reduce.
Another idea: at very low depths, the difference between a full-depth search and a slightly reduced search is minimal, but searching one more move could be valuable. So for depth <= 2, reduce by 1; for depth <= 4, reduce by 1 only if it's not the first few moves.
Let me look at the code again:
What if we added:
This would reduce depth by 1 for all moves in this category when depth <= 2.
But let's think about the implications. At depth 2, reducing to depth 1 might not be very aggressive. Depth 1 is still a reasonable search depth.
Another approach: make the reduction depend on how promising the move is. The code already has:
This is a large reduction if there's no TT move, indicating the move is less promising. But maybe we could add a smaller reduction based on other factors.
Looking at the surrounding code, I see:
So statScore is already used to adjust reductions. But this is before the LMR section.
For the "full-depth" search section, we could consider using statScore to determine if we should reduce further.
However, this might be redundant with the existing logic.
Let me consider a different angle. The notes mention:
"Applying aggressive LMR at very low depths (e.g., starting from depth 2) can be surprisingly effective, potentially leading to deeper selective searches in key lines."
So maybe for depth <= 4, we should be more aggressive with reductions even for moves that would normally get full-depth searches.
The current code only reduces depth if r > 3200 or r > 4600. But at low depths, even a moderate r might justify a reduction.
So what if we lowered the thresholds for low depths?
For example:
This would make the reductions more aggressive at low depths.
But let's check if this aligns with the notes. The note says "aggressive LMR at very low depths can be surprisingly effective." This patch would make LMR more aggressive at low depths for moves that would normally get full-depth searches.
This seems promising. Let's see if there's precedent for this kind of change.
In example patch number 10, there's a change that adds a condition value >= VALUE_MATED_IN_MAX_PLY to the LMR condition. This is to avoid reducing moves in positions where we're already mated, which makes sense.
But it doesn't directly address our question.
In example patch number 9, there's a change that adds else if (!PvNode && moveCount > 47) r--;. This decreases reduction for late quiet moves in non-PV nodes, which is the opposite of what we're considering.
Let me think more about the rationale for being more aggressive with reductions at low depths.
At low depths, the search is very fast, and the difference between searching to depth 3 vs depth 2 is minimal in terms of time, but it allows us to search one more move. Since we're at low depths, the accuracy of the evaluation is lower anyway, so a small reduction in search depth might not hurt much, but searching more moves could help find a better move.
This aligns with the note about "deeper selective searches in key lines" - by being more aggressive with reductions at low depths, we can search more moves, which might help identify the most promising lines to search more deeply later.
So, lowering the thresholds for reductions at low depths seems reasonable.
Let's formalize this:
Current:
Proposed:
This lowers the thresholds for reductions at low depths (<= 4), making reductions more likely.
But let's check if this is consistent with other parts of the code. In the LMR section, I see:
Here, r is divided by 1024, which scales it down. The thresholds 3200 and 4600 are in the same scale as r.
In the reduction formula:
Here, reductionScale is in units that get divided by 1024 later.
So the thresholds 3200 and 4600 are in the same units as r.
Now, is lowering the thresholds from 3200/4600 to 2000/3500 at low depths reasonable? Let's think about what r represents.
From the notes:
"The reduction variable r is subtracted from the new search depth (newDepth - r), so a larger positive value for the reduction variable r corresponds to a larger (deeper) reduction."
So a larger r means a bigger reduction.
The condition (r > 3200) means "if the expected reduction is more than 3.2 (since r is later divided by 1024)", we reduce depth by 1.
Lowering the threshold to 2000 means we reduce depth by 1 if the expected reduction is more than 2.0.
This seems reasonable for low depths - we're more willing to reduce because the search is fast and we want to search more moves.
Let me check if there are other places in the code that adjust thresholds based on depth.
In the LMR section, I see:
These are absolute additions to r, not scaled by depth.
But in the reduction formula itself:
Here, reductions[d] is an array indexed by depth, so reductions are inherently depth-dependent.
Given this, my proposal to lower the thresholds at low depths seems consistent with the overall approach.
Let me double-check the logic:
- At low depths (<= 4), we lower the thresholds for reductions in the "full-depth" search section.
- This means we're more likely to reduce the search depth for these moves.
- The rationale is that at low depths, the search is fast, and we can afford to search more moves by slightly reducing the depth of each move.
- This aligns with the note about "aggressive LMR at very low depths" being effective.
Another way to look at it: at low depths, the search is less selective, so we want to search more moves but not as deeply for each move. At higher depths, selectivity is more important, so we want to search fewer moves but more deeply.
This patch would make the search more aggressive with reductions at low depths, which should help with time management and potentially find better moves by exploring more options.
Let me check if there are any potential pitfalls:
- Reducing depth too much could cause tactical misses. But at low depths, the search is already shallow, so a small reduction (1 ply) is unlikely to make a big difference.
- The condition
newDepth > 2already prevents reducing to depth <= 2 when applying the second reduction. So we won't go to depth 0 or 1, which might be too shallow. - This only affects moves that would normally get full-depth searches but for some reason LMR was skipped. These are typically promising moves, but even among promising moves, some are more promising than others.
Given these considerations, I think this is a reasonable patch.
Let me write it out:
Current code:
Proposed change:
This introduces two new variables, threshold1 and threshold2, which are set based on depth.
Let me check if this is consistent with the coding style. In the LMR section, I see:
So using intermediate variables for clarity is acceptable.
Another thing to consider: the depth check. Should it be depth <= 4 or depth < 5? They're equivalent, but depth <= 4 is clearer.
Also, are 2000 and 3500 the right values? They're somewhat arbitrary, but they're proportional to the original thresholds (2000/3200 = 0.625, 3500/4600 = 0.76). This seems reasonable.
Let me see if there's a more principled way to set these values. The reductions array might provide guidance, but it's indexed by depth, and we're already using it indirectly through r.
Given that these are tuning parameters, the exact values might need testing, but the concept of lowering the thresholds at low depths seems sound.
One more consideration: the notes mention that patches should "prefer scalers (i.e. patches that scale well in LTC (long time control))."
Does this patch scale well in LTC? At longer time controls, the engine searches to higher depths, so the low-depth cases (<= 4) might be less frequent. However, even at longer time controls, the search still goes through low depths during iterative deepening. So this patch should still have an effect.
Moreover, the patch makes the search more aggressive at low depths, which could help with move ordering and potentially lead to better search trees at higher depths. This could have a positive scaling effect.
Let me check if there's another potential improvement in this area.
Looking at the code again:
This is a large increase to r. But maybe this should also be depth-dependent. At higher depths, not having a TT move is more problematic (because move ordering is more critical), so the penalty should be larger.
So what if we did:
But MAX_PLY is 245, which is much larger than typical depths (which are often < 100). This might make the penalty too small at typical depths.
Alternatively:
This would make the penalty proportional to depth, up to a maximum at depth 60.
But this might be too complex, and the exact scaling would need tuning.
Given the complexity, and since my first proposal seems reasonable, I'll stick with that.
Let me write the final patch.
Current code:
Improved code:
For the branch name, something like "lmr_aggressive_at_low_depths" would be appropriate.
Wait, let me double-check if there's an even better improvement.
Looking at the code again, I notice:
This reduces depth by 1 if r > 3200, and by an additional 1 if r > 4600 and newDepth > 2.
What if, at low depths, we also reduced depth by 1 unconditionally? This would be even more aggressive.
For example:
This would reduce depth by 1 for all moves in this category when depth <= 4, in addition to the other reductions.
But this might be too aggressive. The existing logic already reduces depth in some cases, and adding an unconditional reduction might be excessive.
Given the notes about not wanting to be too aggressive with pruning (which could hurt mate-finding), I think my original proposal is safer.
Another idea: instead of lowering the thresholds, make the reduction amount depth-dependent. For example, at depth <= 2, reduce by 2 if r > 3200, rather than 1.
But this seems more complex and less principled.
I'll stick with my original proposal.
Let me check the exact line numbers to make sure I'm modifying the right part of the code.
In the provided code, the section is:
Yes, that's the correct section.
One last check: the notes mention "Generally avoid changing parameters, since they are already optimized/tuned for long time controls."
I am changing parameters (the thresholds), but I'm doing it in a way that's depth-dependent, which is a common pattern in the code (as seen in the reduction formula). This isn't just arbitrarily changing a constant; it's making the constant adaptive based on search depth, which is a known technique for improving time control scaling.
Moreover, the patch is designed to be more aggressive at low depths, which should help with the early stages of search and potentially improve move ordering for deeper searches.
I think this is a valid improvement.