Mittel 1 gelöst 100.0% Erfolgsquote

Alpha-Beta Pruning

Evaluate a game tree with minimax and alpha-beta pruning, and count how many leaves the search really looks at.

Das lernst du

  • Track alpha and beta bounds
  • Skip branches that cannot change the result
  • Measure how much work pruning saves

Problem

Übersetzung anzeigen

Alpha-beta pruning gives the same answer as minimax while skipping branches that cannot change the result. It tracks two bounds: alpha, the best score MAX is already sure of, and beta, the best score MIN is already sure of.

The game tree is complete: every internal node has branching children, and all leaves are at the same depth. leaves lists the leaf scores from left to right. The root is a MAX node and the levels alternate MAX, MIN, MAX, …

Search children from left to right, starting with alpha = -∞ and beta = +∞:

  • At a MAX node, after each child: best = max(best, value), then alpha = max(alpha, best).
  • At a MIN node, after each child: best = min(best, value), then beta = min(beta, best).
  • As soon as alpha ≥ beta, skip the node's remaining children.

Implement alpha_beta(leaves, branching).

Input

leaves: The leaf scores, left to right; the length is a power of branching.

branching: Children per internal node.

Output

Return [value, evaluated]: the minimax value of the root and how many leaves were evaluated.

Einschränkungen

2 ≤ branching ≤ 5, length of leaves = branching^depth with 1 ≤ depth ≤ 8, at most 10,000 leaves

-1,000 ≤ each leaf ≤ 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

The first MIN node sees 3, 12, 8 and returns 3, so alpha = 3. The second MIN node sees 2: beta = 2 ≤ alpha, so 4 and 6 are skipped. The third sees 14, 5, 2 and returns 2. The root value is max(3, 2, 2) = 3 after 7 of the 9 leaves.

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

The left MIN node evaluates 5 and 6 and returns 5, so alpha = 5. The right MIN node evaluates 7 (beta = 7), then 4 (beta = 4 ≤ 5). All 4 leaves are evaluated and the value is 5.

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Traverse the game tree left to right while carrying the best guaranteed bounds for MAX and MIN.

Hinweis 2

Use a recursive minimax search that updates the current bound after each child and stops when the two bounds cross.

Hinweis 3

Be careful to count only leaves actually visited, and remember the root starts as a MAX node.

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.