Verzweigungsfaktor & Knotenzahl
Ein Spielbaum modelliert jede mögliche Zugfolge von einer Ausgangsposition. Jeder Knoten stellt einen Feldstand dar. Jede Kante stellt einen legalen Zug dar. Die Struktur des Baums bestimmt, ob die Suche durchführbar bleibt.
Wichtige Parameter
Verzweigungsfaktor b: Anzahl der legalen Züge an einer typischen Position.
Tiefe d: Anzahl der Halbzüge, die voraus gesucht werden sollen.
Knotenzahl in Tiefe d: b^d
Gesamtknotenzahl über alle Tiefen: 1 + b + b² + ... + b^d = (b^(d+1) − 1) / (b − 1)
Für großes b und d ist die Summe ≈ b^d (dominiert durch die Blattebene).
4×4×4 Tic-Tac-Toe
Der vollständige Spielbaum: b ≈ 64 (legale Felder), d = 64 (Gesamtzüge). Vollständige Knotenzahl ≈ 64^64 ≈ 10^115. Das beobachtbare Universum enthält etwa 10^80 Atome. Brute-Force-Suche ist physikalisch unmöglich.
Berechnung der Baumgröße
Schach bietet realistischere Zahlen. Durchschnittlicher Verzweigungsfaktor b ≈ 35. Eine 6-Halbzug-Suche (3 Züge pro Seite) erfordert ungefähr 35^6 Knoten.
Alpha-Beta-Pruning: Reduktion des Exponenten
Alpha-Beta-Pruning eliminiert Teilbäume, die das Minimax-Ergebnis nicht beeinflussen können. Die Schlüsseleinsicht: wenn du bereits weißt, dass ein Zweig den Wert V ergibt, kannst du jeden Geschwister-Zweig prunen, dessen Wert bewiesenermaßen unter V liegt (für den maximierenden Spieler) oder über V liegt (für den minimierenden Spieler).
Best-Case-Geometrie
Unter optimaler Zugordnung (beste Züge werden zuerst gesucht), reduziert Alpha-Beta den effektiven Verzweigungsfaktor von b auf √b. Die Suchtiefe verdoppelt sich effektiv für das gleiche Knotenbudget:
Vollständige Suche: b^d Knoten
Alpha-Beta Best-Case: b^(d/2) Knoten
Beispiel: b=35, d=6. Vollständig: 35^6 ≈ 1,84 × 10^9. Alpha-Beta: 35^3 = 42.875. Reduktionsfaktor: ~43.000.
In der Praxis ist die Zugordnung unvollkommen. Typische Reduktion: b^(d×0,75) — äquivalenter Verzweigungsfaktor ≈ b^0,75.
Zentrum-Ecken-Dualität
Hamming notiert eine geometrische Dualität im 4×4×4-Würfel: es gibt eine Inversion, die die 8 Eckenpositionen zu den 8 Zentrumpositionen (der innere 2×2×2-Würfel) & umgekehrt sendet, während alle 76 gewinnenden Linien erhalten bleiben.
Linien durch eine Position zählen
Im 4×4×4-Würfel unterscheiden sich Positionen darin, wie viele gewinnende Linien durch sie gehen:
Eckenpositionen: 7 Linien je (4 Flächendiagonalen, 2 Kantlinien, 1 Raumdiagonale)
Kantenzentrum-Positionen: 4 Linien je
Flächenzentrum-Positionen: 6 Linien je
Körperzentrum-Positionen (innere 2×2×2): 7 Linien je
Die Dualität sendet Ecken (7 Linien) zu Körperzentren (7 Linien). Beide Sätze bilden 'Hot Spots.'
Warum Hot Spots geometrisch wichtig sind
Ein Spieler, der mehr High-Line-Count-Positionen kontrolliert, kontrolliert mehr potenzielle Gewinnanfänge. Das ist ein direktes geometrisches Argument: Line-Coverage-Maximierung führt die Zugauswahl ohne jede Suche.
Bewertungsfunktionen
Jedes Spielprogramm benötigt eine Bewertungsfunktion: eine Funktion, die Feldstände zu numerischen Werten abbildet (positiv = gut für den maximierenden Spieler, negativ = gut für den minimierenden Spieler). Die Bewertungsfunktion liefert die Randbedingung bei den Blättern des Suchbaums.
Lineare Bewertungsfunktionen
Eine lineare Bewertungsfunktion weist jedem Merkmal f_i des Feldstands ein Gewicht 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 kontrollierte offene Linien, Positionen in High-Line-Count-Feldern, drohende Gabelungen beinhalten. Für Schach: Materialzahl, Zentrumskontrolle, Königssicherheit, Bauernstruktur.
Das ist eine lineare Funktion im Merkmalsraum — eine Hyperebene in ℝ^n. Zwei Positionen mit den gleichen Merkmalswerten erhalten die gleiche Bewertung unabhängig aller anderen Unterschiede. Die Geometrie der Bewertungsfunktion bestimmt, was das Programm 'sieht.'
Samuels Dameprogramm verbesserte sich durch die Anpassung des Gewichtsvektors w — Gradientenabstieg im Raum der linearen Bewertungsfunktionen.
Geometrie & die Grenze der Formalisierung
Der Spielbaum hat eine saubere geometrische Struktur: exponentielles Wachstum bei Tiefe d, reduzierbar zu b^(d/2) durch Alpha-Beta, weiter reduzierbar durch Beschränkung auf High-Value-Positionen (Hot Spots reduzieren effektiv b). Die Bewertungsfunktion definiert eine Hyperebene im Merkmalsraum.
Das alles ist sauber, präzise, formal komplett. Es beschreibt das Zentrum des Spielspiel-Problems — die Region, wo mathematische Struktur klare Anleitung bietet.
Die Grenze — wann von Regelanwendung zu Erkundung wechseln, wann positiven Vorteil für taktische Gelegenheit handeln, wie aufkommende Muster jenseits der Bewertungsfunktion erkennen — widersteht dieser Formalisierung. Hammings stillschweigendes Wissen lebt an dieser Grenze.
Die Geometrie ermöglicht dir, zu berechnen, wie viel Suche du dir leisten kannst. Sie sagt dir nicht, nach was du suchen solltest.