Zero move search

from Wikipedia, the free encyclopedia

With zero-train-search ( null move pruning ) is called a forward Pruningtechnik in game tree search method for two-person zero-sum games with perfect information .

Especially in chess programs this has zero move pruning proven. This technique is required to accelerate the determination of the strength of possible moves or the course of the game by excluding moves which are determined as too weak by the method described below from a further calculation.

Based on the assumption that the right to move is an advantage, nullmove pruning in the tree search (further tracking of possible positions resulting from a move) enables one side to make two moves. If the advantage achieved is not great enough, the first of the two moves was probably already inferior, and the branch of the game tree (all possible game processes that can result from the current position) does not need to be examined further, it will cut off. In this way, inferior variants can be identified quickly and easily and the time available can be used to analyze more important variants.

In order to reduce the overall search effort, the tree search with which the zero move is evaluated must be carried out with a lower search depth than the search for evaluating normal moves. A reduction of the search depth by two half strokes has proven to be advantageous. Some programs also work with a reduction of three half-moves, which causes a stronger pruning, but is tactically a bit more vulnerable, since promising moves can also be sorted out.

The normal null move pruning fails in forced pulling positions because the premise is not fulfilled here . A tactically disadvantageous move due to the forced move may be necessary. Since forced moves are relatively rare in chess (most likely in certain endgame situations), the error rate is rather low. Some chess programmers simply switch off Nullmove Pruning in the endgame, as there are only a few branches of the tree left at the end and these can be forced positions.

In games like checkers (English. Checkers ) are Zugzwangstellungen the norm, which is why this technique is not applied in such games.

An improved technique is called Verified Nullmove Pruning and bypasses the problems in forced pull positions.

swell

  1. ↑ Omid David Tabibi and Nathan S. Netanyahu (2002), Verified Null-Move Pruning

Web links