Previous Next
An alpha-beta tree consists for the largest part of refutation trees. In such a refutation tree, one side proves that the other cannot get even (i.e. will fail low in the root of this refutation tree) no matter what he tries. To do this, the refuting side only has to play a single move in each position (i.e. a cut-move) to show he can refute the previous move of his opponent. The opponent, however, desperately tries anything. So all-nodes and cut-nodes alternate along the branches of such a refutation tree.
The refutation tree does not affect the score, and in that sense you might say it was searched in vain. But of course the usefulness of a search can only be judged on a statistical basis, you do it because there might be something there, despite the fact that there is no guarantee that there was. Sometimes during the building of a refutation tree you stumble on something winning for the side that did not have the upper hand so far. In that case the refuting side has to work harder, and start trying to find alternatives for its cut-move (which now failed low), to show he can avoid the discovered trouble. If he cannot, in any of his moves leading to the trouble, the roles reverse and the tree is no longer a refutation tree, but might become the new PV.
The refutation trees are thus searched in the hope to discover a better alternative to the PV for the side that deviated. As long as he has not found it, though, all nodes where he is to move are all-nodes. Now in such all-nodes even the most ridiculous moves are tried. As every move fails low in such an all-node, the score cannot be used to distingush attempts with merit from mere garbage: fail-low scores are merely upper bounds, and the upper bounds might not be too strict. The major fraction of the moves, however, only makes matters worse for the side that was already behind. They withdraw pieces from good places, sacrifice them with no compensation, do not cooperate well with earlier moves, etc. The chances that you will still discover a winning position after such a sequence of moves get progressively lower as you do more of them.
The idea of late-move reductions is now to let the search of garbage moves lag a little behind (in depth) with respect to that of useful moves that merely happened not to lead anywhere yet, but at least make sense. This is not done by hard pruning, but by a reduction. This guarantees that, as the nominal depth of the search increases, even the garbage branches continue to deepen, albeit more slowly. If, against all expectation, there was something there to be uncovered, it will eventually be found. But in the mean time, the nodes are mainly added to the tree at the unreduced branches, where we supect a lot higher probability to discover a turn-around. (The term 'late-move reduction' originated in the context where you have some initial move ordering that ranks moves by likelyhood to produce something good even before any search is done on them. A late move is then a move late in this ranking, from which you don't expect much.)
As soon as we do discover something, we of course immediately undo the reduction, and search the branch at least as deep as the formerly best line. In that case we wasted some time on deeply searching a line that after all was not best, because the best line started with a number of very unlikely moves. As this should not happen often, on the average, we will save time.
Now distinguishing useless moves from promising moves is an art in itself. In a program as simple as micro-Max, we can't use very advanced criteria for this. Of course we don't want to reduce the move that was best so far. Apart from that, a very simple and obvious criterion is if the move is a capture. Captures, even bad captures that in themselves give away material, have a larger probability to lead to a good position for the capturer. This is because even a bad capture leaves the opponent little choice for his reply. He has to recapture, or he will have lost part or all of his advantage, and then some. So if there is an unexpected positive side effect to the exchange, he has no leeway to avoid it. On the other hand, passive moves will leave him so many options that he can usually steer away from any trouble, even in the unlikely case that after the passive move you could still stir up some. So of all moves that originally looked bad, captures have a higher probability to upgrade their score than non-captures.
Of course there are many other tactical motifs that keep the opponent under pressure. For instance, attacking a higher or insufficiently defended piece. Usually this does not restrict the options of the opponent as much as the need to recapture. Thus, even reducing all low-failing non-captures does less harm than good.
For practical reasons, micro-Max also exempts all Pawn moves from reduction. This because for Pawn moves the best move it not necessarily tried first, but only second. (If it was a double move it is tried after the corresponding single move, which is bad from the viewpoint of move ordering, but an unfortunate necessity in order not to miss e.p. capture on the reply.) In addition this automatically catches all promotions and passer pushes, so it is not entirely bad. The latter have a high probability of collecting a very large reward (promotion!) that comes only deep into the search, and are thus also among the moves that might see a sudden score jump on deeper search. In addition, Pawns do not have very many moves, so this is not very costly.
All other moves are first searched with a reduction of 1 ply. If they do not fail low there, the search is on to something, and they are immediately re-searched at the nominal depth. The reductions are only applied if the remaining search depth is at least 5 ply, meaning that the reply to the move then is either searched to 3 ply (reduced) or 4 ply (non-reduced). Reducing the reply search to below 3 ply does not bring much additional benifit, as truly useless moves are already handsomely refuted by a null-move reply at QS level, on which no further savings are possible. And those few moves that cannot be refuted by a null move, and could thus benefit from further reduction, are exactly the moves that might be good for something.
Previous Next