QCM - Algorithme min-max

QCM - Algorithme min-max et élagage α-β

Question 1. Pourquoi l'algorithme de calcul des attracteurs n'est-il pas applicable directement aux échecs ou au go ?

Il ne fonctionne pas sur les graphes bipartisLe nombre de configurations est beaucoup trop grand ($\approx 10^{44}$ aux échecs)Il ne gère pas les puitsIl nécessite un graphe non orienté

Question 2. L'heuristique $h(s)$ utilisée par min-max mesure :

La distance entre $s$ et l'état initialLe nombre de coups restantsÀ quel point la configuration $s$ est favorable au joueur 0Le nombre de successeurs de $s$

Question 3. Quelles affirmations sont vraies concernant min-max et le calcul des attracteurs ? (plusieurs réponses possibles)

Min-max utilise une profondeur limitée, les attracteurs parcourent tout le grapheMin-max nécessite un graphe acyclique, les attracteurs fonctionnent aussi avec des cyclesMin-max fonctionne en top-down, les attracteurs en bottom-upLes deux algorithmes donnent toujours le même résultat

Question 4. Si la profondeur $p = 0$ dans min-max, que renvoie l'algorithme ?

La valeur du premier successeurLa valeur de l'heuristique $h(s)$ de la configuration courante0$+\infty$ ou $-\infty$

Question 5. L'élagage $\alpha$-$\beta$ permet de :

Changer l'heuristique utiliséeCouper des branches inutiles pour accélérer min-max sans changer le résultatAugmenter la profondeur de recherche automatiquementGarantir la solution optimale avec n'importe quelle heuristique

Question 6. Dans l'élagage $\alpha$-$\beta$, on coupe une branche d'un sommet Max quand on trouve une valeur :

Inférieure à $\alpha$Supérieure à $\beta$Égale à $0$Supérieure à $\alpha$

Question 7. Les bornes $\alpha$ et $\beta$ sont initialisées à :

$\alpha = 0$, $\beta = 0$$\alpha = -\infty$, $\beta = +\infty$$\alpha = +\infty$, $\beta = -\infty$$\alpha = -1$, $\beta = 1$

Question 8. Quelles techniques peuvent accélérer l'algorithme min-max ? (plusieurs réponses possibles)

Mémoïsation des configurations déjà rencontréesÉlagage $\alpha$-$\beta$Augmenter la profondeur de rechercheUtiliser une bonne heuristique pour ordonner les successeurs

Question 9.

En appliquant l'élagage $\alpha$-$\beta$ sur l'arbre ci-dessus (parcours de gauche à droite), quelle est la valeur de la racine et quelles feuilles sont élaguées ?

Valeur 7, feuilles 2, 9 et 6 élaguéesValeur 8, feuille 2 élaguéeValeur 7, feuille 2 élaguée uniquementValeur 5, feuilles 9 et 6 élaguées