Альфа-бета отсечение даёт тот же ответ, что и минимакс, но пропускает ветви, которые не могут изменить результат. Оно отслеживает две границы: alpha — лучшая оценка, которую MAX уже гарантировал, и beta — лучшая оценка, которую уже гарантировал MIN.
Дерево игры полное: у каждого внутреннего узла branching потомков, и все листья на одной глубине. leaves перечисляет оценки листьев слева направо. Корень — узел MAX, уровни чередуются: MAX, MIN, MAX, …
Обходите потомков слева направо, начиная с alpha = -∞ и beta = +∞:
- 'В узле MAX после каждого потомка: best = max(best, value), затем alpha = max(alpha, best).'
- 'В узле MIN после каждого потомка: best = min(best, value), затем beta = min(beta, best).'
- Как только alpha ≥ beta, пропустите оставшихся потомков узла.
Реализуйте alpha_beta(leaves, branching).
Входные данные
leaves: Оценки листьев слева направо; длина — степень branching.
branching: Число потомков у внутреннего узла.
Выходные данные
Верните [value, evaluated]: минимаксное значение корня и число оценённых листьев.
Ограничения
2 ≤ branching ≤ 5, длина leaves = branching^depth, где 1 ≤ depth ≤ 8, не более 10 000 листьев
-1 000 ≤ каждый лист ≤ 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};Пояснение
Первый узел MIN видит 3, 12, 8 и возвращает 3, поэтому alpha = 3. Второй узел MIN видит 2, beta = 2 ≤ alpha, поэтому 4 и 6 пропускаются. Третий видит 14, 5, 2 и возвращает 2. Значение корня — max(3, 2, 2) = 3 после 7 из 9 листьев.
Ввод:
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};Пояснение
Левый узел MIN оценивает 5 и 6 и возвращает 5, поэтому alpha = 5. Правый узел MIN оценивает 7 (beta = 7), затем 4 (beta = 4 ≤ 5). Оценены все 4 листа, значение равно 5.
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.