Problema
La potatura alfa-beta dà lo stesso risultato di minimax saltando i rami che non possono cambiare il risultato. Tiene traccia di due limiti: alpha, il miglior punteggio di cui MAX è già sicuro, e beta, il miglior punteggio di cui MIN è già sicuro.
L'albero di gioco è completo: ogni nodo interno ha branching figli e tutte le foglie sono alla stessa profondità. leaves elenca i punteggi delle foglie da sinistra a destra. La radice è un nodo MAX e i livelli si alternano MAX, MIN, MAX, …
Esplora i figli da sinistra a destra, partendo da alpha = -∞ e beta = +∞:
- 'In un nodo MAX, dopo ogni figlio: best = max(best, value), poi alpha = max(alpha, best).'
- 'In un nodo MIN, dopo ogni figlio: best = min(best, value), poi beta = min(beta, best).'
- Appena alpha ≥ beta, salta i figli rimanenti del nodo.
Implementa alpha_beta(leaves, branching).
Input
leaves: I punteggi delle foglie, da sinistra a destra; la lunghezza è una potenza di branching.
branching: Figli per nodo interno.
Output
Restituisci [value, evaluated]: il valore minimax della radice e quante foglie sono state valutate.
Vincoli
2 ≤ branching ≤ 5, lunghezza di leaves = branching^depth con 1 ≤ depth ≤ 8, al massimo 10.000 foglie
-1.000 ≤ ogni foglia ≤ 1.000
Esempi
Input:
leaves = [3, 12, 8, 2, 4, 6, 14, 5, 2]
branching = 3
Output atteso:
expected = [3, 7]Input:
std::vector<long long> leaves = {3, 12, 8, 2, 4, 6, 14, 5, 2};
long long branching = 3;
Output atteso:
std::vector<long long> expected = {3, 7};Input:
long[] leaves = new long[] {3, 12, 8, 2, 4, 6, 14, 5, 2};
long branching = 3;
Output atteso:
long[] expected = new long[] {3, 7};Spiegazione
Il primo nodo MIN vede 3, 12, 8 e restituisce 3, quindi alpha = 3. Il secondo nodo MIN vede 2, beta = 2 ≤ alpha, quindi 4 e 6 vengono saltati. Il terzo vede 14, 5, 2 e restituisce 2. Il valore della radice è max(3, 2, 2) = 3 dopo 7 foglie su 9.
Input:
leaves = [5, 6, 7, 4]
branching = 2
Output atteso:
expected = [5, 4]Input:
std::vector<long long> leaves = {5, 6, 7, 4};
long long branching = 2;
Output atteso:
std::vector<long long> expected = {5, 4};Input:
long[] leaves = new long[] {5, 6, 7, 4};
long branching = 2;
Output atteso:
long[] expected = new long[] {5, 4};Spiegazione
Il nodo MIN di sinistra valuta 5 e 6 e restituisce 5, quindi alpha = 5. Il nodo MIN di destra valuta 7 (beta = 7), poi 4 (beta = 4 ≤ 5). Tutte e 4 le foglie vengono valutate e il valore è 5.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Percorri l'albero di gioco da sinistra a destra mantenendo i migliori limiti garantiti per MAX e MIN.
Suggerimento 2
Usa una ricerca minimax ricorsiva che aggiorna il limite corrente dopo ogni figlio e si ferma quando i due limiti si incrociano.
Suggerimento 3
Fai attenzione a contare solo le foglie davvero visitate, e ricorda che la radice parte come nodo MAX.
Complessità attesa
O(b^d) time in the worst case, O(d) extra space
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.