In Computerschachprogrammen ist die heuristische ungültige Bewegung eine heuristische Technik, die verwendet ist, um die Geschwindigkeit des Beschneidungsalgorithmus des Alpha-Betas zu erhöhen.

Grundprinzip

Beschneidung des Alpha-Betas beschleunigt den minimax Algorithmus, indem sie Abkürzungen identifiziert wird, Punkte im Spielbaum, wo die aktuelle Position für die Seite so gut ist, um sich zu bewegen, die am besten durch die andere Seite spielen, hätten es vermieden. Seitdem sich solche Positionen aus bestem Spiel nicht ergeben haben könnten, können sie und alle Zweige des Spielbaums, der von ihnen stammt, ignoriert werden. Je schneller das Programm Abkürzungen erzeugt, desto schneller die Suche läuft. Die heuristische ungültige Bewegung wird entworfen, um Abkürzungen mit weniger Anstrengung zu erraten, als es sonst erforderlich wäre, während es ein angemessenes Niveau der Genauigkeit behält.

Die heuristische ungültige Bewegung basiert auf der Tatsache, dass angemessenste Schachbewegungen die Position für die Seite verbessern, die sie gespielt hat. Also, wenn der Spieler, dessen Umdrehung es bewegen soll, das Recht verwirken, eine "ungültige Bewegung" - eine ungesetzliche Handlung im Schach zu bewegen (oder zu machen), und noch eine Position haben kann, die stark genug ist, um eine Abkürzung zu erzeugen, dann würde die aktuelle Position fast sicher eine Abkürzung erzeugen, wenn sich der aktuelle Spieler wirklich bewegen würde.

Durchführung

In der Beschäftigung der heuristischen ungültigen Bewegung verwirkt das Computerprogramm zuerst die Umdrehung der Seite, deren Umdrehung es bewegen soll, und dann eine Suche des Alpha-Betas auf der resultierenden Position zu einer seichteren Tiefe durchführt, als es gesucht hätte, hatte die aktuelle Position es nicht verwendet die ungültige heuristische Bewegung. Wenn diese seichte Suche eine Abkürzung erzeugt, nimmt sie an, dass die Suche der vollen Tiefe ohne eine verwirkte Umdrehung auch eine Abkürzung erzeugt hätte. Weil eine seichte Suche schneller ist als tiefere Suche, wird die Abkürzung schneller gefunden, das Computerschachprogramm beschleunigend. Wenn die seichte Suche scheitert, eine Abkürzung zu erzeugen, dann muss das Programm die volle Tiefe suchen lassen.

Diese Annäherung macht zwei Annahmen. Erstens nimmt es an, dass der Nachteil, jemandes Umdrehung zu verwirken, größer ist als der Nachteil, eine seichtere Suche durchzuführen. Vorausgesetzt dass die seichtere Suche nicht zu viel seichter ist (in der praktischen Durchführung, ist die Suche der ungültigen Bewegung gewöhnlich 2 oder 3 seichtere Falten, als die volle Suche gewesen wäre), ist das gewöhnlich wahr. Zweitens nimmt es an, dass die Suche der ungültigen Bewegung eine Abkürzung oft genug erzeugen wird, um die verbrachte Zeit zu rechtfertigen, Suchen der ungültigen Bewegung statt voller Suchen durchführend. In der Praxis ist das auch gewöhnlich wahr.

Probleme mit der heuristischen ungültigen Bewegung

Es, gibt jedoch, eine Klasse von Schachpositionen, wo die Beschäftigung der heuristischen ungültigen Bewegung auf strenge taktische Fehler hinauslaufen kann. In diesen Zugzwang (Deutsch für "erzwungenen, um sich zu bewegen",) Positionen hat der Spieler, dessen Umdrehung es bewegen soll, nur schlechte Bewegungen als ihre gesetzlichen Wahlen, und würde wirklich so aus, wenn erlaubt, sein besser, das Recht zu verwirken, sich zu bewegen. In diesen Positionen kann die heuristische ungültige Bewegung eine Abkürzung erzeugen, wo eine volle Suche ein nicht gefunden hätte, das Programm veranlassend, anzunehmen, dass die Position sehr gut für eine Seite ist, für die es tatsächlich sehr schlecht sein kann.

Zu vermeiden, die ungültige Bewegung zu verwenden, die in Zugzwang-Positionen, die meisten schachspielenden Programme heuristisch ist, die die ungültige Bewegung heuristische gestellte Beschränkungen seines Gebrauches verwenden. Solche Beschränkungen schließen häufig das nicht Verwenden der heuristischen ungültigen Bewegung wenn ein

• die Seite, um sich zu bewegen, ist unter Kontrolle
• die Seite, um sich zu bewegen, hat nur seinen König und Pfänder, die bleiben
• die Seite, um sich zu bewegen, hat eine kleine Zahl von Stücken, die bleiben
• die vorherige Bewegung in der Suche war auch eine ungültige Bewegung.

Nachgeprüfte Beschneidung der ungültigen Bewegung

Ein anderer, der heuristisch ist, um sich mit dem Zugzwang-Problem zu befassen, ist Omid David und die nachgeprüfte ungültige Bewegung von Nathan Netanyahu, die http://www.omiddavid.com/pubs/vrfd_null.pdf beschneidet. In der nachgeprüften Beschneidung der ungültigen Bewegung, wann auch immer die seichte Suche der ungültigen Bewegung das Scheitern hoch anzeigt, anstatt die Suche vom aktuellen Knoten abzuschneiden, wird die Suche mit der reduzierten Tiefe fortgesetzt.

Siehe auch

• Ungültige Bewegung
• Zugzwang