The problem that you describe does not happen with top programs because they do not search for an exact score in order to get a fail high.hgm wrote:This behavior is a consequence of the desire to search every branch to the same effective depth (equating the "effective depth" of a null move to R+1 ply). From a chessic perspective this is a non-sensical desire: after having concluded that promotion is unavoidable, and takes 35 moves against best defense, it is not satisfied (and thus will not give the 35-ply score) before it has searched all other branches to that depth as well. Also those branches that, against very stupid defense, already promoted after 15 ply. Before those braches were null-move pruned to almost nothing, because there was no need to move the Queen: it could just be sitting there on the promotion square while you null-moved, until you finally received its big fat score in the material evaluation of the much-reduced end leaf, which would make these null-moves fail high.
But when merely having a Queen is no longer guarantee for fail high, because the PV now has a Queen too, the Queen has suddenly to take offensive action in those sub-trees, exploding them completely. It will be making an attempt to figure out how much damage that Queen can do in the remaining 20 ply, of which it had no idea before. (So this is a completely uninformed search.)
Humans don't think that way; they think more in a DTC metric. First you try to delay the Queening as much as possible. When you finally proved that Queening is unavoidable, you start analyzing the next phase of the game, where you start counting the depth from the point where you promoted. Allowing an early promotion might be a much beter defense; before you discovered that promotion was unavoidable the tree will contain many horizon moves sacrificing material or position just to delay promotion. So it makes sense to compare early promotions to delayed promotions, with the same number of ply after the promotion. If you don't, the late promotion is likely to (unjustly) look better for many more plies, because there is less depth to see the sme (or worse) disasters. Basically you are just cultivating the horizon effect. To make a sensible choice between the promotion positions, you need to compare their search scores at the same remaining depth.
This is not impossible to implement in an engine: one could propagate the "depth after resolution", defined as depth searched past the point where the static eval approximated the search score, back towards the root with the PV score. In a sense it would be a tag to the window limit, and should also be propagated upward through the tree, together with this window limit. As long as the static eval is very far from the window limit, depth for daughter nodes would be decreased as usual. But as soon as the static eval reaches the window limit again (e.g. because you are in a branch that promoted early), so that this new branch could become PV, the remaining depth should be reduced to the depth of resolution of the window limit we are comparing it against.
Another, more general method, which also ameliorates problems like this, is node-balancing: use fractional ply, and could each ply made from a given position for log(nr_of_moves). This would count plies after promotion more heavily than plies before promotion, reducing the search work in the early-promotion branches somewhat. This method would also help in the opposite situation, where you trade your last piece. The plies in the resulting Pawn ending would be counted for much less, increasing the true search depth there.
Branches that, against very stupid defense, already promoted after 15 ply are pruned to almost nothing when the score is not winning score and the score can be winning score only after fail high that means after finding the best move.
The program may be slow in finding an exact score for the best move but finding the best move should not be a problem.
I guess that the main problem is simply that the program needs to search many lines to fail high and not the problem of searching positions with big advantage.
Uri
