Mittel 1 gelöst 100.0% Erfolgsquote

Alpha-Beta-Pruning

Bewerte einen Spielbaum mit Minimax und Alpha-Beta-Pruning und zähle, wie viele Blätter die Suche tatsächlich ansieht.

Das lernst du

  • Alpha- und Beta-Schranken verfolgen
  • Zweige überspringen, die das Ergebnis nicht ändern können
  • Messen, wie viel Arbeit das Pruning spart

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

Beispiel 1
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.

Beispiel 2
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.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

# Coder Sprache Zeit Speicher KI-Bewertung Lösung
1 ННикита Python 1,183 ms - 5/5 Code ansehen

Von anderen lernen

Community-Lösungen

Achtung Spoiler: 1 vollständige Lösung unten Versuche es zuerst selbst zu lösen. Du kannst trotzdem einen Blick auf den Code und die KI-Reviews anderer Entwickler werfen. Melde dich an und löse die Aufgabe, um an der Diskussion teilzunehmen.