Mit Nullmove bezeichnet man eine "Forward Pruningtechnik" in Spielbaumsuchverfahren für "Zwei Personen Nullsummenspielen mit vollständiger Information".
Speziell in Schachprogrammen hat sich das Nullmove Pruning bewährt. Diese Technik wird benötigt, um die Ermittlung der Spielstärke möglicher Züge bzw. Spielverläufe zu beschleunigen, indem Züge, welche durch unten beschriebenes Verfahren als zu schwach ermittelt werden von einer weiteren Berechnung ausgeschlossen werden. (siehe auch ELO-Zahl)
Ausgehend von der Annahme, das das Zugrecht einen Vorteil darstellt, wird beim Nullmovepruning in der Baumsuche (Weiterverfolgung von Stellungsmöglichkeiten, die sich aus einem Zug ergeben) einer Seite ermöglicht zwei Züge auszuführen. Ist der dadurch erzielte Vorteil nicht groß genug, so war wahrscheinlich schon der erste der beiden Züge minderwertig und der daraus resultierende Ast des Spielbaums (sämtliche mögliche Spielverläufe, die sich aus der aktuellen Stellung ergeben können) braucht nicht weiter untersucht zu werden. Er wird einfach abgeschnitten, also nicht weiter untersucht. Hierdurch können minderwertige Varianten gut und schnell erkannt werden und die zur Verfügung stehende Zeit für die Analyse wichtigerer Varianten genutzt werden.
Das normale Nullmove Pruning versagt in Zugzwangstellungen, da hier die Prämisse nicht erfüllt wird. Es kann ein taktisch nachteiliger Zug durch den Zugzwang erforderlich sein.
Da Zugzwangstellungen beim Schach relativ selten vorkommen (am ehesten in bestimmten Endspielsituationen), ist die Fehlerhäufigkeit eher gering. Einige Schachprogrammierer schalten das Nullmove Pruning im Endspiel auch einfach ganz ab, da gerade am Ende nur noch wenige Zweige des Baumes übrig sind und diese eher Zugzwangsstellungen sein können.
Beim Nullmove Pruning wird mit verschiedenen Reduktionsfaktoren gearbeitet. Als gut hat sich ein Wert von R=2 herausgestellt. Manche Programme arbeiten auch mit R=3, was ein stärkeres Pruning bewirkt, aber taktisch etwas anfälliger ist, da auch vielversprechende Züge mit aussortiert werden können.
Bei Spielen wie Dame (Checkers) gehören Zugzwangstellungen zum Normalfall, so dass bei solchen Spielen diese Technik nicht angewandt wird.
Eine verbesserte Technik nennt sich "Verified Nullmove Pruning" und umgeht die Probleme in Zugzwangstellungen.
|
