Dr. Roland Stuckardt

IT-Beratung - Sprachtechnologie - Medienanalyse

History-Heuristik

Auf derselben Ebene wie Killerzug- und Transpositionstafel-Heuristiken angesiedelt. Die Präferierung von Zügen soll hier anhand von Kriterien erfolgen, die an der globalen Nützlichkeit von Zügen festmachen. Anders gesagt: Wir schauen auf die globale Statistik innerhalb der jeweils laufenden Partie und nicht alleine auf die suchlokale Nützlichkeit als Cutoff-Zug, wie dies die Killerzüge tun. Deshalb die Bezeichnung History-Heuristik.

Konzeptuelle Beschreibung

In der Literatur werden verschiedene Erfolg versprechende komplexere statistische Verfahren zur Implementierung einer History-Heuristik beschrieben. Im Rahmen der gegenwärtigen Version von Fischerle wird hingegen nur ein vergleichsweise elementares Verfahren verwendet. Wie die Killerzug-Heuristik basiert es auf einer Hashtafel, jedoch nur einer globalen, partie- anstatt von suchbezogenen, die weder zwischen Suchebenen noch der am Zug befindlichen Partei unterscheidet.

Überall da, wo ein Zug als Cutoff-induzierend erkannt wird (und in der Killerzug-Tafel der jeweiligen Suchebene abgelegt wird), wird dieser ebenfalls in der globalen History-Tafel abgelegt. Wie im Falle der Killerzug-Tafeln führen wir auch hier keine Häufigkeitsstatistik, obwohl ein Zähler prinzipiell leicht implementiert werden könnte - somit verkörpert die derzeitige Implementierung eher eine Verallgemeinerung der Killerzug-Heuristik auf die globale Ebene und lässt Spielraum für künftige Verfeinerungen.

In der Rangliste der Präferenz-Heuristiken kommt die History-Heuristik nach der Transpositionstafel-Heuristik und der Killerzug-Heuristik sowie ferner erst nach den gemäß Zugvorsortierung zu präferierenden Zügen (siehe folgenden Abschnitt) zum Einsatz. Auch die History-Heuristik kommt ausschließlich im Non-QS-Part der rekursiven Suche zur Anwendung.

Eine empirische Evaluation hat Anhaltspunkte dafür gegeben, dass ein Geschwindigkeitsgewinn im unteren bis mittleren einstelligen Prozentbereich erzielt wird.