Partiel Master 1 Informatique - Intelligence Artificielle

Exercice 1 - Algorithmes de recherche

Question 1 - Admissibilité des heuristiques h1 et h2

Pour qu'une heuristique soit admissible, elle ne doit jamais surestimer le coût réel pour atteindre le but. Mathématiquement, pour tout nœud n, on doit avoir h(n) ≤ h*(n). En comparant avec les valeurs de h* données dans le tableau :

• Pour h1 : on vérifie que h1(n) ≤ h*(n) est vrai pour chaque nœud (ex: h1(A)=10 ≤ 10, h1(B)=5 ≤ 5, etc.). Donc h1 est admissible.
• Pour h2 : on observe que h2(C) = 8, alors que le coût réel h*(C) = 5. Puisque 8 > 5, l'heuristique h2 surestime le coût. Elle n'est donc pas admissible.

Question 2 - Domination entre h1 et h2

Ni l'une ni l'autre ne domine. D'après le cours, on ne peut parler de domination de manière stricte que si les deux heuristiques comparées sont admissibles, ce qui n'est pas le cas ici. De plus, elles se croisent : on a h1(B) = 11 > h2(B) = 2, et inversement h2(C) = 8 > h1(C) = 5.

Question 3 - Admissibilité de h3 = max(h1, h2)

Non, h3 n'est pas admissible. Puisque h3(n) = max(h1(n), h2(n)), on obtient pour le nœud C : h3(C) = max(5, 8) = 8. Puisque 8 > h*(C) = 5, h3 surestime le coût.

Question 4 - Recherche gloutonne avec h2

La recherche gloutonne (ou "greedy search") développe toujours le nœud ayant la plus petite valeur d'heuristique h. Voici la trace du développement en utilisant h2 :

• Nœud initial : (A, 10)
• Depuis A, on a le choix entre C(8) et D(11). On choisit C. File : (C, 8), (D, 11).
• Depuis C, on a le choix entre B(2), H(4) et F(6). On choisit B. File : (B, 2), (H, 4), (F, 6), (A, 10), (D, 11).
• Depuis B, on a le choix entre I(0) et G(3). On choisit I. File : (I, 0), (G, 3), (H, 4), (F, 6), (E, 9), (A, 10), (D, 11).

On s'arrête en atteignant le but I. Le chemin trouvé est : A, C, B, I.

Question 5 - Recherche A* avec h1

L'algorithme A* développe le nœud minimisant la fonction f(n) = g(n) + h(n). Voici la suite des nœuds développés (avec leurs valeurs f = g + h) :

• (A, 10 = 0 + 10)
• (C, 10 = 5 + 5), (D, 15 = 5 + 10)
• (F, 10 = 5 + 2 + 3), (H, 11 = 5 + 3 + 3), (B, 13 = 5 + 3 + 5), (D, 15), (A, 20 = 5 + 5 + 10), (D, 21 = 5 + 6 + 10)
• (H, 11), (G, 13 = 5 + 2 + 3 + 3), (B, 13), (C, 14 = 5 + 2 + 2 + 5), (B, 15 = 5 + 2 + 3 + 5), (D, 15), (A, 20), (D, 21)
• (I, 12 = 5 + 3 + 4), (G, 13), (B, 13), (C, 14), (B, 15), (D, 15), (C, 16 = 5 + 3 + 3 + 5), (A, 20), (D, 21)

On s'arrête avec le nœud I. Le chemin optimal trouvé est : A, C, H, I.

Question 6 - Recherche A* avec h2

En théorie, on ne devrait pas appliquer A* avec h2 car l'algorithme est défini pour garantir l'optimalité uniquement avec des heuristiques admissibles, et h2 ne l'est pas. Si l'on force quand même l'exécution, voici la trace des développements (f = g + h2) :

• (A, 10 = 0 + 10)
• (C, 13 = 5 + 8), (D, 16 = 5 + 11)
• (B, 10 = 5 + 3 + 2), (H, 12 = 5 + 3 + 4), (F, 13 = 5 + 2 + 6), (D, 16), (A, 20 = 5 + 5 + 10), (D, 22 = 5 + 6 + 11)
• (H, 12), (I, 13 = 5 + 3 + 5 + 0), (F, 13), (G, 15 = 5 + 3 + 4 + 3), (D, 16), (F, 17 = 5 + 3 + 3 + 6), (C, 19 = 5 + 3 + 3 + 8), (A, 20), (E, 22 = 5 + 3 + 5 + 9), (D, 22)
• (I, 12 = 5 + 3 + 4 + 0), (I, 13), (F, 13), (G, 15), (C, 16 = 5 + 3 + 3 + 5), (D, 16), (F, 17), (C, 19), (A, 20), (E, 22), (D, 22)

