Problème
L'élagage alpha-bêta donne le même résultat que minimax tout en sautant les branches qui ne peuvent pas changer le résultat. Il suit deux bornes : alpha, le meilleur score dont MAX est déjà sûr, et beta, le meilleur score dont MIN est déjà sûr.
L'arbre de jeu est complet : chaque nœud interne a branching enfants et toutes les feuilles sont à la même profondeur. leaves liste les scores des feuilles de gauche à droite. La racine est un nœud MAX et les niveaux alternent MAX, MIN, MAX, …
Explorez les enfants de gauche à droite, en partant de alpha = -∞ et beta = +∞ :
- 'À un nœud MAX, après chaque enfant : best = max(best, value), puis alpha = max(alpha, best).'
- 'À un nœud MIN, après chaque enfant : best = min(best, value), puis beta = min(beta, best).'
- Dès que alpha ≥ beta, sautez les enfants restants du nœud.
Implémentez alpha_beta(leaves, branching).
Entrée
leaves : Les scores des feuilles, de gauche à droite ; la longueur est une puissance de branching.
branching : Le nombre d'enfants par nœud interne.
Sortie
Renvoyez [value, evaluated] : la valeur minimax de la racine et le nombre de feuilles évaluées.
Contraintes
2 ≤ branching ≤ 5, longueur de leaves = branching^depth avec 1 ≤ depth ≤ 8, au plus 10 000 feuilles
-1 000 ≤ chaque feuille ≤ 1 000
Exemples
Entrée :
leaves = [3, 12, 8, 2, 4, 6, 14, 5, 2]
branching = 3
Sortie attendue :
expected = [3, 7]Entrée :
std::vector<long long> leaves = {3, 12, 8, 2, 4, 6, 14, 5, 2};
long long branching = 3;
Sortie attendue :
std::vector<long long> expected = {3, 7};Entrée :
long[] leaves = new long[] {3, 12, 8, 2, 4, 6, 14, 5, 2};
long branching = 3;
Sortie attendue :
long[] expected = new long[] {3, 7};Explication
Le premier nœud MIN voit 3, 12, 8 et renvoie 3, donc alpha = 3. Le deuxième nœud MIN voit 2 : beta = 2 ≤ alpha, donc 4 et 6 sont sautés. Le troisième voit 14, 5, 2 et renvoie 2. La valeur de la racine est max(3, 2, 2) = 3 après 7 des 9 feuilles.
Entrée :
leaves = [5, 6, 7, 4]
branching = 2
Sortie attendue :
expected = [5, 4]Entrée :
std::vector<long long> leaves = {5, 6, 7, 4};
long long branching = 2;
Sortie attendue :
std::vector<long long> expected = {5, 4};Entrée :
long[] leaves = new long[] {5, 6, 7, 4};
long branching = 2;
Sortie attendue :
long[] expected = new long[] {5, 4};Explication
Le nœud MIN de gauche évalue 5 et 6 et renvoie 5, donc alpha = 5. Le nœud MIN de droite évalue 7 (beta = 7), puis 4 (beta = 4 ≤ 5). Les 4 feuilles sont évaluées et la valeur est 5.
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.