Improving
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; }