Difference between revisions of "Improving"
(→Improving as a Modifier to Search Heuristics: add lmp link) |
(new discoveries :D) |
||
Line 25: | Line 25: | ||
| style="text-align:left;" | Reduce more when not improving / less when improving | | style="text-align:left;" | Reduce more when not improving / less when improving | ||
|} | |} | ||
+ | |||
+ | =Dynamic Improving= | ||
+ | |||
+ | [[Aron Petkovski]] introduced the concept of ''Dynamic Improving''. By using static evaluation differences as a bonus to a improving score, Dynamic Improving allows for more control over improving-based mechanisms. | ||
+ | |||
+ | <pre> | ||
+ | stack->improving_rate = 0.0; | ||
+ | |||
+ | if (!state.InCheck() && !stack->excluded_tt_move) { | ||
+ | |||
+ | ... | ||
+ | |||
+ | Score static_eval_diff = kScoreNone; | ||
+ | double prev_improving_rate = 0.0; | ||
+ | if ((stack - 2)->static_eval != kScoreNone) { | ||
+ | static_eval_diff = stack->static_eval - (stack - 2)->static_eval; | ||
+ | prev_improving_rate = (stack - 2)->improving_rate; | ||
+ | } else if ((stack - 4)->static_eval != kScoreNone) { | ||
+ | static_eval_diff = stack->static_eval - (stack - 4)->static_eval; | ||
+ | prev_improving_rate = (stack - 4)->improving_rate; | ||
+ | } | ||
+ | |||
+ | if (static_eval_diff != kScoreNone) { | ||
+ | stack->improving_rate = prev_improving_rate + (static_eval_diff) / 25.0; | ||
+ | stack->improving_rate = std::clamp(stack->improving_rate, 0.0, 1.0); | ||
+ | } | ||
+ | } else { | ||
+ | stack->static_eval = eval = kScoreNone; | ||
+ | } | ||
+ | </pre> | ||
=Code Example= | =Code Example= | ||
Line 46: | Line 76: | ||
</pre> | </pre> | ||
− | This following code is from [[Integral]]. It demonstrates one | + | This following code is from [[Integral]]. It demonstrates one way to adjust LMP margin with dynamic improving. |
<pre> | <pre> | ||
− | const int lmp_threshold = (3 + depth * depth) / (2 - | + | const int lmp_threshold = static_cast<int>((3.0 + depth * depth) / |
+ | (2.0 - stack->improving_rate)); | ||
if (is_quiet && moves_seen >= lmp_threshold) { | if (is_quiet && moves_seen >= lmp_threshold) { | ||
move_picker.SkipQuiets(); | move_picker.SkipQuiets(); |
Revision as of 00:28, 6 July 2024
Improving is an important modifier for many search heuristics. It is a boolean flag indicating whether the static evaluation of a position has improved from the position two plys ago. Improving can be used to modify the frequency and aggressiveness of certain pruning heuristics.
Improving as a Modifier to Search Heuristics
Heuristic | Modification |
---|---|
Reverse Futility Pruning | Lower pruning margin when improving |
Late Move Pruning | Prune more late quiet moves when not improving |
ProbCut | Lower ProbCut beta threshold when improving |
Null Move Pruning | More NMP when improving. This can be done by allowing pruning even when eval is under beta (and above a certain threshold) when improving. |
Late Move Reductions | Reduce more when not improving / less when improving |
Dynamic Improving
Aron Petkovski introduced the concept of Dynamic Improving. By using static evaluation differences as a bonus to a improving score, Dynamic Improving allows for more control over improving-based mechanisms.
stack->improving_rate = 0.0; if (!state.InCheck() && !stack->excluded_tt_move) { ... Score static_eval_diff = kScoreNone; double prev_improving_rate = 0.0; if ((stack - 2)->static_eval != kScoreNone) { static_eval_diff = stack->static_eval - (stack - 2)->static_eval; prev_improving_rate = (stack - 2)->improving_rate; } else if ((stack - 4)->static_eval != kScoreNone) { static_eval_diff = stack->static_eval - (stack - 4)->static_eval; prev_improving_rate = (stack - 4)->improving_rate; } if (static_eval_diff != kScoreNone) { stack->improving_rate = prev_improving_rate + (static_eval_diff) / 25.0; stack->improving_rate = std::clamp(stack->improving_rate, 0.0, 1.0); } } else { stack->static_eval = eval = kScoreNone; }
Code Example
The following code is taken from Alexandria. Note that in case the position is in check both 2 and 4 plies ago, improving can be set to either true or false. SPRT testing should be done to determine which of the two options is optimal for a given engine.
// Improving is a very important modifier to many heuristics. It checks if our static eval has improved since our last move. // As we don't evaluate in check, we look for the first ply we weren't in check between 2 and 4 plies ago. If we find that // static eval has improved, or that we were in check both 2 and 4 plies ago, we set improving to true. if(inCheck) improving = false; else if ((ss - 2)->staticEval != SCORE_NONE) { improving = ss->staticEval > (ss - 2)->staticEval; } else if ((ss - 4)->staticEval != SCORE_NONE) { improving = ss->staticEval > (ss - 4)->staticEval; } else improving = true;
This following code is from Integral. It demonstrates one way to adjust LMP margin with dynamic improving.
const int lmp_threshold = static_cast<int>((3.0 + depth * depth) / (2.0 - stack->improving_rate)); if (is_quiet && moves_seen >= lmp_threshold) { move_picker.SkipQuiets(); continue; }