1.

1 Concepts IA: Résolution de problèmes

Jean-Charles Régin

Master Informatique 1ère année

JC Régin - Concepts IA
 But du cours
1.2

 Vous faire comprendre que les ordinateurs peuvent aussi

être utilisés pour résoudre des problèmes complexes
 Il n’y a pas que le web et la video !
 Utilisation intelligente de la puissance de calcul
 Qu’il est important de faire des codes sans bugs (ou
avec le moins possible)

JC Régin - Concepts IA
1.3 Introduction

JC Régin - Concepts IA
 Graphe : définitions
1.4

 Un Graphe Orienté G=(X,U) est déterminé par la

donnée :
 d’un ensemble de sommets ou nœuds X
 d’un ensemble ordonné U de couples de sommets appelés
arcs.
 Si u=(i,j) est un arc de G alors i est l’extrémité initiale de
de u et j l’extrémité terminale de u.
 Les arcs ont un sens. L’arc u=(i,j) va de i vers j.
 Ils peuvent être munit d’un coût, d’une capacité etc…
JC Régin - Concepts IA
 Graphe
1.5

JC Régin - Concepts IA
 Graphe
1.6

 On note par (i) : l’ensemble des arcs ayant i comme

extrémité
 On note par +(i) : l’ensemble des arcs ayant i comme
extrémité initiale = ensemble des arcs sortant de i
 On note par -(i) : l’ensemble des arcs ayant i comme
extrémité terminale = ensemble des arcs entrant dans i
 N(i) : ensemble des voisins de i : ensemble des sommets j
tels qu’il existe un arc contenant i et j

JC Régin - Concepts IA
 Graphe non orienté
1.7

 Un Graphe non orienté G=(X,E) est déterminé par la

donnée :
 d’un ensemble de sommets ou nœuds X
 D’un ensemble E de paires de sommets appelées arêtes

 Les arêtes ne sont pas orientées

JC Régin - Concepts IA
 Graphe non orienté
1.8

JC Régin - Concepts IA
 Graphe : définitions
1.9

 Deux sommets sont voisins s’ils sont reliés par un arc ou

une arête
 Degré entrant d’un sommet i : nombre d’arcs ayant i
comme extrémité terminale = nombre d’arc entrant dans
i
 Degré sortant d’un sommet i : nombre d’arcs ayant i
comme extrémité initiale = nombre d’arcs sortant de i

JC Régin - Concepts IA
 Graphe : définitions
1.10

 Chemin de longueur q : séquence de q arcs

{u1,u2,…,uq} telle que
 u1=(i0,i1)

 u2= (i1,i2)
 uq=(iq-1,iq)

 Chemin : tous les arcs orientés dans le même sens

 Circuit : chemin dont les extrémités coïncident

JC Régin - Concepts IA
1.11 Problèmes de cheminement

JC Régin - Concepts IA
 Plan
1.12

 Graphe d’état
 Cheminement dans un graphe (DFS, BFS)
 Plus court chemin entre deux points
 Algorithme de Dijkstra
 Graphe trop grand : algorithme A*
 Applications

JC Régin - Concepts IA
 Graphe d’état
1.13

 De nombreux problèmes peuvent être résolu en définissant le

graphe d’état
 Un nœud = un état possible
 Un arc = le passage autorisé d’un état à un autre
 En général on a deux états particuliers
 État initial
 État final

 La solution du problème devient simple : c’est un chemin dans

le graphe de l’état initial vers l’état final
 La difficulté est la représentation du graphe d’état

JC Régin - Concepts IA
 Graphe d’état
1.14

 Problème de la chèvre, du loup et de la salade

 Un fermier doit passer transporter de l’autre côté d’une
rivière, un loup, une chèvre et une salade
 La rivière est traversée dans une barque juste assez grande
pour lui et le loup, ou lui et sa chèvre, ou lui et sa salade.
 La salade sera mangé s'il la laisse seule avec la chèvre,

 La chèvre sera mangée s'il la laisse seule avec le loup.

 Comment faire passer tout ce monde sans dégâts ?

JC Régin - Concepts IA
 Graphe d’état
1.15

 Définissons les états :

 On a 3 choses et 2 bords de rivière et le placement
courant de la barque. Loup (L), Chèvre (C), Salade (S)
 (G=(B,C,L) D=(S)) sens ?
 Certains états sont impossibles
 (G=(C,L) D=(B,S)) le loup va manger la chèvre
 (G=(B,C,L) D=(S)) est ok carle fermier surveille le loup et la
chèvre

JC Régin - Concepts IA
 Graphe d’état
1.16

 On fait tous les états possibles, puis on les relie entre

