Problema
La poda alfa-beta da la misma respuesta que minimax mientras se salta las ramas que no pueden cambiar el resultado. Lleva dos cotas: alpha, la mejor puntuación que MAX ya tiene asegurada, y beta, la mejor puntuación que MIN ya tiene asegurada.
El árbol de juego es completo: cada nodo interno tiene branching hijos y todas las hojas están a la misma profundidad. leaves lista las puntuaciones de las hojas de izquierda a derecha. La raíz es un nodo MAX y los niveles se alternan MAX, MIN, MAX, …
Recorre los hijos de izquierda a derecha, empezando con alpha = -∞ y beta = +∞:
- 'En un nodo MAX, después de cada hijo: best = max(best, value), luego alpha = max(alpha, best).'
- 'En un nodo MIN, después de cada hijo: best = min(best, value), luego beta = min(beta, best).'
- En cuanto alpha ≥ beta, sáltate los hijos restantes del nodo.
Implementa alpha_beta(leaves, branching).
Entrada
leaves: Las puntuaciones de las hojas, de izquierda a derecha; la longitud es una potencia de branching.
branching: Hijos por nodo interno.
Salida
Devuelve [value, evaluated]: el valor minimax de la raíz y cuántas hojas se evaluaron.
Restricciones
2 ≤ branching ≤ 5, longitud de leaves = branching^depth con 1 ≤ depth ≤ 8, como máximo 10.000 hojas
-1.000 ≤ cada hoja ≤ 1.000
Ejemplos
Entrada:
leaves = [3, 12, 8, 2, 4, 6, 14, 5, 2]
branching = 3
Salida esperada:
expected = [3, 7]Entrada:
std::vector<long long> leaves = {3, 12, 8, 2, 4, 6, 14, 5, 2};
long long branching = 3;
Salida 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;
Salida esperada:
long[] expected = new long[] {3, 7};Explicación
El primer nodo MIN ve 3, 12, 8 y devuelve 3, así que alpha = 3. El segundo nodo MIN ve 2, beta = 2 ≤ alpha, así que se saltan 4 y 6. El tercero ve 14, 5, 2 y devuelve 2. El valor de la raíz es max(3, 2, 2) = 3 tras 7 de las 9 hojas.
Entrada:
leaves = [5, 6, 7, 4]
branching = 2
Salida esperada:
expected = [5, 4]Entrada:
std::vector<long long> leaves = {5, 6, 7, 4};
long long branching = 2;
Salida esperada:
std::vector<long long> expected = {5, 4};Entrada:
long[] leaves = new long[] {5, 6, 7, 4};
long branching = 2;
Salida esperada:
long[] expected = new long[] {5, 4};Explicación
El nodo MIN izquierdo evalúa 5 y 6 y devuelve 5, así que alpha = 5. El nodo MIN derecho evalúa 7 (beta = 7) y luego 4 (beta = 4 ≤ 5). Se evalúan las 4 hojas y el valor es 5.
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.