문제
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.
제약 조건
2 ≤ branching ≤ 5, length of leaves = branching^depth with 1 ≤ depth ≤ 8, at most 10,000 leaves
-1,000 ≤ each leaf ≤ 1,000
예시
입력:
leaves = [3, 12, 8, 2, 4, 6, 14, 5, 2]
branching = 3
예상 출력:
expected = [3, 7]입력:
std::vector<long long> leaves = {3, 12, 8, 2, 4, 6, 14, 5, 2};
long long branching = 3;
예상 출력:
std::vector<long long> expected = {3, 7};입력:
long[] leaves = new long[] {3, 12, 8, 2, 4, 6, 14, 5, 2};
long branching = 3;
예상 출력:
long[] expected = new long[] {3, 7};설명
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.
입력:
leaves = [5, 6, 7, 4]
branching = 2
예상 출력:
expected = [5, 4]입력:
std::vector<long long> leaves = {5, 6, 7, 4};
long long branching = 2;
예상 출력:
std::vector<long long> expected = {5, 4};입력:
long[] leaves = new long[] {5, 6, 7, 4};
long branching = 2;
예상 출력:
long[] expected = new long[] {5, 4};설명
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.
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.