Math
Spielbaum und Alpha-Beta
Ein Spielbaum, in dem jeder Block so hoch ist wie sein Wert: ein MAX-Knoten so hoch wie sein höchstes Kind, ein MIN-Knoten so niedrig wie sein niedrigstes. Minimax liest jedes Blatt; Alpha-Beta überspringt, was die Antwort nicht ändern kann, und wie viel es überspringt, hängt von der Zugreihenfolge ab.
Was passiert
Jeder Block ist so hoch wie sein Wert, darum ist die Regel sichtbar, bevor sie genannt wird: ein MAX-Knoten steht so hoch wie sein höchstes Kind, ein MIN-Knoten so niedrig wie sein niedrigstes, und die Wurzel ist der Wert des Spiels. Minimax liest alle b^d Blätter. Alpha-Beta liest sie der Reihe nach und hört bei einem Knoten auf, sobald ein schon gesehener Nachbar den Rest belanglos macht - die Zweige, die es nie betritt, bleiben dunkel. Die Antwort ändert sich dadurch nie, nur die Zahl, und die hängt von der REIHENFOLGE der Züge ab, nicht vom Baum: mit dem besten Zug zuerst an jedem Knoten braucht es genau das Minimum von Knuth und Moore, etwa die Wurzel aus b^d; mit dem schlechtesten zuerst sieht es jedes Blatt - aber nur bis Tiefe 3, denn ab Tiefe 4 reicht das an der Wurzel gehobene Alpha nach unten und schneidet selbst das. Worauf zu achten ist: die dunklen Zweige, der goldene Pfad der Hauptvariante und die drei Balken dahinter - Minimax, diese Suche, das Minimum.
Gleichungen des Moduls
Gleichungen MAX-Knoten: v = max über die Kinder; MIN-Knoten: v = min über die Kinder; Minimax liest alle b^d Blätter Alpha-Beta: den Rest der Kinder eines Knotens abschneiden, sobald alpha >= beta - die Antwort bleibt dieselbe, die Anzahl nicht perfekte Ordnung: N_min = 2·b^(d/2) − 1 für gerades d, b^((d+1)/2) + b^((d−1)/2) − 1 für ungerades d (Knuth - Moore, 1975) schlechteste Ordnung an jedem Knoten: N = b^d für d <= 3; ab d = 4 erreicht das Alpha der Wurzel die dritte Ebene und schneidet trotzdem ab Ordnung s in [−1, 1]: die Kinder eines Knotens werden nach exaktem Wert sortiert, wenn die eigene Hash-Münze unter |s| liegt - bei s > 0 das beste zuerst, bei s < 0 das schlechteste zuerst
