Heuristics with null movement

For the Software S of failures, the heuristic with null movement is a technique Heuristique used to improve the speed of the algorithm of pruning alpha-beta. Developed by Beal in 1989, then Goetsch and Campbell in 1990, it is Christian Donninger - implied in the project Hydra - which made this technique accessible to the amateurs from Programmation échiquéenne by publishing its comments.

Principle

The technique of pruning alpha-beta is an optimization of the Algorithme MinMax which consists of the identification of “cuts” - are the nodes of the Decision tree which are so strong for the player having the initiative that the best preceding blow of its adversary would have avoided making it possible. Since this type of position is not the result of the best possible blow of the adversary, all the branches of the decision tree which rise from these nodes are ignored. The more the software generates “cuts”, the more research of the best blow is fast. The heuristics with null movement makes it possible to guess the nodes of cut in less attempts, while keeping a reasonable precision.

The principle is based on the fact that the majority of the blows to the failures contribute to improve the position of their player. Thus if the player having the initiative passed his turn (what is contrary with the rules of the game of failures) but kept an enough strong position nevertheless to produce cuts, then the current position would generate certainly also a cut by playing a blow (improvement of the position thanks to this new blow).

By employing this technique, the software starts by making pass the turn of the player having the initiative and then lance a pruning alpha-beta on the resulting positions but on a level surface than without use of the null movement. If this restricted research produces a cut, then it is deduced that a more thorough research - after having played a blow - would have also produced a cut on this branch of the decision tree. Thus the discovery of the cut is faster, accelerating the process of evaluation of the software. If restricted research does not find any cut, then the software proceeds to a research as thorough as possible.

This approach rests on two premises. First is that it is necessary that the disadvantage to pass a turn is stronger than the disadvantage to proceed to a restricted research. Provided that this research is not too surface - in practice this one is less deep of two or three half-blows compared to a traditional research - it is generally the case. Second is that this research will have to sufficient find cuts to justify time spent to use this technique (if not one cumulates two research). In practice it is often the case.

However, certain positions combined with the use of this method can generate big mistakes of tactic. In these positions of zugzwang the player of which it is the turn has only bad blows like choice and, consequently would prefer to pass its turn rather than to play. In these positions the restricted research based on the “loss” of the turn finds a cut whereas traditional research would not have found any. The consequence is that the software evaluates like good a position being able to actually be very bad.

It is thus necessary to restrict the use of this technique of optimization and to draw aside it in the following cases:

the player of which it is the turn to play is in failure
the player of which it is the turn to play does not have more that its king and of the pawns
the player of which it is the turn to play does not have which few parts
the blow preceding in decision tree were also of the heuristic type with null movement

Another heuristic technique to manage the problems of zugzwang is declined by Omid David Tabibi and Nathan Netanyahu. In this method, when the function of restricted research indicates a rupture, rather than to cut the branch to the knot slip, research is continued with a reduced depth.

External bonds

Random links: