Alpha-Beta-Suche verständlich erklärt

Wer ein Brettspiel wie Vier gewinnt gründlich durchrechnet, muss sehr viele Zwischenstände ansehen. Ein einfacher Gedanke erspart einen großen Teil davon, ohne das Ergebnis zu ändern. Wie viel er erspart, hängt von der Reihenfolge ab, in der man prüft.

Zuletzt aktualisiert: 11. November 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Ein Zug, viele Antworten

Sie spielen Vier gewinnt gegen eine Freundin. Die Steine fallen abwechselnd in ein aufrecht stehendes Brett. Wer zuerst vier eigene Steine in einer Reihe hat, gewinnt. Ist das Brett voll und niemand hat gewonnen, heißt das Remis.

Sie sind am Zug und wollen sicher gehen. Sie nehmen an, Ihre Freundin findet die Antwort, die Ihnen am meisten schadet. Zu jedem Ihrer Züge fragen Sie darum: Was ist das Schlimmste, das sie daraus machen kann? Sie wählen den Zug, bei dem dieses Schlimmste noch am besten ausgeht. Ein Sieg ist besser als ein Remis, ein Remis besser als eine Niederlage. Diese Regel heißt Minimax.

Sicher wissen Sie das nur, wenn Sie alles bis zum Spielende durchrechnen. Eine Maschine geht dazu alle Zugfolgen durch wie die Äste eines Baums. Jeder Zwischenstand auf dem Brett heißt Stellung. Es sind sehr viele.

Die Abkürzung

Angenommen, Sie haben einen ersten Zug schon geprüft. Er sichert Ihnen ein Remis, was auch immer Ihre Freundin tut. Nun sehen Sie sich einen zweiten Zug an und gehen ihre Antworten darauf einzeln durch. Schon die erste Antwort lässt Ihre Freundin gewinnen.

Jetzt können Sie aufhören. Ihre Freundin wählt die für sie beste Antwort. Der zweite Zug ist also höchstens so gut wie diese eine Antwort. Weitere Antworten können ihn nur verschlechtern. Schon jetzt ist er schlechter als Ihr Remis-Zug. Die übrigen Antworten sehen Sie sich nicht mehr an.

Dasselbe gilt, wenn die Antwort nur ein Remis ergibt und Sie schon ein Remis haben. Der zweite Zug könnte den ersten dann nicht übertreffen.

Dieses Abschneiden von Ästen heißt Alpha-Beta-Pruning („Pruning“ ist englisch für Zurückschneiden). Alpha und Beta sind zwei Merkzettel der Maschine. Alpha ist das Beste, das Sie schon sicher haben, im Beispiel das Remis. Beta ist das Beste, das Ihre Freundin Ihnen noch zugesteht. Nach ihrer ersten Antwort ist das nur noch eine Niederlage. Beta liegt dann unter Alpha, und die Maschine bricht ab.

Das Ergebnis bleibt dabei dasselbe wie beim vollen Durchrechnen. Abgeschnitten wird nur, was den Zug nie hätte retten können. Die Maschine findet also den gleichen besten Zug, nur mit weniger Arbeit.

Die Reihenfolge entscheidet

Hätten Sie die Antwort, die den zweiten Zug erledigt, als erste gesehen, wären Sie nach einem Blick fertig. Kommt sie als letzte, haben Sie alle anderen umsonst angesehen. Die Abkürzung bringt also je nach Reihenfolge mehr oder weniger.

Auch bei Ihren eigenen Zügen hilft es, die guten zuerst zu prüfen. Dann steht früh fest, was Sie sicher haben, und schwächere Züge fallen schneller durch. Ein wirklich guter Zug lässt sich dagegen nicht abkürzen: Hier müssen Sie alle Antworten ansehen, denn keine darf ihn widerlegen. Gespart wird bei den schwächeren Zügen.

Die beste Reihenfolge kennt man erst, wenn man weiß, welche Züge gut sind.

Das Programm zum Ausprobieren

Zu dieser Seite gehört ein Programm zum Ausprobieren im Browser, die Demo. Der erste Knopf unten öffnet sie, der zweite führt zum zweiten Teil für Fachleute. Zum Verstehen brauchen Sie sie nicht.

