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.
Hierzu werden zwei Schranken und (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 , ein Minknoten verursacht einen Abbruch bei Unterschreiten von . Die Wurzel des Baumes wird mit = - , = + aufgerufen.
PROCEDURE alphabeta (s: Spielbaum;
, : INTEGER): INTEGER;
BEGIN
IF blatt(s) THEN RETURN statisch(s)
ELSE
bestimme Nachfolger
s1,s2,...,sd ;
FOR i := 1 TO d DO
m := alphabeta(
si,, );
IF typ(s) = max AND m > THEN := m END;
IF typ(s) = min AND m < THEN := m END;
IF
THEN RETURN m;
END
IF typ (s) = max THEN RETURN ELSE RETURN
END
Alpha-Beta-Suche in einem Spielbaum. | |
Vermerkt an den Knoten sind die sich ändernden Suchfenster. | |
Cutoffs sind durch gestrichelte Kanten angedeutet. |
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: