un

guest
1 / ?
back to lessons

Auswurzgrad & Knotenanzahl

Ein Spielbaum modelliert jede mögliche Folge von Zügen von einer Startposition. Jeder Knoten stellt einen Spielbrettzustand dar. Jede Kante stellt einen gültigen Zug dar. Die Struktur des Baums bestimmt, ob die Suche ertragreich bleibt.

Schlüsselparameter

Auswurzgrad b: Anzahl der verfügbaren legalen Züge in einer typischen Position.

Tiefe d: Anzahl der Pli (Halbzüge), für die voraus gesehen zu werden.

Knotenanzahl in der Tiefe d: b^d

Gesamt Knoten über alle Tiefen: 1 + b + b² + ... + b^d = (b^(d+1) − 1) / (b − 1)

Für groß b und d, das gesamte ≈ b^d (dominiert von der Endstufe).

4×4×4 Tic-Tac-Toe

Der vollständige Spielbaum: b ≈ 64 (legale Felder), d = 64 (gesamt Züge). Vollständige Knotenanzahl ≈ 64^64 ≈ 10^115. Der beobachtete Universum enthält ungefähr 10^80 Atome. Brute-Force Suche ist physisch unmöglich.

Spielbaum & Alpha-Beta-Schürfung

Berechnung der Baumgröße

Schach liefert realistischere Zahlen. Durchschnittlicher Auswurzgrad b ≈ 35. Eine 6-Ply-Suche (3 Züge pro Seite) erfordert ungefähr 35^6 Knoten.

Berechne die Anzahl der Blattknoten für eine Schachsuche von Tiefe d = 6 Pli mit Auswurzgrad b = 35. Berechne dann das gleiche für d = 10 Pli. Zeige beide Berechnungen ausdrücklich.

Alpha-Beta-Schürfung: Reduzierung der Exponent

Alpha-Beta-Trennung eliminiert Unterbäume, die den Minimax-Ergebnis nicht beeinflussen können. Der Schlüsselgedanke: Wenn Sie bereits wissen, dass ein Ast den Wert V hat, können Sie jeden Verwandten Ast, dessen Wert beweislich unter V (für den maximierenden Spieler) oder über V (für den minimierenden Spieler) fällt, ausschließen.

Best-Geometrie

Unter optimaler Zugreihenfolge (erste Suche nach besten Zügen) reduziert Alpha-Beta die effektive Verzweigungsfaktor von b auf √b. Die Suchtiefe wirkt sich effektiv verdoppelt für den gleichen Knotenhaushalt:

Vollständige Suche: b^d Knoten

Alpha-Beta Best Case: b^(d/2) Knoten

Beispiel: b=35, d=6. Voll: 35^6 ≈ 1,84 × 10^9. Alpha-Beta: 35^3 = 42.875. Reduktionssatz: ~43.000.

In der Praxis ist die Reihenfolge der Züge unvollkommen. Typischer Reduktionssatz: b^(d×0,75) - äquivalenter Verzweigungsfaktor ≈ b^0,75.

Für ein Schachmodell mit b = 35 und d = 8 Zügen, berechnen Sie die Anzahl der Knoten unter: (1) vollständiger Minimax-Suche, (2) perfekter Alpha-Beta-Trennung (Best-Case). Was ist der Reduktionssatz? Zeigen Sie alle Berechnungen.

Zentrum-Eck-Dualität

Hamming weist auf eine geometrische Dualität im 4×4×4 Würfel hin: Es existiert eine Inversion, die die 8 Eckenpositionen auf die 8 Mittelpositionen (das innere 2×2×2 Würfel) und umgekehrt abbildet, während alle 76 Gewinnlinien erhalten bleiben.

Anzahl Linien durch eine Position

In einem 4×4×4 Würfel unterscheiden sich Positionen durch die Anzahl der Gewinnlinien, die durch sie verlaufen:

Eckpositionen: 7 Linien pro Position (4 Gesichtsdiagonale, 2 Kantenlinien, 1 Raumdiagonale)

Kanten-Mittelpositionen: 4 Linien pro Position

Flächen-Mittelpositionen: 6 Linien pro Position

Körper-Mittelpositionen (innere 2×2×2): 7 Linien pro Position

Die Dualität abbildet Ecken (7 Linien) auf Körper-Mittelpunkte (7 Linien). Beide Mengen bilden 'Hitzepunkte'.

Warum Hitzepunkte geometrisch wichtig sind

Ein Spieler, der mehr Positionen mit einer hohen Anzahl von Linien kontrolliert, kontrolliert mehr potenzielle Gewinnlinien. Dies ist ein direkter geometrischer Argument: die Maximierung der Leitungskennzeichnung leitet die Auswahl der Schritte ohne Suchprozess.

