Problem
Alpha-Beta-Pruning liefert dasselbe Ergebnis wie Minimax, überspringt aber Zweige, die das Ergebnis nicht ändern können. Es verfolgt zwei Schranken: alpha, die beste Bewertung, die MAX bereits sicher hat, und beta, die beste Bewertung, die MIN bereits sicher hat.
Der Spielbaum ist vollständig: Jeder innere Knoten hat branching Kinder, und alle Blätter liegen auf derselben Tiefe. leaves listet die Blattbewertungen von links nach rechts. Die Wurzel ist ein MAX-Knoten und die Ebenen wechseln sich ab: MAX, MIN, MAX, …
Durchsuche die Kinder von links nach rechts, beginnend mit alpha = -∞ und beta = +∞:
- 'An einem MAX-Knoten nach jedem Kind: best = max(best, value), dann alpha = max(alpha, best).'
- 'An einem MIN-Knoten nach jedem Kind: best = min(best, value), dann beta = min(beta, best).'
- Sobald alpha ≥ beta gilt, überspringe die restlichen Kinder des Knotens.
Implementiere alpha_beta(leaves, branching).
Eingabe
leaves: Die Blattbewertungen von links nach rechts; die Länge ist eine Potenz von branching.
branching: Kinder pro innerem Knoten.
Ausgabe
Gib [value, evaluated] zurück: den Minimax-Wert der Wurzel und die Anzahl der ausgewerteten Blätter.
Einschränkungen
2 ≤ branching ≤ 5, Länge von leaves = branching^depth mit 1 ≤ depth ≤ 8, höchstens 10.000 Blätter
-1.000 ≤ jedes Blatt ≤ 1.000
Beispiele
Eingabe:
leaves = [3, 12, 8, 2, 4, 6, 14, 5, 2]
branching = 3
Erwartete Ausgabe:
expected = [3, 7]Eingabe:
std::vector<long long> leaves = {3, 12, 8, 2, 4, 6, 14, 5, 2};
long long branching = 3;
Erwartete Ausgabe:
std::vector<long long> expected = {3, 7};Eingabe:
long[] leaves = new long[] {3, 12, 8, 2, 4, 6, 14, 5, 2};
long branching = 3;
Erwartete Ausgabe:
long[] expected = new long[] {3, 7};Erläuterung
Der erste MIN-Knoten sieht 3, 12, 8 und gibt 3 zurück, also alpha = 3. Der zweite MIN-Knoten sieht 2, beta = 2 ≤ alpha, also werden 4 und 6 übersprungen. Der dritte sieht 14, 5, 2 und gibt 2 zurück. Der Wurzelwert ist max(3, 2, 2) = 3 nach 7 von 9 Blättern.
Eingabe:
leaves = [5, 6, 7, 4]
branching = 2
Erwartete Ausgabe:
expected = [5, 4]Eingabe:
std::vector<long long> leaves = {5, 6, 7, 4};
long long branching = 2;
Erwartete Ausgabe:
std::vector<long long> expected = {5, 4};Eingabe:
long[] leaves = new long[] {5, 6, 7, 4};
long branching = 2;
Erwartete Ausgabe:
long[] expected = new long[] {5, 4};Erläuterung
Der linke MIN-Knoten wertet 5 und 6 aus und gibt 5 zurück, also alpha = 5. Der rechte MIN-Knoten wertet 7 aus (beta = 7), dann 4 (beta = 4 ≤ 5). Alle 4 Blätter werden ausgewertet und der Wert ist 5.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Durchlaufe den Spielbaum von links nach rechts und führe dabei die besten garantierten Grenzen für MAX und MIN mit.
Hinweis 2
Nutze eine rekursive Minimax-Suche, die die aktuelle Grenze nach jedem Kind aktualisiert und stoppt, sobald sich die beiden Grenzen kreuzen.
Hinweis 3
Achte darauf, nur tatsächlich besuchte Blätter zu zählen, und denk daran, dass die Wurzel als MAX-Knoten startet.
Erwartete Komplexität
O(b^d) time in the worst case, O(d) extra space
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.