eux si cela est possible
 (G=(B,C,L) D=(S)) peut etre relié à
 (G=(C,L)D=(B,S)) la barque a juste changé de côté
 (G=(L) D=(B,C,S)) la chèvre a traversé

 (G=(C) D=(B,L,S)) le loup a traversé

JC Régin - Concepts IA
 Graphe d’états
1.17

 2 côtés et 4 objets. Pour chaque objet on a 2 possibilités, il y a donc 24=16 états possibles :
 (G=(B,C,L,S) D=()) ok ETAT INITIAL
 (G=(B,C,L) D=(S)) ok
 (G=(B,C,S) D=(L)) ok
 (G=(B,L,S) D=(C)) ok
 (G=(C,L,S) D=(B)) interdit
 (G=(B,C) D=(L,S)) ok
 (G=(B,L) D=(C,S)) interdit
 (G=(B,S) D=(C,L)) interdit
 (G=(C,L) D=(B,S)) interdit
 (G=(C,S) D=(B,L)) interdit
 (G=(L,S) D=(B,C)) ok
 (G=(B) D=(C,L,S)) interdit
 (G=(C) D=(B,L,S)) ok
 (G=(L) D=(B,C,S)) ok
 (G=(S) D=(B,C,L)) ok
 (G=() D=(B,C,L,S)) ok ETAT FINAL

JC Régin - Concepts IA
 Graphe d’états
1.18

 2 côtés et 4 objets. Pour chaque objet on a 2 possibilités, il y a donc 24=16 états possibles :
 (G=(B,C,L,S) D=()) ok ETAT INITIAL
 (G=(B,C,L) D=(S)) ok
 (G=(B,C,S) D=(L)) ok
 (G=(B,L,S) D=(C)) ok
 (G=(C,L,S) D=(B)) interdit
 (G=(B,C) D=(L,S)) ok
 (G=(B,L) D=(C,S)) interdit
 (G=(B,S) D=(C,L)) interdit
 (G=(C,L) D=(B,S)) interdit
 (G=(C,S) D=(B,L)) interdit
 (G=(L,S) D=(B,C)) ok
 (G=(B) D=(C,L,S)) interdit
 (G=(C) D=(B,L,S)) ok
 (G=(L) D=(B,C,S)) ok
 (G=(S) D=(B,C,L)) ok
 (G=() D=(B,C,L,S)) ok ETAT FINAL

JC Régin - Concepts IA
 Graphe d’états
1.19

 On dessine maintenant le graphe des états !

JC Régin - Concepts IA
 Graphe d’états
1.20

 Un détachement de soldats arrive devant une rivière. Le

pont a sauté, et le courant est trop fort pour que l'on s'y
risque à la nage. Le capitaine réfléchit, et aperçoit un
petit bateau manœuvré par deux garçons. Il le
réquisitionne, mais s'aperçoit que le bateau est
 justeassez grand pour un seul soldat ou deux enfants,
 trop petit pour un soldat et un enfant.

 Le capitaine, cependant, trouve une solution. Laquelle ?

JC Régin - Concepts IA
 Graphe d’états
1.21

 On fait le graphe d’états

 Mais le nombre de soldats n’est pas défini, alors
comment peut-on faire ?

JC Régin - Concepts IA
 Graphe d’états
1.22

 On fait le graphe d’états

 Mais le nombre de soldats n’est pas défini, alors
comment peut-on faire ?

 Essayons de faire passer un soldat et de revenir à l’état

initial
 Donc on commence avec 1 soldat et 2 enfants et on
essaie de faire traverser le soldat et de ramener les 2
enfants sur la rive initiale
JC Régin - Concepts IA
 Graphe d’états
1.23

 On définit donc les états

 (G=(B,S,E1,E2) D=()) état initial
 (G=(B,E1,E2) D(S)) état final

 On énumère les autres états, on fait le graphe et on

cherche un chemin de l’état initial à l’état final.
 Ensuite on répétera cette solution pour tous les soldats !

JC Régin - Concepts IA
 Graphe d’états
1.24

 Le problème de l’échange de cavaliers aux échecs

 On veut passer de la gauche vers la droite

JC Régin - Concepts IA
 Graphe d’états
1.25

 Le problème de l’échange de cavaliers aux échecs

 On veut passer de la gauche vers la droite
1 2 3

4 5 6

7 8 9

JC Régin - Concepts IA
 Graphe d’états
1.26

 On dessine les mouvements possibles de cases en case

1
8 6

3 7

4 2

JC Régin - Concepts IA
 Plan