Der 4×4×4-Würfel hat insgesamt 76 gewinnende Linien und 64 Positionen. Die 4 Ecken liegen jeweils auf 7 Linien, die 8 Körper-Zentrum-Positionen liegen jeweils auf 7 Linien, die 24 Gesichtszentrum-Positionen liegen jeweils auf 6 Linien und die 24 Kantenpositionen liegen jeweils auf 4 Linien. Bestätigen Sie: Liegen diese Zahlen konsistent zusammen? Berechnen Sie die Gesamtanzahl der (Position, Linie)-Beziehungen von beiden Seiten: durch Addition über Positionen und getrennt durch Zählung von 4 Endpunkten pro Linie. Stimmen die beiden Gesamtzahlen überein?

Bewertungsfunktionen

Jedes Schachprogramm benötigt eine Bewertungsfunktion: eine Funktion, die Spielbrett-Zustände auf numerische Werte (positiv = gut für den maximalisierenden Spieler, negativ = gut für den minimalisierenden Spieler) abbildet. Die Bewertungsfunktion liefert die Randbedingung an den Blättern des Suchbaums.

Lineare Bewertungsfunktionen

Eine lineare Bewertungsfunktion zuweist jedem Merkmal f_i der Position einen Gewichtungsfaktor w_i zu:

E(position) = w_1 × f_1 + w_2 × f_2 + ... + w_n × f_n

Für 4×4×4 Tic-Tac-Toe: Merkmale könnten offene Linien kontrollieren, Positionen in hochlinienreichen Quadrate, bedrohte Verbindungen umfassen. Für Schach: Materialzählung, Zentrumskontrolle, Königsicherheit, Bauerneinteilung.

Dies ist eine lineare Funktion im Merksraum - eine Ebene in ℝ^n. Zwei Positionen mit den gleichen Merkwerten erhalten die gleiche Bewertung, unabhängig von allen anderen Unterschieden. Die Geometrie der Bewertungsfunktion bestimmt, was das Programm 'sieht'.

Samuels Schachprogramm wurde durch die Anpassung des Gewichtungsvektors w verbessert - Gradientenabfall im Raum linearer Bewertungsfunktionen.

Eine einfache 4×4×4 Tic-Tac-Toe-Bewertungsfunktion verwendet zwei Merkmale: (1) f_1 = Anzahl Ihrer offenen Linien (Linien, an denen Sie Steine haben und der Gegner keine), (2) f_2 = Anzahl der offenen Linien des Gegners. Die Bewertung: E = w_1 × f_1 − w_2 × f_2. Wenn w_1 = 2 und w_2 = 3, berechnen Sie E für eine Position, an der Sie 12 offene Linien haben und der Gegner 8. Dann: Wenn E > 0 bedeutet dies, dass die Position Ihnen zugunsten fällt, was sagt dieses Ergebnis über die Position?

Geometrie & die Grenze der Formalisierung

Der Spielbaum hat eine saubere geometrische Struktur: exponentieller Wachstum bei der Tiefe d, reduziert auf b^(d/2) durch Alpha-Beta, weiter reduziert durch Einschränkung auf hochwertige Positionen (Hitzspots reduzieren die effektive b). Die Auswertungsfunktion definiert eine Hyperfläche im Merkmalsraum.

All das ist sauber, präzise, formal vollständig. Es beschreibt das Zentrum des Spielproblems - die Region, in der die mathematische Struktur klare Anweisungen gibt.

Die Grenze - woher von Regel-Anwendung zur Exploration gewechselt wird, wann taktische Möglichkeiten gegen positionelle Vorteile getauscht werden sollten, wie emergente Muster jenseits der Auswertungsfunktion erkannt werden - widersteht dieser Formalisierung. Hamming's stillschweigendes Wissen lebt an dieser Grenze.

Die Geometrie ermöglicht es Ihnen, zu berechnen, wie viel Suche Sie sich leisten können. Sie sagt Ihnen jedoch nicht, wonach Sie suchen sollten.

Besinnt euch auf die Geometrie, die in diesem Unterricht behandelt wurde. Die Formelsprache des Spielbaums (b^d Knoten, Alpha-Beta-Reduktion auf b^(d/2), lineare Auswertungsfunktionen) bietet eine genaue Beschreibung der *beherrschbaren* Teile des Spielens. Wo bricht die Geometrie zusammen - und welche Eigenschaft der Spielintelligenz liegt jenseits des geometrischen Modells? Geben Sie eine spezifische Antwort, nicht eine allgemeine Beobachtung.