Dr. Roland Stuckardt

IT-Beratung - Sprachtechnologie - Medienanalyse

Iterative Vertiefung & Aspirationsfenster-Suche

Grundgedanken und Merkmale der Iterativen Vertiefung:

  • Wir suchen nicht gleich mit maximaler Suchtiefe, sondern steigern diese mit 1 oder 2 beginnend; Vorteil: Wir können die Suche jederzeit abbrechen und erhalten trotzdem ein Ergebnis.
  • insbesondere zentrale Voraussetzung für die ausstehende Implementierung eines Zeitmanagements.
  • Anders als auf den ersten Blick zu erwarten entsteht hierdurch in aller Regel kein Zusatzaufwand, da wir ja schrittweise die Transpositionstafel auffüllen und somit redundante Mehrfachberechnungen (weitestgehend!?) vermeiden; gemäß den Erfahrungen, die mit dieser Technik in vielen anderen Schach-Engines gemacht wurden, soll sich sogar i. A. eine signifikante Effizienzsteigerung ergeben.

Grundgedanken und Merkmale der Aspirationsfenster-Suche:

  • Die Aspirationsfenstersuche spielt sich (in Abgrenzung von der nachfolgend beschriebenen Minimalfenstersuche (MFS)) definitionsgemäß auf dem Such-Top-Level ab und soll hier wie allgemein üblich mit der Technik der Iterativen Vertiefung kombiniert werden.
  • Wenn wir von vornherein mit einem eingeschränkten Alpha-Beta-Fenster suchen, innerhalb dessen die dynamische Positionsbewertung der letztlich gefundenen Hauptvariante liegt, so erreichen wir oftmals eine Geschwindigkeitssteigerung, da wir bedingt durch die engeren Schranken mehr prunen können.
  • Potenzieller Nachteil: Wir müssen den Suchvorgang mit größeren bzw. maximalen Schranken vollständig wiederholen (sog. Re-Searches), insofern sich das hypothetisierte Suchfenster im nachhinein als falsch herausstellt.
  • →Es kommt also entscheidend darauf an, geeignete Aspirationsfenstergrößen zu wählen, sodass der i. A. moderate Mehrgewinn qua verbessertem Pruning-Verhalten nicht durch teure Re-Searches aufgezehrt werden – laut einschlägiger Literatur ein delikates Problem!
  • In besonderem Maße kritisch sind natürlich solche Re-Searches, die sich für Iterationen mit maximaler oder nahezu maximaler Suchtiefe ergeben.
  • Auch in Erwägung zu ziehen ist Festlegung der Aspirationsfenstergrößen mit Blick auf die Dynamik der aktuellen Spielphase – denkbar ist etwa der Verzicht auf die Anwendung der Aspirationsfenstertechnik in Phasen, in denen bereits eine Reihe von Top-Level-Re-Searches durchzuführen waren.

Konzeptuelle Beschreibung

Die in der gegenwärtigen Fischerle-Version zum Einsatz kommende Technik der Iterativen Vertiefung ist schnell beschrieben:

  • Wir iterieren über die Suchtiefen 1 (Tiefe 2 wäre wohl ebenfalls möglich) bis modisubati, wobei die zuletzt genannte sog. modifizierte Suchbasistiefe i. d. R. der vom Benutzer gewählten maximalen Suchtiefe entspricht, jedoch ggf. modifiziert (genauer: reduziert) wird, falls bereits ein Matt in Sicht ist – somit wird nur so tief gesucht, wie tatsächlich notwendig ist.
  • Für jeden Iterationsschritt wird Methode alphabetaminimax unter Angabe der entsprechenden Suchtiefe aufgerufen; die Parameter alpha und beta ergeben sich gemäß nachfolgend beschriebener Aspirationsfenster-Technik.
  • Zurückgeliefert wird der Wert sowie die Hauptvariante des letzten Iterationsdurchlaufs. (Ausnahme: Der Anwender bricht die Suche vorzeitig ab; in diesem Fall wird das letzte vollständig ermittelte Zwischenergebnis zurückgeliefert.)

Die von Fischerle derzeit verwendete Technik der Aspirationsfenstersuche ist folgendermaßen ausgestaltet:

  • Im ersten Iterationsschritt (Suchtiefe 1) starten wir stets mit einem Fenster maximaler Größe (MinAlpha, MaxBeta);
  • in den Folgeschritten nehmen wir stets das Ergebnis des jeweils zuletzt abgeschlossenen Iterationsschritts als Bezugswert B, um den herum wir das Fenster legen;
  • wir beobachten nun ferner, dass aus Sicht der am Zug befindlichen Partei der Evaluationswert
    • für ungerade Suchtiefen gegenüber dem Bezugswert B tendenziell eher steigt – schließlich ist die am Zug befindliche Partei in dem (ausschließlich der QS) zuletzt betrachteten Zug ebenfalls an der Reihe;
    • für gerade Suchtiefen gegenüber dem Bezugswert tendenziell eher sinkt – hier verhält es sich genau andersherum.
  • unter Maßgabe dieser Beobachtung legen wir nun das Suchintervall asymmetrisch um den Bezugswert, wobei sich Größe und effektive Lage des Intervalls aus den zwei Werten AFF_Gross := 560 und AFF_Klein := 240; (Bezugsgröße: tausendstel Bauerneinheiten)  ergeben, denn wir setzen:
    • alpha := B–AFF_Klein; beta := B+AFF_Gross für ungerade STen;
    • alpha := B–AFF_Gross; beta := B+AFF_Klein für gerade STen.

Somit beträgt die Größe des Intervalls stets 0.8 Bauerneinheiten, und das Intervall ist mit einer 7:3-Asymmetrie angelegt.

Die Festlegungen AFF_Gross := 560, AFF_Klein := 240 wurden empirisch ermittelt und scheinen einen guten Kompromiss betreffend Kleinheit des Intervalls vs. Re-Search-Häufigkeiten zu ergeben – vgl. externe Notizen. Weiter gehende Beobachtungen aus dem Dauereinsatz legen jedoch eine Optimierungsmöglichkeit nahe: Insofern die Bezugswerte eine stärkere Volatilität aufweisen, also beispielsweise starke Schwankungen bzw. häufige Re-Searches bereits für die niedrige Suchtiefen einer Iterativen Suche beobachtet werden, kann es sich anbieten, die höheren Suchtiefen gleich mit dem Maximalintervall anzugehen; dieses Verfahren ist weiter generalisierbar dahingehend, das auch die Schwankungsbreite des Evaluationswerts für die k vorangegangenen Züge – k geeignet zu wählen – als Entscheidungskriterium herangezogen wird.