1.27

 Graphe d’état
 Cheminement dans un graphe (DFS, BFS)
 Plus court chemin entre deux points
 Algorithme de Dijkstra
 Graphe trop grand : algorithme A*
 Applications

JC Régin - Concepts IA
 Arbre
1.28

 Un arbre (tree en anglais) est un graphe non orienté

connexe et sans cycle

 Un graphe non orienté G ayant n sommets est un arbre

est équivalent à l’une des deux propriétés
G est connexe et a n-1 arêtes
 G n’a pas de cycle et a n-1 arête.

JC Régin - Concepts IA
 Arbre
1.29

JC Régin - Concepts IA
 Arbre
1.30

 La racine r de l'arbre est l'unique nœud ne possédant pas

de parent

 Tout sommet x qui n’est pas la racine a

 un unique parent, noté parent(x) (appelé père parfois)
 0 ou plusieurs fils. fils(x) désigne l’ensemble des fils de x
 Si x et y sont des sommets tels que x soit sur le chemin de r à
y alors
 x est un ancêtre de y
 y est un descendant de x
 Un sommet qui n’a pas de fils est une feuille

JC Régin - Concepts IA
 Arbre
1.31

1 est la racine
9,10,6,3,11,12,8 sont les feuilles
11 est un descendant de 4, mais pas de 2- Concepts IA
JC Régin
2 est un ancêtre de 10
 Arbre
1.32

 Quand il n’y a pas d’ambiguïté, on regarde les arêtes

d’un arbre comme étant orienté de la racine vers les
feuilles

 La profondeur d’un sommet (depth) est définie

récursivement par
 prof(v) = 0 si v est la racine
 prof(v) = prof(parent(v)) + 1

JC Régin - Concepts IA
 Arbre
1.33

1 est la racine
2,3,4 sont à la profondeur 1
5,6,7,8 à la profondeur 2 JC Régin - Concepts IA
La hauteur de 2 est 2, celle de 9 est 0, celle de 3 est 0, celle de 1 est 4
 Arbre : parcours
1.34

 Parcours (tree traversal) : on traverse l’ensemble des

sommets de l’arbre

 Parcours en largeur d’abord

 Parcours en profondeur d’abord
 Préfixé

 Infixé

 Postfixé

JC Régin - Concepts IA
 Arbre : parcours en largeur d’abord
1.35

 Largeur d’abord (bfs = breadth-first search)

 On visite la racine, puis on répète le processus suivant
jusqu’à avoir visité tous les sommets :
visiter un fils non visité du sommet le moins récemment
visité qui a au moins un fils non visité

 On visite tous les sommets à la profondeur 1, puis tous

ceux à la profondeur 2, puis tous ceux à la profondeur
3 etc…
JC Régin - Concepts IA
 Arbre
1.36

Largeur d’abord: ordre de visite

1, 2 ,3 ,4 ,5, 6 , 7, 8, 9 , 10 ,11 ,12
JC Régin - Concepts IA
 Arbre : largeur d’abord
1.37

 Bfs(T) : array
r  racine(T)
créer un file F et ajouter r dans F
i0
tant que (F n’est pas vide)
x  premier(F); supprimer x de F
array[i]  x
i++
pour chaque fils y de x
ajouter y dans F
fin pour
fin tant que

JC Régin - Concepts IA
 Arbre : largeur d’abord avec passes
1.38

 Bfs(T) : array
r  racine(T)
créer deux files F1 et F2 et ajouter r dans F1
i0
faire
tant que (F1 n’est pas vide)
x  premier(F1); supprimer x de F1
array[i]  x
i++
pour chaque fils y de x
ajouter y dans F2
fin pour
fin tant que
F1  F2 // fin d’une passe début de la nouvelle : la
F2 devient vide // profondeur change
tant que F1 n’est pas vide

JC Régin - Concepts IA
 Arbre
1.39

Largeur d’abord: ordre de visite

Passe 1 : 1
Passe 2 : 2,3,4 JC Régin - Concepts IA
Passe 3 : 5,6,7,8 et passe 4 : 9,10,11,12
 Arbre parcours en profondeur d’abord
1.40

 Profondeur d’abord (dfs = depth-first search)

 Défini de façon récursive

 visit(sommet x)
previsit(x)
pour chaque fils y de x
visit(y)
postvisit(x)
 Premier appel : visit(racine(T))
JC Régin - Concepts IA
 Abre : profondeur d’abord
1.41

 Ordre préfixé ou postfixé dépend des fonction previsit

et postvisit
 Si previsit(x) : met x dans le array et incremente i alors
array contient l’ordre préfixé
 Si c’est postvisit qui le fait alors array contiendra l’ordre
postfixé