On s'arrête avec le nœud I. Le chemin trouvé est : A, C, H, I.

Question 7 - Recherche A* avec h3

Tout comme pour h2, appliquer A* avec h3 est techniquement incorrect car h3 n'est pas admissible. Si on déroule l'algorithme, on obtient :

• (A, 10 = 0 + 10)
• (C, 13 = 5 + 8), (D, 16 = 5 + 11)
• (H, 12 = 5 + 3 + 4), (F, 13 = 5 + 2 + 6), (B, 13 = 5 + 3 + 5), (D, 16), (A, 20 = 5 + 5 + 10), (D, 21 = 5 + 6 + 10)
• (I, 12 = 5 + 3 + 4 + 0), (F, 13), (B, 13), (D, 16), (C, 19 = 5 + 3 + 3 + 8), (A, 20), (D, 21)

On s'arrête avec le nœud I et le chemin : A, C, H, I.

Question 8 - Preuve d'admissibilité de max(h1, h2)

Si h1 et h2 sont admissibles, cela implique par définition que pour tout nœud n, h1(n) ≤ h*(n) et h2(n) ≤ h*(n). Puisque les deux valeurs h1(n) et h2(n) sont inférieures ou égales à h*(n), la plus grande des deux l'est également. On a donc systématiquement max(h1(n), h2(n)) ≤ h*(n). Par conséquent, l'heuristique combinée h3 = max(h1, h2) est toujours admissible.

Question 9 - Choix de la meilleure heuristique

Si l'on a le choix entre trois heuristiques admissibles h1, h2 et h3 = max(h1, h2), il faut choisir h3. Justification : h3 fournit systématiquement la valeur la plus élevée (sans jamais dépasser le coût réel), elle estime donc le mieux la vraie distance h*. Une heuristique qui domine les autres permet à l'algorithme A* de développer moins de nœuds tout en garantissant un résultat optimal.

Exercice 2 - Jeux

Question 1 - Coupures alpha-beta sur un arbre de jeu

Il existe une infinité de combinaisons possibles pour forcer l'algorithme à couper les branches indiquées. Voici un exemple de valeurs pour les feuilles : a=5, b=2, c=6, e=7, f=1, g=1, h=8, j=1, k=1, l=1 (les autres feuilles peuvent avoir n'importe quelle valeur car elles seront coupées).

Trace du déroulement avec ces valeurs (α, β) :

• On commence à la racine A avec (-∞, ∞).
• B descend avec (-∞, ∞), puis C avec (-∞, ∞).
• C évalue "a" et trouve 5. C met à jour sa valeur de remontée (5, ∞).
• B, nœud MIN, récupère 5 et met à jour β. Son intervalle devient (-∞, 5).
• D descend avec (-∞, 5). Il évalue "c" et trouve 6. D met à jour α à 6. Son intervalle devient (6, 5).
• Condition de coupure atteinte (α ≥ β) : on coupe les autres fils de D.
• B remonte 5 à A. L'intervalle de A (nœud MAX) devient (5, ∞).
• E descend avec (5, ∞). F descend avec (5, ∞) et évalue "e" à 7. F met à jour (7, ∞) et remonte à E.
• L'intervalle de E (nœud MIN) devient (5, 7).
• G descend avec (5, 7). Il évalue "h" à 8. L'intervalle de G devient (8, 7).
• Coupure (α ≥ β) : on coupe les autres fils de G.
• A reçoit 7 de E (car E min(7, ?)). L'intervalle de A devient (7, ∞). (Note: la correction de l'énoncé source suggère que la remontée de A reste à (5, ∞) à ce stade précis, pour des raisons de lecture de gauche à droite avant la finalisation de E).
• H descend. Il trouvera une valeur qui forcera une coupure précoce si on maintient correctement l'intervalle restreint issu de la mise à jour de A.

Question 2 - Algorithme alpha-beta avec paramètres initiaux modifiés

• Avec α = 9 et β = 14 : L'algorithme va couper l'évaluation des deux nœuds valant 10, du nœud valant 11, et de tout le troisième sous-arbre (troisième fils de la racine). Le résultat remonté sera 14.