Die Demo spielt Vier gewinnt auf kleinen Brettern durch, das kleinste hat 3×3 Felder. Sie zählt, wie viele Stellungen die Maschine dabei ansieht. Fachleute nennen jede angesehene Stellung einen Knoten. Sie vergleicht vier Reihenfolgen, in denen die Maschine die Spalten prüft. Zwei davon brauchen Vorwissen, also die Kenntnis, welche Züge wirklich gut sind:

• Naiv: von links nach rechts, ohne Vorwissen.
• Mitte zuerst: die mittleren Spalten zuerst, eine verbreitete Faustregel, ohne Vorwissen.
• Bester Fall: nach dem wahren Wert der Züge, der beste zuerst, mit Vorwissen.
• Schlechtester Fall: nach dem wahren Wert der Züge, der schlechteste zuerst, mit Vorwissen.

Das Vorwissen für die letzten beiden holt sich die Demo, indem sie das Brett vorab ganz durchrechnet. Diese Vorarbeit zählt sie nicht mit, und im echten Spiel gäbe es sie nicht. Die beiden Fälle zeigen nur, wie sich der Aufwand verschiebt, wenn man die Zugwerte kennt. Andere Reihenfolgen können darüber oder darunter liegen. Sie gibt es nur auf den drei kleinsten Brettern.

Die Aussagen in diesem Teil beschreiben diese kleinen Bretter, nicht Vier gewinnt in voller Größe.

Was die Demo zeigt

Abschneiden spart sehr viel, schon ohne Vorwissen. Auf dem Brett mit 4×4 Feldern sah die volle Suche 83.078.201 Stellungen an. Mit Abschneiden und der Reihenfolge von links nach rechts waren es 43.827, bei gleichem Ergebnis. Das sind 1.896-mal weniger. Der Grund: Ein Schnitt weit oben im Baum spart den ganzen Ast samt allem, was daran hängt.

Die Reihenfolge verschiebt den Aufwand. Auf einem Brett mit 4 Zeilen und 3 Spalten sah die Maschine im besten Fall 601 Stellungen an. Im schlechtesten waren es 1.286, bei demselben Ergebnis.

Eine Faustregel ist keine Garantie. Auf dem Brett mit 4×4 Feldern sah die Maschine mit „Mitte zuerst“ 108.671 Stellungen an. Von links nach rechts waren es nur 43.827. Beide Werte gelten ab dem leeren Brett. Ab einer anderen Stellung sparte dieselbe Regel dagegen. Auf dem Brett mit 4 Zeilen und 3 Spalten sah die Maschine nach einem ersten Stein in der Mitte weniger Stellungen an als von links nach rechts.

Warum die Faustregel auf 4×4 bremst, hat die Demo nicht untersucht. Eine mögliche Deutung: Die Regel kennt nur die Lage der Spalte, nicht die Stärke des Zugs. Sind die mittleren Züge nicht die stärksten, fallen schwache Züge erst spät durch.

Auf dem kleinsten Brett ändern die vier Reihenfolgen nichts. Alle brauchen auf 3×3 Feldern 213 Stellungen. Der Grund: Hier passt keine Viererreihe hin, jede Partie endet remis, und keine Antwort ist besser als eine andere. Abgeschnitten wird trotzdem, denn ein Remis, das man schon in der Hand hat, genügt zum Abbruch.

Häufige Missverständnisse

• „Mit dem Abschneiden ist Vier gewinnt in voller Größe gelöst.“ Nein. Die Arbeit wächst mit dem Brett weiter. Ein Brett mit 4 Zeilen und 5 Spalten war der Demo auch mit Abschneiden zu langsam (laut ihrer Vormessung).
• „Der beste Fall zeigt, was eine Maschine erreicht.“ Nein. Er setzt voraus, dass die Maschine die Zugwerte schon kennt.

Woran Sie das im Alltag erkennen

Nehmen wir an, Sie wählen eine Wohnung, die nur so gut ist wie ihr schwächster Punkt, etwa Lärm, Preis oder Arbeitsweg. Anzeichen:

• Sie haben schon eine brauchbare Möglichkeit. Zeigt eine neue gleich beim ersten Punkt einen schlechteren Wert, prüfen Sie ihre übrigen Punkte nicht mehr.
• Sie fragen zuerst nach dem Punkt, an dem Möglichkeiten am ehesten scheitern, etwa dem Lärm. So hören Sie früh auf.

Wie ernst ist das Rechenbild zu nehmen?

Die Demo ist ein vereinfachtes Rechenbild: ein kleines Brettspiel ohne Zufall und ohne Zeitlimit. Wie viel eine Reihenfolge spart, kann in einer anderen Stellung anders ausfallen.