JC Régin - Concepts IA
 Arbre
1.42

Profondeur d’abord: ordre de visite préfixé

On marque quand on atteint le noeud
1 ,2 ,5, 9, 10, 6, 3, 4, 7, 11, 12, 8 JC Régin - Concepts IA
 Arbre
1.43

Profondeur d’abord: ordre de visite postfixé

On marque quand on quitte le noeud
9, 10, 5, 6, 2, 3, 11, 12, 7, 8, 4, 1 JC Régin - Concepts IA
 Arbre : profondeur d’abord
1.44

 Dfs(T) : array
r  racine(T)
créer une pile P et ajouter r dans P
i0
tant que (P n’est pas vide)
x  premier(P); supprimer x de P
array[i]  x
i++
pour chaque fils y de x
ajouter y dans P
fin pour
fin tant que

JC Régin - Concepts IA
 Arbre : implémentation
1.45

 Représentation des fils

 Par une liste :
◼ Le parent possède un premier fils
◼ Chaque sommet possède un pointeur vers son frère suivant (liste
chaînée des fils)
 Par un tableau si le nombre de fils est connu à l’avance
(arbre k-aire)
 Dans le cas binaire, le parent possède le fils gauche et le fils
droit

JC Régin - Concepts IA
 Cheminement dans un graphe
1.46

 Les algorithmes que l’on a vu pour les arbres (DFS et

BFS) peuvent s’appliquer aux graphes
 Il faut faire un peu attention
 On ne doit pas visiter deux fois le même sommet

JC Régin - Concepts IA
 Illustration of BFS
47
0 1
0
2
1 2 4
9 4
5 9 10
5 7
10
11
6 7 8 11 8
6
BFS Tree Graph G

JC Régin - Concepts IA
 Graphe : largeur d’abord
1.48

 Bfs(G,s) : array
rs
pour tous les sommets x marque[x]  faux
créer un file F; enfiler(F,r); marque[r]  vrai
i0
tant que (F n’est pas vide)
x  premier(F); defiler(F)
array[i]  x
i++
pour chaque voisin y de x
si marque[y] est faux
alors marque[y]  vrai
enfiler(F,y)
fin pour
fin tant que

JC Régin - Concepts IA
 Illustration of DFS
49
0 1
0
2
1
9 4
4
5 7
2 10
11
9 8
5
6
7 11
6 Graph G
8 10

DFS Tree

JC Régin - Concepts IA
 Plan
1.50

 Graphe d’état
 Cheminement dans un graphe (DFS, BFS)
 Plus court chemin entre deux points
 Algorithme de Dijkstra
 Graphe trop grand : algorithme A*
 Applications

JC Régin - Concepts IA
 Plus court chemin entre deux points
1.51

 On introduit maintenant une longueur sur les arcs

 Le coût sur les arcs peut être appelé différement
 Distance

 Poids

 Coût

…

 Ce qui est important ce que la longueur d’un chemin

est égal à la somme des longueurs des arcs qui le
compose
JC Régin - Concepts IA
 Plus court chemin entre deux points
1.52

 On Supposera que tous les coûts sont positifs

 Ce n’est pas une obligation : on peut très bien calculer le
plus court chemin avec des coûts négatifs, mais ce
problème sort du cadre de ce cours

JC Régin - Concepts IA
 Chemin de A vers J
1.53

JC Régin - Concepts IA
 Plus court chemin
1.54

 On ne peut pas énumérer tous les chemins

 On se place dans le cas où toutes les longueurs sont
positives
 Un algorithme glouton existe !

JC Régin - Concepts IA
 Algorithme de Dijkstra
1.55

 On maintien en permanence la distance des sommets avec l’origine

 On a trois ensembles de sommets
 Les ouverts (ce sont les candidats pour la prochaine étape)
◼ On peut les atteindre en passant par des sommets précdemment choisis
 Les fermés : ce sont des sommets qui ont été choisis
 Les indéfinis : pour l’instant on ne peut pas les atteindre
 A chaque étape on choisit le sommet ouvert situé à la plus petite distance
 On regarde les sommets qui sont reliés à ce sommet
 Ceux qui sont indéfinis deviennent ouvert et on calcule leur distance
 Ceux qui sont ouverts ont leur distance modifiée
 On ferme le sommet

JC Régin - Concepts IA
 Chemin de A vers J
1.56

A est ouvert
Sommets reliés à A : B,C et E
Ils sont ouverts avec
D(A,B) ≤ 85
D(A,C) ≤ 217
D(A,E) ≤ 173
Ouvert={B,E,C}

JC Régin - Concepts IA
 Chemin de A vers J
1.57

