Null-move heuristic
With zero - train search ( null move pruning ) refers to a forward Pruningtechnik in game tree search method for two-person zero-sum games with perfect information.
Especially in chess programs, the null move pruning has been proven. This technique is needed to accelerate the determination of the skill level of possible moves and game histories by trains, which are determined by method described below to be too weak to be excluded from further calculation.
Starting from the assumption that the train right constitutes an advantage is the zero move pruning in the tree search ( follow-up of position possibilities arising from a train ) allows one side to run two trains. Where the benefit is thereby achieved is not big enough, so it was probably the first of the two trains inferior, and the resulting branch of the game tree ( all possible game histories, which may arise from the current position) need not be further examined, it is cut off. This allows low-grade variants are well recognized and quickly and be used for the analysis of more important variants, the time available.
In order to reduce the total search effort, has the tree search at which the train is zero rated, be carried out with less depth of search, as the search for the assessment of normal trains. A reduction of the search depth to two half- trains has been found to be advantageous. Some programs also work with a reduction by three half-moves, causing a stronger pruning, but tactically is somewhat more susceptible, since promising traits can be sorted out with.
The normal null move pruning fails in Zugzwangstellungen, since the premise is not fulfilled. It may require a tactically disadvantageous train through the tight spot. Since Zugzwangstellungen chess relatively infrequent ( most likely in certain endgame situations), the error rate is rather low. Some chess programmers turn the null move pruning in the final from quite simply, because just at the end only a few branches of the tree are left and these can be rather Zugzwangsstellungen.
In games like checkers (English checkers ) are Zugzwangstellungen the norm, so for those games, this technique is not applied.
An improved technique is called Verified null move pruning and bypasses the problems in Zugzwangstellungen.