Problema
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.
Restrições
2 ≤ branching ≤ 5, length of leaves = branching^depth with 1 ≤ depth ≤ 8, at most 10,000 leaves
-1,000 ≤ each leaf ≤ 1,000
Exemplos
Entrada:
leaves = [3, 12, 8, 2, 4, 6, 14, 5, 2]
branching = 3
Saída esperada:
expected = [3, 7]Entrada:
std::vector<long long> leaves = {3, 12, 8, 2, 4, 6, 14, 5, 2};
long long branching = 3;
Saída esperada:
std::vector<long long> expected = {3, 7};Entrada:
long[] leaves = new long[] {3, 12, 8, 2, 4, 6, 14, 5, 2};
long branching = 3;
Saída esperada:
long[] expected = new long[] {3, 7};Explicação
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.
Entrada:
leaves = [5, 6, 7, 4]
branching = 2
Saída esperada:
expected = [5, 4]Entrada:
std::vector<long long> leaves = {5, 6, 7, 4};
long long branching = 2;
Saída esperada:
std::vector<long long> expected = {5, 4};Entrada:
long[] leaves = new long[] {5, 6, 7, 4};
long branching = 2;
Saída esperada:
long[] expected = new long[] {5, 4};Explicação
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.
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.