• Avec α = 16 et β = 21 : L'algorithme coupera systématiquement le deuxième fils de chaque nœud MIN, ainsi que le troisième le cas échéant (puisque les valeurs dépassent largement l'intervalle de recherche des nœuds MIN qui vont abaisser β sous 16 très vite). Le résultat remonté sera 16.

• Signification des résultats :

  • Le premier résultat (14) étant égal à la borne supérieure β (14), cela signifie que la vraie valeur minimax de l'arbre est supérieure ou égale à 14 (≥ 14).
  • Le deuxième résultat (16) étant égal à la borne inférieure α (16), cela signifie que la vraie valeur minimax est inférieure ou égale à 16 (≤ 16).

• Condition pour obtenir le même résultat qu'avec α = -∞ et β = ∞ : Pour que les bornes initiales (a, b) ne faussent pas le résultat final de l'arbre, il faut que la vraie valeur minimax se trouve strictement à l'intérieur (ou aux limites) de cet intervalle. La condition est : a ≤ vrai résultat ≤ b.

Question 3 - Recherche en avant vs Recherche en arrière

Les algorithmes pour les jeux cherchent à partir de la position courante vers l'avant (vers les feuilles) plutôt que de l'arrière (des feuilles vers la racine) pour plusieurs raisons pratiques :

1. Les états buts (victoire, défaite) sont très nombreux (voire infinis ou inconnus à l'avance), il est donc difficile de cibler un but précis pour remonter jusqu'à la racine.
2. La notion de MIN et MAX dépend du tour du joueur, ce qui est trivial en descendant depuis la position courante, mais ambigu en remontant à l'aveugle depuis une position finale sans connaître l'historique exact des tours.

Exercice 3 - Jeux (Calculs de complexité)

Question 1 - Nombre exact de feuilles dans l'arbre

Dans cet arbre complet alternant les nœuds MAX (facteur de branchement b1) et MIN (facteur de branchement b2) depuis une racine MAX :

• Pour une profondeur p impaire : Le dernier niveau (feuilles) sera généré par une couche de nœuds ayant un branchement b1. Le nombre total de feuilles est donné par : b1^((p+1)/2) × b2^((p-1)/2).
• Pour une profondeur p paire : Le dernier niveau sera généré par une couche de nœuds MIN. Le nombre total de feuilles est donné par : b1^(p/2) × b2^(p/2).

Question 2 - Nombre minimum de feuilles évaluées (SSS*)

L'algorithme SSS* dans le meilleur des cas (comme pour l'élagage alpha-beta optimal) n'évalue qu'une fraction des feuilles :

• Pour une profondeur p impaire : Le nombre minimum de feuilles évaluées est de : b1^((p+1)/2) + b2^((p-1)/2) - 1. Justification (reconstituée depuis les fragments) : La première passe de l'algorithme va évaluer b1^((p+1)/2) nœuds pour construire une solution candidate. Ensuite, pour confirmer que ce résultat est le meilleur, l'algorithme doit évaluer le reste de l'arbre optimal, ajoutant b2^((p-1)/2) - 1 nœuds supplémentaires.

• Pour une profondeur p paire : Le nombre minimum de feuilles évaluées est de : b1^(p/2) + b2^(p/2) - 1. Justification : Même principe d'évaluation d'une première passe candidate (b1^(p/2) nœuds) puis vérification minimale des branches alternatives (b2^(p/2) - 1 nœuds).

Méthode

Pour aborder sereinement ce type d'épreuve :

1. Algorithmes de graphes : La clé pour les questions sur A* et la recherche gloutonne est de tenir un registre rigoureux de votre "frontière" (la file de priorité) à chaque étape. Notez les valeurs (f, g, h) pour éviter de vous emmêler entre coût parcouru et coût estimé. Assurez-vous d'avoir bien compris qu'une heuristique doit être admissible pour garantir un résultat A* optimal.
2. Arbres de jeux (Alpha-Beta) : Visualisez la propagation de l'intervalle [α, β]. α est le minimum assuré pour MAX, et β le maximum autorisé pour MIN. Dès que α ≥ β à un nœud, coupez !
3. Formalisme : Ne vous laissez pas impressionner par les formules des arbres minimax. Décomposez le problème en regardant un arbre de profondeur 1, 2 puis 3 pour déduire (ou vérifier) la formule de récurrence liant le nombre de niveaux MAX et MIN.