On ajoute le sommet ouvert

à la plus petite distance
Ici c’est B. On ferme B
On s’intéresse aux voisins de B
Il y a F : on ouvre F
D(A,F) ≤ d(A,B) + d(B,F) ≤ 165
Ouvert = {F,E,C}

JC Régin - Concepts IA
 Chemin de A vers J
1.58

On choisit F. On le ferme
On ouvre I
D(A,I) ≤ d(A,F) + d(F,I) ≤ 415
Ouverts = {E,C,I}

JC Régin - Concepts IA
 Chemin de A vers J
1.59

On choisit E. On le ferme
On ouvre J
D(A,J) ≤ d(A,E) + d(E,J) ≤ 675
Ouverts = {C,I,J}

JC Régin - Concepts IA
 Chemin de A vers J
1.60

On prend C
On ouvre G et H
Ouverts = {H,G,I,J}

JC Régin - Concepts IA
 Chemin de A vers J
1.61

On prend H
On met à jour J

JC Régin - Concepts IA
 Chemin de A vers J
1.62

On prend G

JC Régin - Concepts IA
 Chemin de A vers J
1.63

On prend I

JC Régin - Concepts IA
 Chemin de A vers J
1.64

On prend J
Fin de l’algorithme

JC Régin - Concepts IA
 Dijkstra
1.65

 maj_distances(s1,s2)
si d[s2] > d[s1] + longueur(s1,s2)
alors d[s2]  d[s1] + longueur(s1,s2)
 Dijkstra(G,Poids,sdeb)
Ouvert  {s}
tant que Ouvert ≠ et t n’est pas fermé
faire i  Trouve_min(Ouvert)
supprimer i de Ouvert
fermer(i)
pour chaque nœud k voisin de i
faire si k n’est pas fermé
alors ajouter k dans Ouvert s’il n’y était pas déjà
maj_distances(i,k)
fait
fait
 Pour trouver le chemin il faut garder le predecesseur (celui qui a mis à jour la
distance min)

JC Régin - Concepts IA
 Algorithme de Dijkstra
1.66

 La difficulté vient de la détermination du sommet situé à

la plus petite distance
 Queue de Priorité

JC Régin - Concepts IA
 Plan
1.67

 Graphe d’état
 Cheminement dans un graphe (DFS, BFS)
 Plus court chemin entre deux points
 Algorithme de Dijkstra
 Graphe trop grand : algorithme A*
 Applications

JC Régin - Concepts IA
 Graphe et solution
1.68

 De nombreux problèmes se résolvent facilement si l’on

arrive à trouver un plus court chemin d’un sommet s vers
un sommet t.
 Dans certains cas, on a n’arrive pas à définir le graphe
parce qu’il est trop grand. Pour diverses raisons
 Il
peut être dynamique (il change)
 On ne sait pas tout

 On se promène dans un graphe d’état gigantesque !

JC Régin - Concepts IA
 Problème avec le graphe
1.69

 On va essayer de limiter l’explosion combinatoire (la

taille du graphe)
 On va construire se promener dans le graphe et on va le
construire au fur et à mesure
 PourDijkstra on a juste besoin des voisins d’un sommet
 Mais on voudrait ne pas avoir trop de nœuds ouvert

 Comment limiter le nombre de sommets ouverts ?

 Avec un guide !
JC Régin - Concepts IA
1.70

 On se donne une fonction f capable d'évaluer un noeud

et définie comme suit :
 f(s,n,t) = g(s,n) + h(n,t)avec
 g(s,n) la longueur du meilleur chemin connu pour
atteindre n depuis s
 h(n,t) l'estimation du coût du chemin entre n et t

 f(s,n,t) est donc une estimation du coût du meilleur

chemin solution de s à t passant par n.

JC Régin - Concepts IA
1.71

 A quoi cela sert-il ?

 DansDijkstra on ne fait que regarder la distance par
rapport au début
◼ On sélectionne le nœud le plus proche du début
◼ On met à jour cette distance
 Avec l’algorithme A*
◼ On sélectionne le nœud qui a le plus petit f
◼ On met à jour g

 On évite à la recherche de partir dans toutes les

directions : on la focalise vers le but

JC Régin - Concepts IA
 Algorithme A*
1.72

JC Régin - Concepts IA
 Algorithme A*
1.73

JC Régin - Concepts IA
 Algorithme A*
1.74

JC Régin - Concepts IA
 Algorithme A*
1.75

JC Régin - Concepts IA
 Algorithme A*
1.76

JC Régin - Concepts IA
 Algorithme A*
1.77

JC Régin - Concepts IA
 Algorithme A*
1.78

