Dr. Roland Stuckardt

IT-Beratung - Sprachtechnologie - Medienanalyse

Killerzugheuristik

Fischerle verwendet eine Reihe weiterer Standardtechniken zur sog. Suchbeschleunigung, bei denen es im Unterschied zur oben beschriebenen Technik der Zwischenspeicherung von Evaluationsresultaten nicht darum geht, eine Suche a priori qua Rückgriff auf bereits bekannte Bewertungen abzukürzen, sondern vielmehr die Alpha-Beta-Cutoff-Rate dadurch zu beschleunigen, indem „viel versprechende“ Zugkandidaten zuerst exploriert werden. Insofern stehen die in diesem und den nachfolgenden Abschnitten beschriebenen Heuristiken zur Suchbeschleunigung eher auf einer Ebene mit den Ansätzen zur Optimierung der Zugkandidatensortierung.

Konzeptuelle Beschreibung

Die Idee hinter der Killerzug-Heuristik ist elementar, jedoch in der Praxis sehr wirkungsvoll: Züge, die sich bereits in Nachbarknoten derselben Suchtiefe als Cutoff-Verursacher (vulgo: Killer) erwiesen haben, induzieren tendenziell auch Cutoffs im aktuellen Suchknoten – dies deshalb, da sich die Nachbarknoten (meist) nur in einem – dem letzten - durchgeführten Zug unterscheiden, die Wahrscheinlichkeit also erheblich ist, dass die Bedingungen für den Cutoff nach wie vor erfüllt sind. Folglich lautet die Killerzug-Heuristik: Speichere je Ebene der Suche eine begrenzte Zahl von cutoff-induzierenden Zügen; steht nun ein neuer Knoten dieser Ebene zur Suche an, so starten wir die Suche mit der Exploration dieser Killerzüge, insofern diese für die vorliegende Stellung tatsächlich anwendbar sind.

Feinheiten:

  • Wir verwalten die Killerzug-Datenstrukturen bezugnehmend auf den Suchtiefe–Parameter; eine Bezugnahme auf den Suchlevel-Parameter führte zu falschen Ergebnissen, da qua Selektiver Suche fallweise dynamisch auf das Dekrement des Suchlevel-Werts verzichtet wird.
  • Killerzüge beziehen sich ausnahmslos lokal auf den Kontext der gegenwärtig laufenden Suche; die entsprechenden Datenstrukturen werden somit zu Beginn einer jeden Suche reinitialisiert.