Was Sie mitnehmen:

• Wer schon etwas Gutes in der Hand hat, muss Schlechteres nicht zu Ende prüfen.
• In welcher Reihenfolge Sie prüfen, entscheidet über die Arbeit, nicht über das Ergebnis.
• Eine Faustregel für die Reihenfolge ist zunächst eine Vermutung. Messen Sie nach, bevor Sie sich auf sie verlassen.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar.

• Spiel: Mini-Vier-Gewinnt, ein deterministisches Nullsummenspiel mit zwei abwechselnd ziehenden Seiten. Die Steine fallen in die unterste freie Zeile einer Spalte, die Sieglänge ist fest 4, Rot beginnt. Der Spielwert einer Stellung ist +1 (Sieg Rot), −1 (Sieg Gelb) oder 0 (Remis) bei perfektem Spiel beider Seiten; Rot maximiert, Gelb minimiert. Der Wert kennt nur diese drei Stufen.
• Bretter: Live wählbar sind 3×3, 4×3, 3×4, 4×4, 5×4 und 3×5 (Zeilen × Spalten). Voreinstellung ist 4 Zeilen × 3 Spalten mit der naiven Reihenfolge. Die Demo rechnet ab dem leeren Brett oder ab jeder Stellung, die man durch Anklicken von Zügen erreicht; die Messwerte unten gelten für das leere Brett.
• Knoten: Gezählt wird jeder Aufruf der Suche für eine noch unentschiedene Stellung, die Wurzel eingeschlossen. Endstellungen (Sieg oder volles Brett) zählen nicht. Genauso zählt die vollständige Minimax-Suche, mit der die Demo vergleicht.
• Suchfenster: Die Suche führt ein Fenster \([\alpha, \beta]\) mit. \(\alpha\) ist der Wert, den Rot auf dem bisherigen Pfad schon sicher hat, \(\beta\) der Wert, den Gelb Rot höchstens lässt. Die Wurzel startet mit \([-2, 2]\), weiter als jeder Spielwert.
• Reihenfolge: An jedem Knoten werden die freien Spalten in einer von vier Reihenfolgen geprüft. Naiv: Spalte 0, 1, 2 und so weiter. Mitte zuerst: nach wachsendem Abstand zur Brettmitte, bei gleichem Abstand die kleinere Spaltennummer zuerst. Bester und schlechtester Fall: nach dem exakten Wert des Folgezustands, aus Sicht des Ziehenden der beste bzw. der schlechteste zuerst; bei gleichem Wert bleibt die Reihenfolge von links nach rechts.
• Vorwissen (Orakel): Für den besten und den schlechtesten Fall löst die Demo die Ausgangsstellung vorab einmal vollständig ohne Abschneiden und merkt sich den Wert jedes erreichbaren Zustands. Diese Vorarbeit wird ausgewiesen, aber nicht in die Knotenzahl eingerechnet. Sie steht nur auf 3×3, 4×3 und 3×4 zur Verfügung. Die Vorarbeit ist eine vollständige Suche ohne Abschneiden und ohne Wiederverwendung gleicher Stellungen; auf 4×4 dauerte die vollständige Suche 334 s, zu lang für den Live-Betrieb.
• Messung: Die Suche enthält keinen Zufall. Knotenzahlen sind daher ganze Zahlen, die vom Rechner nicht abhängen; Zeiten hängen von ihm ab.

Die Formel

Die Suche ist Minimax mit einem Fenster. Die Demo schreibt sie so:

\[\alpha\text{-}\beta(s, \alpha, \beta) = \begin{cases} \text{Endwert} & s \text{ ist Sieg/Remis} \\ v & \text{sobald } \alpha \geq \beta \text{ (Abschneiden)} \end{cases}\]

Der erste Fall gibt bei einer Endstellung ihren Wert zurück. Der zweite beschreibt den Abbruch: Sobald \(\alpha \ge \beta\), kann kein weiterer Zug des Knotens das Ergebnis noch verbessern, und die übrigen Züge werden nicht besucht. Das ist eine Skizze, keine vollständige Rekursion. Vollständig läuft sie so: Ist Rot am Zug, ist \(v\) der größte bisher gefundene Wert über die geprüften Nachfolger, nach jedem Nachfolger setzt man \(\alpha \leftarrow \max(\alpha, v)\), bei \(\alpha \ge \beta\) bricht man ab. Ist Gelb am Zug, ist \(v\) der kleinste bisher gefundene Wert, und man setzt \(\beta \leftarrow \min(\beta, v)\). Zurückgegeben wird \(v\), nicht \(\alpha\) oder \(\beta\) (fail-soft). \(v\) hat vor dem ersten Nachfolger keinen Wert und wird von ihm gesetzt. Die Nachfolger erhalten das jeweils aktuelle Fenster.

