Zugsortierung

Die Zugsortierung verändert die Reihenfolge, in der eine Schachengine, also ein Programm zur Stellungsanalyse, die legalen Möglichkeiten untersucht. Sie entfernt einen Zug nicht bloß deshalb, weil er vorher schwach aussieht. Stattdessen versucht sie, jene Kandidaten an den Anfang zu stellen, die wahrscheinlich stark sind, eine schnelle Widerlegung ermöglichen oder nützliche Informationen liefern.

Die Reihenfolge ist wichtig, weil viele Suchen Alpha-Beta-Pruning verwenden, ein Verfahren, das die Untersuchung eines Zweigs beendet, sobald bewiesen ist, dass er die aktuelle Entscheidung nicht verbessern kann. Erscheint ein ausgezeichneter Zug früh, setzt er eine anspruchsvolle Referenz, und viele schlechtere Antworten lassen sich mit wenig Aufwand verwerfen. Erscheint derselbe Zug zuletzt, hat die Engine möglicherweise bereits Zeit für Zweige aufgewendet, die sich später als bedeutungslos erweisen.

Häufige Signale für die Sortierung

• Die beste Variante aus einer früheren Suche, besonders während der iterativen Vertiefung.
• Ein gespeicherter Zug, der gefunden wird, wenn die Engine erkennt, dass sie dieselbe Stellung bereits untersucht hat.
• Schlagzüge, die günstig erscheinen und manchmal mit einer schnellen Schätzung des Materialabtauschs gefiltert werden.
• Ruhige Züge, also Züge ohne unmittelbaren Schlagzug oder Schachgebot, die nach internen Aufzeichnungen früherer Ergebnisse in ähnlichen Stellungen bereits Suchabbrüche verursacht haben.

Bei einer vollständigen Suche mit fester Tiefe sollte eine andere Reihenfolge zum selben Endergebnis führen. Drastisch verändern kann sich jedoch der Arbeitsaufwand, der dafür nötig ist. Techniken wie die Hauptvariantensuche hängen noch stärker davon ab, früh einen guten Kandidaten zu finden.