Условие
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.
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Traverse the game tree left to right while carrying the best guaranteed bounds for MAX and MIN.
Подсказка 2
Use a recursive minimax search that updates the current bound after each child and stops when the two bounds cross.
Подсказка 3
Be careful to count only leaves actually visited, and remember the root starts as a MAX node.
Ожидаемая сложность
O(b^d) time in the worst case, O(d) extra space
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.