Herleitungen Schritt für Schritt

Die Herleitungen dieses Abschnitts sind Rechnungen dieser Seite, keine Messungen der Demo.

Warum das Abschneiden den Wert nicht ändert. Sei \(M(s)\) der Minimax-Wert der Stellung \(s\) und \(v\) der Rückgabewert der Suche mit Fenster \((\alpha, \beta)\), wobei \(\alpha < \beta\) gilt. Die Rückgabe ist eine Schranke, kein stets exakter Wert.

• Schritt 1, Behauptung: (a) Aus \(\alpha < v < \beta\) folgt \(v = M(s)\). (b) Aus \(v \le \alpha\) folgt \(M(s) \le v\). (c) Aus \(v \ge \beta\) folgt \(M(s) \ge v\). Der Beweis ist eine Induktion über die Zahl der freien Felder.
• Schritt 2, Anfang: Endstellungen tragen ihr Ergebnis, es ist exakt.
• Schritt 3, Rot am Zug, Abbruch: Die Suche bricht ab, sobald \(\alpha \ge \beta\). Weil vorher \(\alpha < \beta\) galt, hat dann ein Nachfolger \(w = v \ge \beta\) geliefert. Nach (c) für diesen Nachfolger ist sein Minimax-Wert mindestens \(w\). Rot maximiert, also \(M(s) \ge v\). Das ist (c).
• Schritt 4, Rot am Zug, \(v \le \alpha\): Kein Nachfolger hat \(\alpha\) übertroffen, alle wurden mit demselben Fenster gerufen und lieferten \(w \le \alpha\). Nach (b) ist ihr Minimax-Wert höchstens \(w \le v\). Also \(M(s) \le v\).
• Schritt 5, Rot am Zug, \(\alpha < v < \beta\): Es gab keinen Abbruch. Jeder Nachfolger lieferte entweder \(w \le \alpha'\) mit dem Alpha \(\alpha'\) seines Fensters (dann nach (b) \(M \le w \le v\), denn \(\alpha' \le v\)) oder \(\alpha' < w < \beta\) (dann nach (a) exakt, \(M = w \le v\)). Der erste Nachfolger mit \(w = v\) hat \(\alpha' < v\) und fällt in den zweiten Fall, also ist \(M = v\) und damit \(M(s) = v\).
• Schritt 6, Gelb und Wurzel: Gelb am Zug ist spiegelbildlich. An der Wurzel gilt \((\alpha, \beta) = (-2, 2)\), und jeder Spielwert liegt in \(\{-1, 0, 1\}\). Dort greift Fall (a): Der Rückgabewert ist der Minimax-Wert, das Abschneiden ändert den Spielwert nicht.
• Folge für die Wurzelzüge: Für die Spalten, die nach dem ersten besten Zug geprüft werden, liefert die Suche nur Schranken nach (b). Exakt ist der Wert des gewählten besten Zugs.

Die Prüfungen der Demo stützen das an Beispielen. Gegen eine unabhängig geschriebene Fassung (Negamax mit anderer Stellungsdarstellung) stimmen an vierzig fest gewählten Zufallsstellungen je Reihenfolge Wert und Knotenzahl überein, und der gewählte Zug ist ein optimaler Zug (Bretter von 1×1 bis 5×5, höchstens acht freie Felder). Auf dem leeren Brett 3×3 und 4×3 werden für alle vier Reihenfolgen die Knotenzahlen verglichen.

Was ein Schnitt spart. Ein Schnitt in einem Knoten überspringt die Teilbäume aller noch nicht geprüften Nachfolger vollständig. Der Gewinn hängt deshalb von der Größe dieser Teilbäume ab, und ein früher Schnitt weit oben spart am meisten. Für einen gleichförmigen Baum mit Verzweigungsgrad \(b\) und Tiefe \(d\) und perfekt geordneten Zügen liegt die Zahl der betrachteten Blätter nach Knuth und Moore bei \(b^{\lceil d/2 \rceil} + b^{\lfloor d/2 \rfloor} - 1\), grob der Quadratwurzel der \(b^d\) Blätter der vollständigen Suche (aus dem Gedächtnis, nicht geprüft). Die Bäume der Demo sind nicht gleichförmig, und die Demo zählt Knoten statt Blätter; die Formel ist deshalb kein Vergleichswert für die Messung. Nur als Größenordnung (Rechnung dieser Seite): Die Quadratwurzel von 83.078.201 liegt bei gut neuntausend, die gemessenen 43.827 der naiven Reihenfolge liegen knapp das Fünffache darüber, wie bei einer nicht perfekten Reihenfolge zu erwarten.

Durchgerechnet: ein Beispielbaum

Rechnung dieser Seite an einem abstrakten Baum, kein Brett der Demo. Rot hat drei Züge \(a\), \(b\), \(c\). Auf jeden antwortet Gelb mit einer der Antworten der Liste; die Zahl ist der Wert der Endstellung (+1 Sieg Rot, 0 Remis, −1 Sieg Gelb). Gezählt werden bewertete Endstellungen, damit der Schnitt sichtbar wird; ohne Abschneiden sind es sieben. Die Antworten stehen in dieser Reihenfolge: \(a\): (+1, 0), \(b\): (0, −1, +1), \(c\): (−1, 0). Rot prüft zuerst \(a\), dann \(b\), dann \(c\); der Start ist \([\alpha, \beta] = [-2, 2]\).

• Zug \(a\): Gelb sieht +1 (\(\beta = 1\)), dann 0 (\(\beta = 0\)). Wegen \(\alpha = -2\) gibt es keinen Abbruch. Wert 0, zwei Bewertungen. Rot hat jetzt \(\alpha = 0\).
• Zug \(b\): Die erste Antwort ist 0, also \(\beta = 0 \le \alpha = 0\). Der Gleichstand schneidet: Der Zug könnte \(a\) nicht übertreffen. Rückgabe 0, eine Bewertung, zwei gespart. Der wahre Wert von \(b\) ist −1; die 0 ist nur eine obere Schranke, die für die Wurzel keine Rolle spielt.
• Zug \(c\): Die erste Antwort ist −1, also \(\beta = -1 \le 0\). Abbruch, Rückgabe −1, eine Bewertung, eine gespart.
• Ergebnis: Der Wurzelwert ist 0 (Remis), gewählt wird \(a\), bewertet wurden vier von sieben Endstellungen.

Alle sechs Reihenfolgen der drei Züge liefern den Wert 0. Bewertet werden vier Endstellungen, wenn \(a\) zuerst kommt, fünf bei \(c, a, b\) und sechs in den drei übrigen Fällen. Das ist der Reihenfolge-Effekt der Demo im Kleinen: Der beste Zug zuerst hebt \(\alpha\) früh an, und die übrigen Züge fallen schneller durch.

Befunde

Gemessen wurde die Alpha-Beta-Suche der Demo ab dem leeren Brett mit Rot am Zug. Der beste und der schlechteste Fall brauchen die Vorarbeit des Orakels und liegen nur für die drei kleinsten Bretter vor; auf 4×4 fehlen sie.

Brett (Zeilen × Spalten)	Naiv	Mitte zuerst	Schlechtester Fall	Bester Fall
3×3	213	213	213	213
4×3	749	749	1.286	601
3×4	2.826	2.826	6.128	2.302
4×4	43.827	108.671	–	–

Frage	Befund
Wie viel spart das Abschneiden gegenüber der vollständigen Suche? (4×4, naive Reihenfolge)	Die vollständige Minimax-Suche braucht 83.078.201 Knoten (334 s), die Alpha-Beta-Suche mit naiver Reihenfolge 43.827 (0,15 s): das ~1.896-fache weniger. Die Zeiten hängen vom Rechner ab; die Quelle nennt ihn nicht.
Wie groß ist der Reihenfolge-Effekt? (4×3, schlechtester gegen bester Fall)	Faktor 2,1 bei identischem Spielwert.
Hilft eine plausible Heuristik immer? (Mitte zuerst)	Nein: Auf 4×4 braucht sie mehr Knoten als die naive Reihenfolge. Auf 4×3 nach einem ersten Stein in Spalte 1 (Spalten von 0 an gezählt, die mittlere) braucht sie deutlich weniger als die naive Reihenfolge.
Macht die Reihenfolge immer einen Unterschied?	Nein: Auf 3×3 braucht jede der vier Reihenfolgen 213 Knoten. Auf 4×3 und 3×4 liegen naiv und Mitte zuerst gleichauf. Erklärung im Abschnitt zu den Grenzen.
Welchen Spielwert liefert die Suche ab dem leeren Brett?	Auf allen vier Brettern Remis (Wert 0). Die Prüfungen der Demo belegen das für die naive Reihenfolge; die übrigen verfügbaren Reihenfolgen liefern denselben Wert (Nachrechnung dieser Seite).

Nachrechnungen dieser Seite mit dem Code der Demo; sie stehen in Worten, weil sie nicht zu den Messwerten der Demo gehören:

• Der Gewinn war auf den vier Brettern wachsend. Gegenüber der vollständigen Suche auf demselben leeren Brett spart die naive Reihenfolge auf 3×3 knapp das Siebzehnfache der Knoten, auf 4×3 gut das Neunzigfache, auf 3×4 rund das Zweihundertfünfzigfache und auf 4×4 das 1.896-fache. Vier Brettgrößen, die sich auch in der Geometrie der Viererreihen unterscheiden, ergeben keinen Verlauf, nur eine wachsende Folge.
• Der Reihenfolge-Vergleich gilt für eine Stellung, nicht für ein Brett. Auf dem leeren Brett (3×5 und 5×4 stehen nicht in der Tabelle) braucht Mitte zuerst auf 3×5 gut ein Viertel der Knoten der naiven Reihenfolge, also weniger, auf 5×4 knapp ein Zehntel mehr. Auf 4×3 nach einem ersten Stein in der mittleren Spalte braucht sie knapp drei Zehntel weniger als die naive Reihenfolge, nach einem ersten Stein in der linken Spalte rund zwei Fünftel mehr.
• Der schlechteste Fall ist nicht der schlimmste. Auf 4×3 wurden dreihundert Zufallsreihenfolgen probiert (an jedem Knoten eine gleichverteilt gemischte Reihenfolge der freien Spalten, ein Lauf je Reihenfolge, drei Wiederholungen mit festen Startwerten): Gut ein Viertel bis knapp drei Zehntel davon brauchten mehr Knoten als der schlechteste Fall der Demo, und der größte Wert lag zwischen einem Sechstel und einem Fünftel darüber. Der schlechteste Fall ist nur die nach dem Wert ungünstigste Reihenfolge. Bei gleichen Werten schneidet die Suche trotzdem, weil schon \(\alpha \ge \beta\) abbricht. Eine Obergrenze ist er nicht. Der beste Fall ist ebenso keine Untergrenze: Auf 4×3 nach einem ersten Stein in der mittleren Spalte braucht Mitte zuerst weniger Knoten als der beste Fall.
• Der Faktor 2,1 ist ein Verhältnis zweier Sonderfälle, nicht die Spanne aller Reihenfolgen. Auf 3×4 beträgt dasselbe Verhältnis mehr als das Zweieinhalbfache, und auf 4×4 braucht Mitte zuerst knapp das Zweieinhalbfache der Knoten der naiven Reihenfolge.

Was die Messung zeigt und was nicht

Was sie belegt:

• Die Knotenzahlen der Tabelle ab dem leeren Brett: ganzzahlig und ohne Zufall. Bis auf drei Zellen (3×4: Mitte zuerst, schlechtester und bester Fall) rechnet eine Prüfung der Demo sie mit der ausgelieferten Suche nach, auf 3×3 und 4×3 zusätzlich für alle vier Reihenfolgen mit der unabhängig geschriebenen Fassung. Diese drei Zellen hat die Seite selbst mit dem Code der Demo reproduziert.
• Die Aussage, dass das Abschneiden den Spielwert nicht ändert: durch die Herleitung oben, unter den Bedingungen Fenster \((-2, 2)\) an der Wurzel und endlich viele Spielwerte, und durch den Vergleich mit der unabhängigen Fassung an den genannten Stellungen.
• Den gleichen Wert Remis auf 3×3, 4×3 und 3×4 in der vollständigen Suche und in der Alpha-Beta-Suche. Auf 4×4 liegt von der vollständigen Suche nur die vorab gemessene Knotenzahl samt Zeit vor, kein nachgerechneter Spielwert; dort stützt sich der Wert allein auf die Alpha-Beta-Suche.

Was sie nicht belegt (Grenzen):

• Bester und schlechtester Fall sind kein Verfahren. Sie setzen ein Orakel voraus und stehen nur auf den drei kleinsten Brettern. Der schlechteste Fall ist keine Obergrenze (siehe oben).
• Nur ein Wurzelzug ist exakt. Ein einzelner Lauf mit vollem Fenster liefert nur für den gewählten besten Zug einen beweisbar exakten Wert, für schlechtere Züge oft nur eine Schranke. Anders als die vollständige Suche kennt er nicht alle gleichwertigen Züge.
• Die Ursache bei „Mitte zuerst“ ist nicht untersucht. Die Deutung, die Regel kenne nur die Lage der Spalte und nicht die Stärke des Zugs, ist nicht gemessen. Dass der Vergleich von der Stellung abhängt, ist dagegen nachgerechnet (siehe oben).
• Zeiten und Rechner: Keine Prüfung der Demo verlangt die Zeiten. Der Rechner ist nicht genannt.
• Nur drei Wertstufen. Sieg, Remis und Niederlage lassen viele Gleichstände zu, und Gleichstände schneiden. Bei einer feineren Bewertung kann der Effekt anders ausfallen; die Demo misst das nicht.
• Kleine Bretter, zum Teil durch die Geometrie bestimmt. Bei Sieglänge 4 passt auf 3×3 keine Viererreihe, auf 4×3 nur senkrechte, auf 3×4 nur waagerechte. Das Remis ist dort zum Teil schon durch die Geometrie vorgegeben, und auf 3×3 gibt es gar keine Gewinnstellung; darum ändert dort keine der vier Reihenfolgen etwas. Bester und schlechtester Fall fallen bei lauter gleichen Werten mit der naiven Reihenfolge zusammen. Weil auf 3×3 alle Spalten gleichwertig sind, ergibt außerdem jede feste Spaltenreihenfolge 213 Knoten (alle sechs geprüft, Rechnung dieser Seite). Mischt man an jedem Knoten neu, ändert sich die Zahl: in hundert Läufen bis gut ein Drittel über 213, bei stets gleichem Wert. Auf 4×3 sind ebenfalls alle Spalten austauschbar (nur senkrechte Viererreihen), darum liegen dort naiv und Mitte zuerst gleichauf; nach dem ersten Stein gilt das nicht mehr. Für 3×4 ist das Gleichauf nicht erklärt.
• Nur Vollsuche bis zum Spielende. Es gibt keine Tiefenbegrenzung und keine Bewertungsfunktion. Transpositionstabellen und Verfeinerungen der Zugreihenfolge wie Killer-Züge und die History-Heuristik sind bewusst nicht umgesetzt.
• Keine öffentliche Referenz. Für diese Brettgrößen gibt es keinen öffentlichen Referenzlöser. Die Korrektheit stützt sich auf die Vergleichswerte der vollständigen Suche und auf die unabhängig geschriebene Fassung; beide sind eigener Code, kein fremder Löser.

Erweiterungen und Verweise

Was die Demo auslässt oder voraussetzt, zeigen eigene Demos derselben Reihe:

• Die Suche ohne Abschneiden: Die minimax-demo durchsucht den vollständigen Spielbaum ohne Abschneiden; ihre Knotenzahlen sind der Vergleichswert dieser Seite.
• Dieselbe Stellung nur einmal lösen: Die transposition-table-demo erkennt Stellungen wieder, die über verschiedene Zugfolgen entstehen, und baut auf der Alpha-Beta-Suche auf. Laut ihrer README wächst der Gewinn mit der Brettgröße.

Quellen

• Knuth, D. E., & Moore, R. W. (1975): An analysis of alpha-beta pruning. Artificial Intelligence 6(4), 293–326 (Analyse des Abschneidens und der besten Reihenfolge).
• Russell, S., & Norvig, P.: Artificial Intelligence: A Modern Approach (Lehrbuch; das Kapitel zur Spielsuche behandelt das Alpha-Beta-Verfahren).
• Quelltext, Messungen und Prüfungen der Demo: github.com/sebastian-hanisch/alpha-beta-demo.

Die beiden Literaturangaben stammen aus dem Gedächtnis und wurden für diese Seite nicht nachgeschlagen; die Demo nennt keine Literatur. Herleitung, Beispielbaum und Nachrechnungen sind Rechnungen dieser Seite, keine Messungen der Demo.