Chapitre 3.

-suite
Intelligence Artificielle
Résolution des Problèmes
(Recherche)- suite
 Algorithmes de
recherche heuristiques
(informés)
 Méthodes de recherche heuristiques

• Les algorithmes de recherche aveugle n'exploitent aucune information concernant

la structure de l'arbre de recherche ou la présence potentielle de nœuds-solution
pour optimiser la recherche.

• La plupart des problèmes réels sont susceptibles de provoquer une explosion

combinatoire du nombre d'états possibles.

• Un algorithme de recherche heuristique utilise l'information disponible pour rendre

le processus de recherche plus efficace.

• Une information heuristique est une règle ou une méthode qui améliore, presque
toujours, le processus de recherche.
 Fonction heuristique
• Une fonction h heuristique est définie :
h : E(états) → IR
fait correspondre à un état s ∈ E (espace d'états) un nombre h(s) ∈ IR qui est
(généralement) une estimation du rapport coût/bénéfice qu'il y a à étendre le
chemin courant en passant par s.

• Contrainte: h(solution) = 0
A
• Le noeud A a 3 successeurs pour lesquels: c(A,b)

b
h(s1) = 0.8 h(s2) = 2.0 h(s3) = 1.6
c(b,k
c(k,n’ k )
• la poursuite de la recherche par s1 n)
est heuristiquement la meilleure ’
c(n’,n
)
g(n)=c(A,b)+c(b,k)+c(k,n’)+c(n’,n) m
n

BUT G h(n)= estimation du coût entre n et

G
 Recherche : Meilleur d’abord (Best First)

Concept
Combinaison de recherche en profondeur et en largeur pour guider la
recherche.
Sélection du prochain nœud basée sur une fonction d'évaluation.
Fonctionnement
Choix du nœud suivant selon sa probabilité de mener à une solution optimale.
Guide la recherche vers les zones les plus prometteuses de l'arbre de
recherche.
Avantages
Orientation vers des solutions potentiellement optimales.
Idée:Efficace dans la recherche dirigée.
étendre le nœud le plus prometteur selon sa valeur heuristique
et d’insérer les successeurs en ordre (dé)croissant en utilisant la valeur heuristique

• Cas particuliers de "best-first search"

o Greedy search (recherche gourmande ou gloutonne )
o A*
 Recherche gourmande (Greedy search)
• Stratégie la plus simple de « best-first search »

• fonction heuristique h(n) = estimation du coût du noeud n au but

• greedy search = minimiser le coût estimé pour atteindre le but

• le nœud qui semble être le plus proche du but sera étendu en priorité

• fonctions heuristiques classiques

– distance à vol d'oiseau
– distance "Manhattan": déplacements limités aux directions verticales et horizontales

Complétude: Non, elle peut être prise dans des cycles. Oui, si l’espace de recherche est fini avec
vérification des états répétés.

Complexité de temps: O(bm), mais une bonne fonction heuristique peut améliorer grandement la situation.

Complexité d’espace: O(bm), elle retient tous les nœuds en mémoire.

Optimale: non, elle s’arrête à la première solution trouvée.

Déroulement d’algorithme greedy

- Q = [a(10)]
Déroulement d’algorithme greedy

d(5
b(12)
) c(4)

- Q = [a(10)]
- dév. : a→ b(12), c(4), d(5)
Déroulement d’algorithme greedy

d(5)
b(12)
c(4)

- Q = [a(10)]
- dév. : a→ b(12), c(4), d(5)
- Q = [c(4),d(5), b(12)]
Déroulement d’algorithme greedy

d(5)
b(12)
c(4)

h(0) g(4)
- Q = [a(10)]
- dév. : a → b(12), c(4), d(5)
- Q = [c(4),d(5), b(12)]
- Dév : c(4) h(0), g(4)
- Q = [h(0), g(4), d(5), b(12)]
- Dév = solution
Déroulement d’algorithme greedy

d(5)
b(12)
c(4)

h(0) g(4)
- Q = [a(10)]
- dév. : a → b(12), c(4), d(5)
- Q = [c(4),d(5), b(12)]
- Dév : c(4) h(0), g(4)
- Q = [h(0), g(4), d(5), b(12)]
- Dév = solution
 Algorithme
A*
• Greedy search minimise le coût estimé h(n) du noeud n au but réduisant ainsi
considérablement le coût de la recherche, mais il n'est pas optimal et pas complet

• l'algorithme de recherche en coût uniforme minimise le coût g(n) depuis l'état initial
au noeud n, il est optimal et complet, mais pas très Efficace

• idée: combiner les deux algorithmes et minimiser le coût total f(n) du chemin passant par le
noeud n A
c(A,b)
f(n) = g(n) + h(n)
b
c(b,k
c(k,n’ k )
n)
’
c(n’,n
)
g(n)=c(A,b)+c(b,k)+c(k,n’)+c(n’,n)
n

BUT G h(n)= estimation du coût entre n et

Exemple: 8_puzzle
g(n) = profondeur du nœud n dans l’arbre de recherche
h1(n) = nombre de carrés mal placés dans ce nœud (sans le carré vide)
h2(n) = somme des distances “manhattan” de chaque carré par rapport à sa destination finale
[sans tenir compte des obstacles]
g(n) est important puisque l’on cherche le chemin le plus court!

- f1(n) = g(n) + h1(n)

- f2(n) = g(n) + h2(n) Meilleure estimation (vis-a-vis du nombre d’étapes avant le but)

2 8 3 1 2 3 B
1 6 4 8 4
7 5 7 6 5 y

f1(n) = g(n) + h1(n) = 0 +( 4) = 4

f2(n) = g(n) + h2(n) = 0 + (1 + 1 + 1 + 2) = 5 x
Une solution optimale prend 5 mouvements
A
f2 est en effet une meilleure estimation que f1
Distance de “Manhattan”(A,B)= |x |+
Dans la vie réelle on utilise aussi l’heuristique:
|y|
Exemple: Au supermarché, on choisit la queue la moins longue ou alors on choisit la
queue dans laquelle les clients ont le plus petit nombre d’objets dans leur panier.
L’Algorithme A*
1.Q ← noeud initial
2.C ← vide
3.répéter
4. si Q est vide, retour avec échec
5. n ← premier élément de Q,
Q ← reste(Q)
6. si n est un noeud but,
retour avec succès (chemin)
7. si n ∉ C ou a un coût inférieur (selon f) alors
8. ajouter n à C (avec repointage)
9. S ← succ(n)
10. Q ← merge(Q,S) ( concaténer Q et S )
11. Q ← Ordo(Q,f)
(Q triée par ordre (dé)croissant de f(n) = g(n) + h(n))
12. finsi
[Link]
Déroulement d’algorithme A*

- Q = [a(10)]
- dév. : a→ b(7+12), c(8+4), d(5+3)
- Q = [d(8), c(12), b(19)]
- dév. : d k(7+2), I(9+1), i(10+4)
- Q = [k(9), I(10), c(12), i(14), b(19)]
- dév. : k e(12+4), m(9+1), I(8+1)
- Q = [I(9), m(10), c(12), i(14), e(16), (b(19)]
- dév. : I n(8+3)
- Q = [m(10), c(12), n(13), i(14), e(16), (b(19)]
- dév. : I n(10+0)
- Q = [n(10), n(11), n(12), c(12), i(14), e(16), (b(19)]
Déroulement d’algorithme A*

d(8)
b(19)
c(12)

- Q = [a(10)]
- dév. : a→ b(7+12), c(8+4), d(5+3)
- Q = [d(8), c(12), b(19)]
- dév. : d k(7+2), I(9+1), i(10+4)
- Q = [k(9), I(10), c(12), i(14), b(19)]
- dév. : k e(12+4), m(9+1), I(8+1)
- Q = [I(9), m(10), c(12), i(14), e(16), (b(19)]
- dév. : I n(8+3)
- Q = [m(10), c(12), n(13), i(14), e(16), (b(19)]
- dév. : I n(10+0)
- Q = [n(10), n(11), n(12), c(12), i(14), e(16), (b(19)]
Déroulement d’algorithme A*

d(8)
b(19)
c(12)

k(9) I(10) i(14)

- Q = [a(10)]
- dév. : a→ b(7+12), c(8+4), d(5+3)
- Q = [d(8), c(12), b(19)]
- dév. : d k(7+2), I(9+1), i(10+4)
- Q = [k(9), I(10), c(12), i(14), b(19)]
- dév. : k e(12+4), m(9+1), I(8+1)
- Q = [I(9), m(10), c(12), i(14), e(16), (b(19)]
- dév. : I n(8+3)
- Q = [m(10), c(12), n(13), i(14), e(16), (b(19)]
- dév. : I n(10+0)
- Q = [n(10), n(11), n(12), c(12), i(14), e(16), (b(19)]
Déroulement d’algorithme A*

d(8)
b(19)
c(12)

k(9) I(10) i(14)

- Q = [a(10)]
- dév. : a→ b(7+12), c(8+4), d(5+3)
- Q = [d(8), c(12), b(19)]
- dév. : d k(7+2), I(9+1), i(10+4) e(16)
- Q = [k(9), I(10), c(12), i(14), b(19)] I(9) m(10)
- dév. : k e(12+4), m(9+1), I(8+1)
- Q = [I(9), I(10), m(10), c(12), i(14), e(16), (b(19)]
- dév. : I n(8+3)
- Q = [m(10), c(12), n(13), i(14), e(16), (b(19)]
- dév. : I n(10+0)
- Q = [n(10), n(11), n(12), c(12), i(14), e(16), (b(19)]
Déroulement d’algorithme A*

d(8)
b(19)
c(12)

k(9) I(10) i(14)

- Q = [a(10)]
- dév. : a→ b(7+12), c(8+4), d(5+3)
- Q = [d(8), c(12), b(19)]
- dév. : d k(7+2), I(9+1), i(10+4) e(16)
- Q = [k(9), I(10), c(12), i(14), b(19)] I(9) m(10)
- dév. : k e(12+4), m(9+1), I(8+1)
- Q = [I(9), I(10), m(10), c(12), i(14), e(16), (b(19)] n(11)
- dév. : I n(8+3)
- Q = [I(10), m(10), n(11), c(12), n(13), i(14), e(16), (b(19)]
- dév. : I n(10+0)
- Q = [n(10), n(11), n(12), c(12), i(14), e(16), (b(19)]
Déroulement d’algorithme A*

d(8)
b(19)
c(12)

k(9) I(10) i(14)

- Q = [a(10)]
- dév. : a→ b(7+12), c(8+4), d(5+3)
- Q = [d(8), c(12), b(19)] n(12)
- dév. : d k(7+2), I(9+1), i(10+4) e(16)
- Q = [k(9), I(10), c(12), i(14), b(19)] I(9) m(10)
- dév. : k e(12+4), m(9+1), I(8+1)
- Q = [I(9), I(10), m(10), c(12), i(14), e(16), (b(19)] n(11)
- dév. : I n(8+3)
- Q = [ m(10), n(11), c(12), n(13), i(14), e(16), (b(19)]
- dév. : I n(10+0)
- Q = [n(10), n(11), n(12), c(12), i(14), e(16), (b(19)]
Déroulement d’algorithme A*

d(8)
b(19)
c(12)

k(9) I(10) i(14)

- Q = [a(10)]
- dév. : a→ b(7+12), c(8+4), d(5+3)
- Q = [d(8), c(12), b(19)] n(12)
- dév. : d k(7+2), I(9+1), i(10+4) e(16)
- Q = [k(9), I(10), c(12), i(14), b(19)] I(9) m(10)
- dév. : k e(12+4), m(9+1), I(8+1)
- Q = [I(9), I(10), m(10), c(12), i(14), e(16), (b(19)] n(11) n(10)
- dév. : I n(8+3)
- Q = [ m(10), n(11), c(12), n(13), i(14), e(16), (b(19)]
- dév. : m n(10+0)
- Q = [n(10), n(11), n(12), c(12), i(14), e(16), (b(19)]
Déroulement d’algorithme A*

d(8)
b(19)
c(12)

k(9) I(10) i(14)

- Q = [a(10)]
- dév. : a→ b(7+12), c(8+4), d(5+3)
- Q = [d(8), c(12), b(19)] n(12)
- dév. : d k(7+2), I(9+1), i(10+4) e(16)
- Q = [k(9), I(10), c(12), i(14), b(19)] I(9) m(10)
- dév. : k e(12+4), m(9+1), I(8+1)
- Q = [I(9), I(10), m(10), c(12), i(14), e(16), (b(19)] n(11) n(10)
- dév. : I n(8+3)
- Q = [ m(10), n(11), c(12), n(13), i(14), e(16), (b(19)]
- dév. : m n(10+0)
- Q = [n(10), n(11), n(12), c(12), i(14), e(16), (b(19)]
- Dev = n(10) solution le chemin solution est : a d k m n
 Admissibilité
•A* utilise une heuristique admissible h, c’est-à-dire h(n) ≤ h*(n), où h*(n) est le véritable coût pour se rendre de
n au but.
•A* Demande aussi que h(n) ≥ 0 et que h(G) = 0 pour tous les buts G.
Dominance
Si h2(n) ≥ h1(n) pour tout n (les deux étant admissibles), alors h2 domine h1 et par conséquent h2 est meilleure
que h1.

Il est toujours préférable de choisir l’heuristique dominante, car elle va développer moins de nœuds

Théorème1 : si A* utilise une fonction heuristique admissible, c-à-d qui ne surestime jamais le coût réel
alors A* est optimal
Théorème2 : Si A2* est mieux informé que A1*, alors lorsque leurs recherches sont terminées, tous les
nœuds développés par A2* l’ont également été par A1* (et peut-être d’autres). A2* est plus efficace que
A 1*
une fonction heuristique admissible est toujours optimiste!
• exemple: vol d'oiseau(n) ne surestime jamais la distance
réelle.
FONCTION HEURISTIQUE CONSISTANTE

Une heuristique h est consistante (monotone) si

1. Pour tout nœud N et tout nœud successeur N’ de N :

N
h(N) ≤ c(N,N’) + h(N’)
c(N,N’
2. Pour tout nœud BUT G: )
N
’ h(N
h(G) = 0 )

h(N’
)

G
Intelligence Artificielle Recherche

Propriétés de A*

Complétude: oui, à moins qu’il y est une infinité de nœuds

avec f ≤ f(but).

Complexité de temps: exponentielle selon la longueur de la

solution.

Complexité en espace: elle garde tous les nœuds en mémoire:

exponentielle selon la longueur de la solution.

Optimale: Oui Habituellement, on manque d’espace longtemps

avant de manquer de temps.
Intelligence Artificielle Recherche

Variantes de A*
• les problèmes réels sont très complexes
• l'espace de recherche devient très grand
• même les méthodes de recherche heuristiques deviennent inefficaces
• A* connaît alors des problèmes de place-mémoire

2 variantes de A*:
– IDA* = A* avec approfondissement itératif
qui est un algorithme A* qui effectue des approfondissements successifs en rapport avec des
valeurs limites pour f(n) ; IDA* est complète et optimale et sa complexité en espace mémoire est
de l`ordre O(b×d)
– SMA* = A* avec gestion de mémoire
qui est un algorithme A* qui effectue la gestion de sa propre mémoire disponible: élimine les
nœuds ayant les valeurs de f(n) plus élevées quand la file ordonnée est pleine. L’algorithme
SMA* est complet si l`espace mémoire disponible est suffisant pour contenir le chemin:
état initial – état solution.
L’algorithme SMA* retourne toujours la meilleure solution qui peut être obtenue avec l’espace
mémoire alloué.
Exercice 1 (suite)

• Meilleur d’abord gourmande

• A*

L’Algorithme A*

1.Q ← noeud initial

2.C ← vide
3.répéter
4. si Q est vide, retour avec échec
5. n ← premier élément de Q,
Q ← reste(Q)
6. si n est un noeud but,
retour avec succès (chemin)
7. si n ∉ C ou a un coût inférieur (selon f) alors
8. ajouter n à C (avec repointage)
9. S ← succ(n)
10. Q ← merge(Q,S) ( concaténer Q et S )
11. Q ← Ordo(Q,f)
(Q triée par ordre (dé)croissant de f(n) = g(n) +
h(n))
12. finsi
[Link]
Dans quel ordre les noeuds sont développés pour chacun des algorithmes?
Exercice 2
Considérez le plan suivant ou les successeurs de chaque case sont les cases adjacentes dans les directions
Nord, Sud, Est et Ouest sauf à la limite du plan ou s'il y a une barrière (ligne épaisse). Par exemple
successeurs(J) = {D, K, F}. On suppose que chaque opérateur (N,S,E,O) à coût 1.

Le problème est de trouver un chemin de S vers F. On suppose que les successeurs sont engendrés dans
l'ordre Est, Sud, Ouest et Nord.
Donnez l'ordre des noeuds développés pour les 4 méthodes de recherche suivante:

1. Recherche en largeur d'abord, Coût Uniforme profondeur d'abord, et Profondeur itérative.

On suppose qu'on détecte des cycles, c.-à-d. on ne développe pas un noeud déjà développé avant.
Exercice 2 (suite)

2. Recherche gourmande. On utilise l'heuristique h(case) = distance de Manhattan de la case avec la case F
en supposant qu'il n'y a pas de barrière. Par exemple h(I) = 2 et h(S) = 4. Si deux noeuds ont la même
valeur, c'est d'abord celui qui est le premier dans l'alphabet qui est développé.

3. Recherche A* avec même heuristique que pour la recherche gourmande.

.

Questions diverses (Justifiez vos réponses):

Est-ce que h est admissible ?

Est-ce que h2(n) = min(2; h(n)) est admissible ?

Est-ce que h3(n) = max(2; h(n)) est admissible ?

 Algorithmes des
(application des méthodes de
jeux
recherche)

• Pourquoi étudier les jeux?

• Algorithme MiniMax

• MiniMax avec élagage α-β

AIMA chapitre 6
• 2 joueurs: MAX et MIN jouant à tour de rôle (MAX joue en
premier)

• Espace d’états

• État initial

• Fonction « successeur » (règles de jeu)

• Test de fin de partie

• Fonction « score » indique si un état terminal est un état de

gain (pour
MAX), de perte ou de nul

• Connaissance parfaite des états, pas d’incertitude dans l’effet

Fonction d'évaluation pour un état
du jeu
• e(s) = + ∞ si s est une situation de gain pour Max
• e(s) = - ∞ si s est une situation de gain pour Min
• e(s) = une mesure du caractère "favorable" de s pour Max
> 0 si s est considéré favorable pour Max
< 0 si non

• exemple: Tic-Tac-Toe (Morpion)

e(s) = (# lignes/cols/diags ouvertes pour Max) - (# lignes/cols/diags ouvertes pour Min)

Il faut disposer d'une fonction d'évaluation statique capable de mesurer la qualité d'une configuration
par rapport à un joueur (gé[Link])

– car il n'est pas possible de produire tout l'arbre de recherche jusqu'à la fin du jeu, càd au moment où la
décision gain/perte/nul est claire.
Principe: maximiser la valeur d'utilité pour Max avec l'hypothèse que Min joue
parfaitement pour la minimiser,

– étendre l'arbre de jeu

– calculer la valeur de la fonction de gain pour chaque noeud terminal
– propager ces valeurs aux noeuds non-terminaux:
• la valeur minimum (adversaire) aux noeuds MIN
• la valeur maximum (joueur) aux noeuds MAX

Formulation récursive de MiniMax

• Fonction MiniMax (noeud,profondeur)

– si profondeur = 0, retourner évaluation(noeud)

– si c'est à MAX de jouer à ce noeud, retourner max MiniMax(n, profondeur - 1)
– si c'est à MIN de jouer à ce noeud, retourner min MiniMax(n, profondeur - 1)

• ceci est calculé de manière "en profondeur" par l'utilisation d'une pile des appels récursifs.
Exemple:
Tic-Tac-Toe
e(s) = (# lignes/cols/diags ouvertes pour Max) - (# lignes/cols/diags ouvertes
pour Min)

Max

Min
Algorithme MiniMax

Algorithmes de remontée des étiquettes numériques

❏ Si noeud Max : On remonte le Max des valeurs des

successeurs

❏ Si nœud Min : On remonte le Min des valeurs des

successeurs

❏ Si nœud Feuille alors valeur de la fonction d’évaluation

Exercice : jeux
1- MiniMax

Max
16

16 4 Min
15

15 19 16 17 4 23 Max
Réduction de
l’espace
Élagage α-
βPrincipe
• étendre l'arbre de jeu jusqu'à une profondeur h par recherche en profondeur
• ne plus générer les successeurs d'un noeud dès qu'il est évident que ce noeud ne sera pas choisi (compte tenu
des noeuds déjà examinés)
• chaque noeud Max garde la trace d'une α-valeur = valeur de son meilleur successeur trouvé jusqu'ici
• chaque noeud Min garde la trace d'une β-valeur = valeur de son plus mauvais successeur trouvé jusqu'ici
• valeurs initiales: α = - ∞ β = + ∞
2 règles
1. Interrompre la recherche d'un noeud Max si son α-valeur ≥ β-valeur de son
noeud-parent
Max

2. Interrompre la recherche d'un noeud Min si sa β-valeur ≤ α-valeur de son

noeud-parent

Max
Algorithme α – β (version
française)
Propriétés de α -
β
• L'élagage n'affecte pas le résultat final,

• l'efficacité de l'élagage α - β est fonction de l'ordre d'apparition des noeuds successeurs,

complexité en temps

• meilleur des cas: O(bm/2)

– permet de doubler la profondeur de recherche pour atteindre une prédiction sur 8 niveaux et ainsi jouer
"dignement" aux échecs

• pire des cas: identique à MiniMax

• cas moyen: O((b/logb)m ) [Knuth&Moore 75]

Variantes de Alpha-Beta
• Approfondissements itératifs
• Étendre les noeuds singuliers (ceux qui présentent un intérêtparticulier) en
priorité
Autres types de jeux

• Jeux à plusieurs joueurs (> 2), avec ou sans alliance (online par exemple)

• Jeux avec intervention du hasard dans la fonction « successeur » (ex

lancer un dé)

• États partiellement connus (ex jeux de cartes)

Exercice : jeux
1- MiniMax
2- Alpha-Beta

16 Max
(-,+ (15,+)
(16,+)
)

(-,+
) (15,+)
(-,15 (15,16) (16,+) Min
(16,16)
)

(-,15 (15,+) (15,16) (16,+)

(-,+
) (15,+) ) Max
(19,15) (16,+) (17,16) (16,+)
Exercice
Utiliser Alpha-Beta
Extensions
Plus de deux joueurs
On peut traiter un jeu à plus de deux joueurs avec un algorithme classique de type
minimax à condition d’effectuer quelques modifications.
- au lieu de manipuler une valeur v, on va manipuler un vecteur de valeurs v1,…,vn
(une par joueur). Remarque : à deux joueurs on ne représentait qu’une valeur car
le jeu étant à somme nulle, l’une dépendait de l’autre. Maintenant, ce n’est plus le
cas.

- A chaque noeud, on fait remonter le vecteur de valeurs le plus favorable au joueur qui
doit jouer à ce moment là. Donc, le vecteur où ce joueur a un vi maximal.
Exemple : jeu à 3 joueurs
Kasparov vs IBM Deep blue

1997: Deep Blue gagne par 3 victoires, 1 défaite, et 2 nuls

2 Août 2003: Égalité (3-3)!

 Ke Jie contre AlphaGo

Mai 2017: L’IA AlphaGo (de DeepMind) défait Ke Jie (1e mondial) par
3 jeux à 0
Défis
•Jeux stratégies en temps réel combinant éléments discrets et continus.
-StarCraft
•Jeux avec lois de la physiques.
–Angry Bird
–Billard
•Méthodes probabilistes
–Random search trees, Monte Carlo, Échantillonnage (sampling), etc.
Apprentissage Par renforcement

En Résumé:
• Il est amusant de pratiquer l’IA avec les jeux.
• Les recherches sur les jeux révèlent des aspects fondamentaux
intéressants applicables à d’autres domaines.
• La perfection est généralement inatteignable dans les jeux : il faut
approximer.
• Aujourdui (2024) vise à explorer ce domaine propice.
FIN