JC Régin - Concepts IA
 Algorithme A*
1.79

 maj_distances_g(s1,s2)
si g[s2] > g[s1] + longueur(s1,s2)
alors g[s2]  g[s1] + longueur(s1,s2)
 Dijkstra(G,Poids,sdeb)
Ouvert  {s}
tant que Ouvert ≠ et t n’est pas fermé
faire i  Trouve_min_f(Ouvert)
supprimer i de Ouvert
fermer(i)
pour chaque nœud k voisin de i
faire si k n’est pas fermé
alors ajouter k dans Ouvert s’il n’y était pas déjà
maj_distances_g(i,k)
fait
fait
 Pour trouver le chemin il faut garder le predecesseur (celui qui a mis à jour la
distance min)

JC Régin - Concepts IA
 Algorithme A*
1.80

 Comment trouver et relier f, g et h ?

 si h=0, alors f(n)=g(n) et l'algorithme se comporte comme
une largeur d'abord
 si f(n) = h(n), l'algorithme ressemble à une profondeur
d'abord, on parle de gradient
 Propriétés de h et de l'algorithme A*
h est dite minorante si pour tout noeud n, on a h(n) inférieure
ou égale à h*(n) ;
 si h est minorante alors l'algorithme A* est admissible (il
trouvera la solution optimale)

JC Régin - Concepts IA
 Algorithme A* : Beam Search
1.81

 Même si l'algorithme A* ne développe pas systématiquement

l'arbre de résolution, le nombre de noeuds ouverts peut devenir
prohibitif.
 Une solution est de ne garder dans les ouverts que les k meilleurs
noeuds.
 On parle alors de beam search.

 Inconvénients
 On risque de ne pas obtenir la meilleure solution
 On risque de ne pas trouver de solution
 Avantage
 On réduit l’explosion combinatoire

JC Régin - Concepts IA
 IDDFS : Iterative Deepening DFS
1.82

 C’est une répétition de DFS à profondeur limité.

 On fait une DFS avec une limite de profondeur égale à 1
 On fait une DFS avec une limite de profondeur égale à 2
…
 On fait une DFS avec une limite de profondeur égale à k

 Cela permet de mélanger une DFS et une BFS.

 C’est intéressant avec les algorithmes de jeu car on a un peu
plus un aperçu en largeur, autrement dit de l’ensemble des
possibilités avant d’aller trop profondemment

JC Régin - Concepts IA
 IDDFS
1.83

Profondeur max = 0
A

Profondeur max = 1
A, B, C, E

Profondeur max = 2
A, B, D, F, C, G, E

DFS : A, B, D, F, E, C, G (C est visité tard)

BFS : A, B, C, E, D, F, G

JC Régin - Concepts IA
1.84 Enumération de l’espace de recherche

JC Régin - Concepts IA
 Coloriage de graphes
1.85

 Algorithme reliement-contraction : on fait l’énumération

de l’espace de recherche
 Il existe plusieurs types d’algorithme généraux
 Brute force search
 Backtrack

 Programmation par contraintes

JC Régin - Concepts IA
 Brute force search
1.86

 Brute force search

 = Exhaustive search
 = Generate and test

 Consiste à énumérer toutes les combinaisons possibles et à

vérifier si ce sont des solutions
 N-queens problems. On fait toutes les combinaisons et on teste
 c first(P)
tant que c ≠ Λ faire
si valid(P,c) alors retourner c
sinon c  next(P,c)
JC Régin - Concepts IA
 Brute force search
1.87

 Rarement intéressant
 Uniquement dans le cas ou le nombre de combinaisons
est faible

JC Régin - Concepts IA
 Backtrack Search
1.88

 L’algorithme de backtracking est une grande

amélioration de l’approche brute force.
 L’idée est de construire une solution petit à petit et de
tester en permanence si cette affectation partielle (on
affecte des valeurs à certaines variables) pourra
conduire à une solution.
 Sice n’est pas le cas, on arrête l’affectation courante et on
revient en arrière : on backtrack

JC Régin - Concepts IA
 Backtrack
1.89

 On fait comme une DFS

 Pour un nœud (visite)
 On sélectionne une variable x
 Pour chaque valeur a possible pour x
◼ On affecte x à a et on regarde si cela viole des contraintes
◼ Si violation on définit x ≠ a et on choisit une autre valeur
◼ Si pas de violations : on continue. On appelle visit récursivement

JC Régin - Concepts IA
 Backtrack
1.90

 Visit(Etat)
 On sélectionne une variable x non déjà sélectionnée
 Pour chaque valeur a possible pour x
