10.4 Spielbaumsuche

Ein Spielbaum hat zwei Typen von Knoten: Minimum-Knoten und Maximum-Knoten. Die Knoten repräsentieren Spielstellungen in einem 2-Personen-Spiel. Der Wert eines Blattes wird bestimmt durch eine statische Stellungsbewertung. Der Wert eines Minimum-Knotens ist das Minimum der Werte seiner Söhne. Der Wert eines Maximum-Knotens ist das Maximum seiner Söhne.

PROCEDURE minmax (s: Spielbaum): INTEGER;
BEGIN
   IF blatt(s) THEN RETURN statisch(s)
   ELSE
      bestimme Nachfolger s[1], s[2], ..., s[d];
      IF typ(s) = max THEN t := -INFINITY ELSE t := +INFINITY END;
      FOR i := 1 TO d DO
         m := minmax (s[i});
         IF typ(s) = max AND m > t THEN t := m END;
         IF typ(s) = min AND m < t THEN t := m END
    END
    RETURN t
END

Der Wert der Wurzel läßt sich durch eine komplette Tiefensuche bis zu den Blättern ermitteln. Eine Beschleunigung wird dadurch erreicht, daß bei einem Knoten dann keine weiteren Söhne bearbeitet werden, wenn ihre Werte keinen Einfluß auf den Wert der Spielbaumwurzel haben.

Cutoff im Spielbaum

Hierzu werden zwei Schranken $\alpha$ und $\beta$ (für die Maximierungs- bzw. Minimierungsebenen) übergeben, die zu einem vorzeitigen Cutoff führen können. D.h., ein Maxknoten verursacht einen Abbruch bei Überschreiten von $\beta$ , ein Minknoten verursacht einen Abbruch bei Unterschreiten von $\alpha$ . Die Wurzel des Baumes wird mit $\alpha$ = - $\infty$, $\beta$ = + $\infty$ aufgerufen.

Bemerkung:

Bei Tiefe h und Verzweigungsgrad d erzeugt minmax d ^h Blätter. Unter günstigen Umständen (alle Söhne sind nach Qualität sortiert) erzeugt
alphabeta 2 · d ^h/2 Blätter, also eine Reduktion von n auf $\sqrt{n}$ .

PROCEDURE alphabeta (s: Spielbaum; $\alpha$, $\beta$ : INTEGER): INTEGER;

BEGIN
     IF blatt(s) THEN RETURN statisch(s)
     ELSE
         bestimme Nachfolger s₁,s₂,...,s_d ;
        

         FOR i := 1 TO d DO
             m := alphabeta( s_i,$\alpha$,$\beta$ );
             IF typ(s) = max AND m > $\alpha$ THEN $\alpha$ := m END;
             IF typ(s) = min AND m < $\beta$ THEN $\beta$ := m END;
             IF $\alpha$ $\geq$ $\beta$ THEN RETURN m;
         END
         IF typ (s) = max THEN RETURN $\alpha$ ELSE RETURN $\beta$
     END

Bei der parallelen Spielbaumsuche bearbeiten Prozessoren lokale Teilbäume (analog wie bei Tiefensuche), die sie bei Bedarf als Auftragnehmer von einem anderen Prozessor, genannt Auftraggeber, anfordern. Zusätzlich entsteht Kommunikationsbedarf:

• Der Auftragnehmer meldet das Ergebnis seiner Teilbaumauswertung an den Auftraggeber zurück, da es dort benötigt wird zur Bestimmung des Vater-Wertes.
• Der Auftraggeber meldet sich verkleinernde $\alpha$ - $\beta$ -Fenster an seine Auftragnehmer weiter, da sie dort zu zusätzlichen Cutoffs führen können.

Können die Söhne eines Knotens durch eine Heuristik vorsortiert werden, so sollten erst nach Auswertung des (vermutlich) besten Sohns dessen Brüder an Auftragnehmer abgegeben werden. Somit entsteht ein unvermeidbarer Tradeoff zwischen unbeschäftigten Prozessoren und überflüssiger Suche.

Bemerkung:

Das Paderborner Schachprogramm ZUGZWANG erreichte auf 1024 Prozessoren einen maximalen Speedup von 400 und einen mittleren Speedup von 344.