◼ Si(Etat  (x=a)) est consistant (ie. pas de violation de contraintes)
alors visit((Etat  (x=a))

JC Régin - Concepts IA
 Backtrack : exemple
1.91

 4-queens : placer 4 dames sur un échiquier 4x4 sans

qu’elles se prennent

JC Régin - Concepts IA
 Programmation par Contraintes (PPC)
1.92

 On ne le verra pas dans ce cours

 Constraint programming en anglais
 On essaie d’être intelligent
 On fait des déductions à chaque niveau du backtrack
 Ce que vous faites quand vous résolvez un sudoku !
 Les sudoku sont intelligemment catégorisés à l’aide de la
PPC

JC Régin - Concepts IA
 PPC Forward checking et Filtrages
1.93

JC Régin - Concepts IA
1.94 Problèmes à deux joueurs

JC Régin - Concepts IA
 Problèmes à deux joueurs
1.95

 Algorithme minimax
 Coupes Alpha-Béta

JC Régin - Concepts IA
 Problèmes à deux joueurs
1.96

 On considère des jeux dans lesquels chaque joueur joue

successivement (chacun à son tour)
 On considère des jeux à information complète (chacun
sait tout de la situation de jeu, à chaque instant).
 Dans la suite, on note J1 et J2 les deux joueurs et l'on se
place dans la situation c'est à J1 de jouer.

JC Régin - Concepts IA
 Problèmes à deux joueurs
1.97

 Le déroulement de la partie peut être vu comme un arbre :

 la racine correspond à l'état actuel du jeu
 les nœuds à profondeur paire = nœuds où J1doit jouer
 les nœuds à profondeur impaire = nœuds où J2 doit jouer
 un arc = un coup joué
 feuilles = les fins de partie : les états gagnants ou perdants
pour J1, ou encore les états bloqués (matches nuls)
 Un arc lie un état où ce coup est autorisé à l'état résultant de
l'application du coup
 un chemin allant de la racine à une feuille décrit une partie
possible.
JC Régin - Concepts IA
 Problèmes à deux joueurs
1.98

 Parallèle avec les graphes d'états :

 l'étatinitial est la situation actuelle,
 les états finaux sont les fins de partie

 les arcs correspondent les coups légaux.

 Cependant il manque dans cette formalisation la

présence de deux joueurs distincts et l'alternance de
leurs coups => algorithmes spécifiques.

JC Régin - Concepts IA
 Problèmes à deux joueurs
1.99

 On va prendre un problème très simple pour

commencer:
 Le jeu de Nim (jeu des allumettes) : chaque joueur peut à
chaque coup prendre 1, 2 ou 3 allumettes et celui qui prend
la dernière allumette a perdu.

JC Régin - Concepts IA
 Problèmes à deux joueurs
1.100

 On fait l’arbre de jeu

JC Régin - Concepts IA
 Problèmes à deux joueurs
1.101

 On évalue les positions terminales

JC Régin - Concepts IA
 Problèmes à deux joueurs
1.102

 On fait remonter les évaluations

Si c’est à J1 de jouer
Si c’est à J2 de jouer Alors on prend le MAX des fils
Alors on prend le MIN des fils

JC Régin - Concepts IA
 Minimax
1.103

 DecisionMinMax (e,J)
// Décide du meilleur coup à jouer par J dans la situation e
Pour chaque coup de CoupJouables(e,J)
valeur[coup] = ValeurMinMax(Applique(coup,e),J,false)
retourner (coup tel que valeur[coup] est maximale)

 ValeurMinMax (e,J,EstUnEtatMax)
// Calcule la valeur de e pour le joueur J selon que e EstUnEtatMax ou pas
If (estUnEtatMax) alors ret=+1 sinon ret=-1;
Si PartieGagnante(e,J) alors retourner(ret)
Si PartiePerdante(e,J) alors retourner(-ret)
Si PartieNulle(e,J) alors retourner(0)
vals = vide
Pour chaque coup c de CoupJouable(e,J)
ajouter ValeurMinMax(Applique(c,e),opposant(J),not(EstUnEtatMax))) à vals
Si EstUnEtatMax alors retourner(maximum de vals)
Sinon retourner(minimum de vals)

JC Régin - Concepts IA
 Minimax
1.104

 En pratique, l'algorithme Minimax n'est pas utilisé en

l'état : il est rarement possible de développer l'ensemble
de l'arbre de jeu.
 Deux adaptations sont fréquentes
 limiterla profondeur d'exploration ;
 effectuer des coupes dans l'arbre de jeu.

JC Régin - Concepts IA
 Minimax avec profondeur bornée
1.105

 Interrompre l'exploration de l'arbre avant d'avoir atteint

des fins de partie implique de pouvoir évaluer l'état du
jeu à un instant quelconque.
 Cela est rendu possible par l'utilisation
 d'une fonction d’évaluation h(e,J)qui évalue la
situation e pour le joueur J.
 On essaie de donner une valeur à une position donnée
 On évalue toujours par rapport au même joueur
 Positif
si en sa faveur (bonne position)
 Négatif si en sa défaveur (mauvaise position)

JC Régin - Concepts IA
 Minimax avec profondeur bornée
1.106

 On limite à la profondeur 4. On évalue les feuilles avec

la fonction d’évaluation

JC Régin - Concepts IA
 Minimax avec profondeur bornée
1.107

 On fait remonter les évaluations

JC Régin - Concepts IA
 Minimax avec profondeur bornée
1.108

 DecisionMinMax (e,J)
//Décide du meilleur coup à jouer par J dans la situation e

Pour chaque coup de CoupJouables(e,J)

valeur[coup]  ValeurMinMax(Applique(coup,e),J,false)
retourner (coup tel que valeur[coup] est maximale)

 ValeurMinMax (e,J,EstUnEtatMax,pmax)
// Calcule la valeur de e pour le joueur J selon que e EstUnEtatMax ou pas et
pmax la profondeur maximale
If (estUnEtatMax) alors ret=+ValMax sinon ret=-ValMax;
Si PartieGagnante(e,J) alors retourner(ret)
Si PartiePerdante(e,J) alors retourner(-ret)
Si PartieNulle(e,J) alors retourner(0)

Si pmax=0 Alors retourner h(e,J)

Sinon vals = vide
Pour chaque coup c de CoupJouables(e,J)
ajouter
ValeurMinMax(Applique(c,e),opposant(J),not(EstUnEtatMax),pmax-1)) à vals
Si EstUnEtatMax alors retourner(maximum de vals)
Sinon retourner(minimum de vals) JC Régin - Concepts IA
 Minimax avec profondeur bornée
1.109

 La fonction d’évaluation est très importante

 On aura des résultats très différents

 Programmation : deux choses importantes

 Enumérer les coups possibles (et valides !)
 Définir une fonction d’évaluation

JC Régin - Concepts IA
 Coupes Alpha Béta
1.110

 On peut éviter de considérer certains sous arbres

 Coupe Alpha (MAX)
MAX des fils

MIN des fils

Ce ne sert à rien d’étudier les autres fils du nœud le plus à droite car 17 ne sera pas pris

JC Régin - Concepts IA
 Coupes Alpha Béta
1.111

 On peut éviter de considérer certains sous arbres

 Coupe Béta (MIN)
MIN des fils

MAX des fils

Ce ne sert à rien d’étudier les autres fils du nœud le plus à droite car 30 ne sera pas pris

JC Régin - Concepts IA
 Minimax avec coupes Alpha-Béta
1.112

 DecisionAlphaBeta (e,J)
// Décide du meilleur coup à jouer par J dans la situation e
alpha  -ValMax
Pour chaque coup de CoupJouables(e,J)
val  ValeurAlphaBeta(Applique(coup,e),J,alpha,+MaxVal,false)
Si (val>alpha) alors
action  coup
alpha = val
retourner action
 ValeurAlphaBeta (e,J,alpha,beta,EstUnEtatMax,pmax)
// Calcule la valeur de e pour le joueur J selon que e EstUnEtatMax ou pas et pmax la profondeur maximale
 If (estUnEtatMax) alors ret=+ValMax sinon ret=-ValMax;
Si PartieGagnante(e,J) alors retourner(ret)
Si PartiePerdante(e,J) alors retourner(-ret)
Si PartieNulle(e,J) alors retourner(0)
Si pmax=0 alors retourner h(s,J)

Si EstUnEtatMax alors
Pour chaque coup c de CoupJouables(e,J)
alpha MAX(alpha,ValeurAlphaBeta(Applique(c,e),opposant(J),alpha,beta,not(EstUnEtatMax),pmax-1)
Si alpha >= beta alors retourner(alpha) /* coupe beta */
retourner(alpha)

/* EtatMin */
Pour chaque coup c de CoupJouables(e,J)
beta  MIN(beta,ValeurAlphaBeta(Applique(c,e),opposant(J),alpha,beta,not(EstUnEtatMax),pmax-1)
Si beta <= alpha alors retourner(beta) /* coupe alpha */
retourner(beta)

JC Régin - Concepts IA
 Améliorations
1.113

 D’autres algorithmes existent

 Scout, Negascout, MTD-f, SSS*
…

JC Régin - Concepts IA