Chapitre II Résolution de problèmes EPSI / Montpellier - Cycle CSII 2A Intelligence Artificielle

chapitre II

Résolution de problèmes

EPSI / Montpellier - Cycle CSII 2A

Intelligence Artificielle


• IntroductionLa résolution de problèmes est le processus qui consiste à sélectionner et ordonnancer des actions élémentaires en séquences afin d'atteindre des buts donnés en respectant les contraintes d'un environnement donné.

Composition du processus :– un état initial (le problème à résoudre), – un état final (la solution au problème),– un ensemble d'actions élémentaires permettant de passer

d'un état à un autre, Objectif du processus :

– Trouver une séquence d'actions à exécuter pour passer de l'état initial à l'état final


• Introduction Complexité du processus :

– A partir d'un état donné, on peut effectuer plusieurs actions élémentaires différentes qui débouchent sur des états différents.La méthode qui consiste à essayer successivement toutes les possibilités jusqu'à trouver une solution est une méthode de recherche fortement combinatoire

– On est souvent amené à choisir entre plusieurs choix ou à choisir la meilleur solution : problème d’optimisation combinatoire

Apport de l’IA :– L’IA apporte une solution à ce problème : les “ heuristiques ” :

méthodes permettant de choisir en premier les actions ayant le plus de chance d'aboutir


• Types de domaines

La démonstration de théorèmes Les jeux de stratégies (échec, dame) La planification :

robotique allocations de ressources emploi du temps


• Exemple de problème - Planification de chaîne de production

Chaîne de production Atelier A Atelier B Atelier C Atelier D

Capacité de production 5v/h/h 3v/h/h 2v/h/h 3v/h/h

Ressources - Op1 : 8h-13h - Op2 : 8h-13h - Op3 : 9h-13h- Op4 : 10h-15h

Etat initial 30v en attente à 8h

0v en attente à 8h

0v en attente à 8h

0v en attente à 8h

But Etablir l'emploi du temps indiquant heure par heure quels opérateurs sont affectés à chaque atelier, de telle sorte que le maximum de voitures soient passées par les 4 ateliers à la fin de la journée


• Exemple de problème - Le voyageur de commerce

140

99

211

80

97

Ville B

Ville C

Ville D

Ville EVille F

Ville A

101

Ville K

Ville L

120

150

100

140 70

160 160

180

220

Un voyageur de commerce partant d'une ville veut se rendre successivement dans un certain nombres de villes sans repasser deux fois dans la même ville et en revenant finalement à la ville de départ. On connaît les distances de ville à ville. Quel trajet doit-il effectuer de façon à minimiser la distance parcourue ?

EXPLOSION COMBINATOIRE

(n-1)!/2 configurations181440 configurations pour n=10466631x10150 configurations pour n=100


• Exemple de problème - Le Taquin n n+1 carreaux numérotés et un carreau

"vide" sont disposés sur un damier dans une configuration donnée. L'objectif du taquin est de modifier la position des carreaux pour arriver à une configuration finale donnée. On autorise les changements de position seulement par glissement d'un des carreaux sur le carreau vide à partir d'une position adjacente orthogonale. Le but du jeu est de trouver la séquence la plus courte amenant à la configuration finale.


(n+1)! configurations362880 configurations pour n = 8933262x10152 configurations pour n=99

Initial Final


• Exemple de problème - La tour de Hanoï Trois disques (un grand, un moyen et un petit) sont

enfilés dans cet ordre sur une tige A. Les déplacer sur une tige B sachant que les opérations autorisées consistent à prendre le disque de sommet de pile sur une tige donnée et le placer sur le disque de sommet de pile d'une autre tige (ou sur la tige seule s'il ne s'y trouve pas de disque). En cas d'empilement, un disque ne peut se poser que sur un disque plus large. On peut utiliser une tige intermédiaire C.


2n -1configurations7 configurations pour n = 3264 -1 configurations pour n=64(soit 238 années (1s/déplacement))


• Exemple de problème - Les n reines

Mettre n reines sur un échiquier de taille nxnsans qu’aucune reine ne soit en prise par une autre(n>3)


n! permutations40320 permutations et 92 solutions différentes pour n = 8

Résolution de problèmes• Complexité

– Complexité d’un algorithme

* une mesure de temps (complexité en temps) ou d'espace mémoire (complexité en espace ) utilisé par un algorithme en fonction de la taille des données

* la complexité en temps d’un algorithme est le nombre d'étapes de calcul qu ’il nécessite, et sa complexité en espace comme la taille de mémoire nécessaire pour stocker les données intermédiaires au cours de son exécution; ces grandeurs sont indiquées en fonction de la taille des données du problème à résoudre, et généralement à une constante de proportionnalité près

* seul l’ordre de grandeur du nombre d’opérations, noté O, est utilisé pour exprimer la complexité : O(f(n))


– principales classes de complexité d’algorithmes– complexité logarithmique

• coût : O(log n)• ex : recherche dichotomique dans un tableau trié

– complexité linéaire• coût : O(n)• ex : recherche du minimum d ’une liste de n éléments, calcul du produit scalaire de deux vecteurs de Rn

– complexité polynomiale• coût : O(nk) (k : une constante > 1)• ex : multiplication de deux matrice carrées d’ordre n : (O(n3))

– complexité exponentielle• coût : O(an) (n : une constante > 1)• ex : tours de Hanoï, voyageur de commerce


–Complexité d’un problème La complexité (maximale) du meilleur algorithme connu pour le résoudre

–Classification des problèmes la classe PClasse des problèmes qu ’on peut résoudre en temps polynomial

la classe EClasse des problèmes qu ’on peut résoudre en temps exponentiel

la classe NPClasse des problèmes qu ’on peut vérifier en temps polynomial et résoudre en temps exponentiel (problèmes non déterministes polynomiaux)

Résolution de problèmes• Représentation des problèmes

– Espace d’états Un problème est défini par un espace d’états qui est l'ensemble des états possibles de ce problèmesExemples d ’états : * une configuration de pièces dans un jeu d ’échecs* un calendrier partiel ou complet des matches de tennis* une partie de preuve ou une preuve complète d'un démonstrateur de théorèmes

– Opérateurs Les états d’un problème sont reliés les uns aux autres par des opérateurs qui transforment un état dans un autreExemples d’opérateurs : * un coup légal aux échecs qui transforme la configuration des pièces dans une autre * l'ajout d'un match de tennis dans le problème de planification

* l'application d'une règle d'inférence dans le démonstrateur de théorèmes


– But

Dans la résolution d’un problème, on a un but qui décrit ce que l'on cherche. Un but est un sous-ensemble d’états de l’espace d’états

Exemples de buts :

* dans le jeu d'échecs, le but est l'ensemble des configurations de pièces qui mettent votre adversaire échec et mat

* Pour le démonstrateur de théorèmes ce sont toutes les preuves dont la dernière ligne correspond à la formule à prouver


- Graphe d’états et espace de recherche

* En IA, on utilise les graphes pour représenter l’espace d’états d’un problème (graphe d’états)

– chaque nœud représente un état– chacun des arcs représente un opérateur (une transition) faisant

passer d'un état à un autre– le but est un nœud particulier du graphe

* La résolution d’un problème revient à explorer Le graphe dans la recherche du nœud but (l’espace de recherche)


- Réduction de problèmes et graphe ET/OU

* Lorsque on a un problème principal qui peut se décomposer en sous problèmes plus faciles à résoudre, résoudre ce problème principal revient à résoudre tous les sous problèmes qu’il le compose

* La technique qui consiste à résoudre un but en résolvant ses sous-buts est appelé réduction de problème* certains buts ne peuvent être atteints que si leurs sous-buts immédiats le sont tous (nœud ET)* les autres buts sont atteints si l'un au moins de leurs sous-buts immédiats est atteint (nœud OU)* le graphe formé de nœuds ET et OU est appelé graphe ET/OU


Composition d’un système de résolution - Des structures de données organisés en arbre ou en graphe

– Des opérateurs définies par leurs conditions d'application et leur action

– Une structure de contrôle mettant en œuvre la stratégie de recherche dans l’arbre ou le graphe (méthodes de recherche ou de résolution)

Résolution de problèmes• Raisonnement

Caractéristiques

1) Le système doit-il trouver une solution à partir de ce qu'il connaît du

problème ou peut-il y avoir une interaction avec l'utilisateur

2) Faut-il se contenter d'une solution sous-optimale mais plus facilement et rapidement accessible

3) Peut-on annuler une action décidée au cours de la réflexion une fois qu'elle

a été exécutée

4) Est-ce qu'on peut prévoir exactement l'effet d'une action sur l'état courant

du problème

5) Est-ce que le problème peut se décomposer en sous problèmes plus faciles à résoudre et est-ce que les sous problèmes sont indépendants ou non.

6) Quelles sont les connaissances minimales requises pour aboutir à la solution

du problème

7) Est-ce qu’une solution est garantie ?, est-ce que la recherche terminera ?

quelle est la complexité de la recherche en temps et en espace ?

Résolution de problèmes• Raisonnement

Caractéristiques

1) Le système doit-il trouver une solution à partir de ce qu'il connaît du

problème ou peut-il y avoir une interaction avec l'utilisateur

2) Faut-il se contenter d'une solution sous-optimale mais plus facilement et rapidement accessible

3) Peut-on annuler une action décidée au cours de la réflexion une fois qu'elle

a été exécutée

4) Est-ce qu'on peut prévoir exactement l'effet d'une action sur l'état courant

du problème

5) Est-ce que le problème peut se décomposer en sous problèmes plus faciles à résoudre et est-ce que les sous problèmes sont indépendants ou non.

6) Quelles sont les connaissances minimales requises pour aboutir à la solution

du problème

7) Est-ce qu’une solution est garantie ?, est-ce que la recherche terminera ?

quelle est la complexité de la recherche en temps et en espace ?

• Méthodes de recherche

– Méthodes aveugles : énumération exhaustive de tous les états de l’espace de recherche

– Heuristiques : construction de chemins minimaux dans l ’exploration de l ’espace de recherche basée sur des critères, des principes, ou des méthodes permettant de faire les choix les plus efficaces pour atteindre le but fixé


• Méthodes de recherche

– Méthodes aveugles : • Recherche en profondeur• Recherche en largeur• Recherche en profondeur limitée• Recherche en approfondissement itératif

– Méthodes heuristiques :• Recherche en profondeur ordonné• Recherche du meilleur d ’abord• Algorithme A*


• Méthodes de recherche– Critères d’évaluation :

• Complétude : solution garantie si elle existe• Optimalisé : meilleur solution garantie• Complexité en espace : espace mémoire

nécessaire pour effectuer la recherche• Complexité en temps : temps nécessaire pour

effectuer la recherche


La complexité est mesuré selon les 3 critères :

1. b : facteur de branchement (nombre de descendants/nœuds) maximum du graphe d’états2. d : profondeur à la quelle se trouve le (meilleur) nœud solution3. m : profondeur maximale du graphe

E7 E8 E9E4 E5 E6

E13 E14

8 12

10 11

E11 E12

3 4

14 situations explorées

E0

17

13

9

E10

E1 E2 E3

142 5 6

• Méthodes de recherche aveugle– Profondeur d ’abord

(LIFO) :– Principe : la priorité est donné

aux nœuds de niveaux les plus profonds du graphe de recherche

Exemple


• Méthodes de recherche aveugle– Profondeur d ’abord :

– Algorithme :

Début1 empiler la racine2 répéterSi sommet de pile <>nœud but alors- dépiler le premier élément- empiler ses fils s'il en a du plus à droite au plus à gaucheSinon ne rien faireJusqu'à ce que la pile soit vide ou sommet pile =nœud but3 la recherche aboutit si lenœud but a été atteint.Fin


• Méthodes de recherche aveugle– Profondeur d ’abord :

– Propriétés :• Complétude : Non si m tends vers l’infini• Complexité en temps : O(bm)• Complexité en espace : O(b*m)• Optimalité : Non


E7 E8 E9E4 E5 E6

7 9

10 situations explorées

E0

12

3

8

E10

E1 E2 E3

104 5 6

• Méthodes de recherche aveugle– Largeur d’abord

(FIFO) :– Principe : la priorité est donné

aux nœuds de niveaux les moins profonds du graphe de recherche

Exemple


• Méthodes de recherche aveugle– Largeur d ’abord :

– Algorithme :

Début1 empiler la racine2 répéterSi sommet de pile <>nœud but alors- dépiler le premier élément- empiler ses fils s'il en a du plus à gauche au plus à droiteSinon ne rien faireJusqu'à ce que la pile soit vide ou sommet pile =nœud but 3 la recherche aboutit si lenœud but a été atteint. Fin


• Méthodes de recherche aveugle– Largeur d’abord :

– Propriétés :• Complétude : Non si b tends vers l’infini• Complexité en temps : O(bd)• Complexité en espace : O(bd)• Optimalité : Non


Profondeur Nœuds Temps Espace02468101214

110010000106

108

1010

1012

1014

1 milliseconde0,1seconde10 secondes18 minutes31 heures128 jours35 années3500 années

100 octets11 kilooctets1 mégaoctetes100 mégaoctets10 gégaoctets1 teraoctets100 teraocets10000 teraocets

Exemple:- b = 10- production de nœuds : 1000 /s-espace mémoire :100 octet/noeud

E7 E8 E9E4 E5 E6

6 8

E0

15

9

7

E10

E1 E2 E3

102 3 4

• Méthodes de recherche aveugle– Profondeur limitée :

– Principe : idem que profondeurd ’abord avec une limite de profondeur d ’exploration L

Exemple avec une profondeur limitée L=2


• Méthodes de recherche aveugle– Profondeur Limitée :

– Algorithme :

Début1 empiler la racine2 répéterSi sommet de pile <>nœud but alors- dépiler le premier élément- empiler ses fils s'il en a du plus à droite au plus à gaucheSinon ne rien faireJusqu'à ce que la pile soit vide ou sommet pile =nœud but ou limite profondeur atteinte3 la recherche aboutit si le nœud but a été atteint.Fin


• Méthodes de recherche aveugle– Profondeur Limitée :

– Propriétés :• Complétude : Oui si L >=d• Complexité en temps : O(bL)• Complexité en espace : O(b*L)• Optimalité : Non


E7 E8 E9E4 E5 E6

9 11

E0

1,42,8

3,12

10

E10

E1 E2 E3

135 6 7

• Méthodes de recherche aveugle– Approfondissement

itératif :– Principe : recherche en

profondeur, limitée à la profondeur 1, puis 2, ... jusqu'à l'obtention d'une solution (ou l'échec de la recherche)

Exemple


• Méthodes de recherche aveugle– Approfondissement itératif :

– Propriétés :• Complétude : Oui • Complexité en temps : O(bd)• Complexité en espace : O(b*d)• Optimalité : Non


• Méthodes de recherche aveugle– Conclusions :

• Les recherches en largeur garantissent de trouver la solution (si elle existe) et de trouver le chemin le plus court au but

• Les recherches en largeur demandent un espace mémoire qui augmente exponentiellement, car elles gardent tous enfants au même niveau

• Les recherches en profondeur sont très efficace dans les cas où le but est loin de la racine, et les branches sont arrangées de gauche à droite par probabilité de solution

• Les recherches en profondeur peuvent se perdre dans une branche sans fin et parfois se retrouve en boucle infinie

• Les recherches aveugles sont caractérisées par une taille souvent rédhibitoire des arborescences et une très forte complexité des algorithmes


• Méthodes de recherche heuristique– Fonction heuristique

• h : E - un état e E (espace d'états) --> un nombre h(e) - h(e) est (généralement) une estimation du rapport coût/bénéfice qu'il y a à étendre le chemin courant en passant par e.

- contrainte : h(solution) = 0


e1 e2 e3

A

h(e1) = 0.8

h(e2) = 2

h(e3) = 1.6

• Méthodes de recherche heuristique– Exemples de fonction heuristique

– Problème des 8 reines

• Heuristique : laisser un plus grand nombre de cases non attaquables dans la partie restante de l'échiquier pour garder le plus de choix possibles pour les ajouts de reines futures




• nombre de cases non attaquables : 8

h(A) = 8





h(B) = 9





h(C) = 10 :meilleure solution


• Méthodes de recherche heuristique– Exemples de fonction

heuristique

– Problème du taquin 3x3

– Heuristique : nombre de carreaux mal placés


Résolution de problèmesVA

VBVK VL

VA VM VC VD

VF

152

329374 250

366 380 178190

0

366

Heuristique : distance à vol d’oiseau

VE

50

70

• Méthodes de recherche heuristique– Profondeur ordonnée :

– Principe : Approfondissement des branches jusqu'a leur extrémité, dans l'ordre inverse de leur

distance au but

Meilleur chemin : VA>VB>VC>VF

• Méthodes de recherche heuristique– Profondeur ordonnée :

– Algorithme :

Début1 empiler la racine2 répéterSi sommet de pile <>nœud but alors- dépiler le premier élément- empiler ses fils s'il en a dans l ’ordre inverse de leur distance au

butSinon ne rien faireJusqu'à ce que la pile soit vide ou sommet pile = nœud but

3 la recherche aboutit si le nœud but a été atteintFin



Heuristique : proximité du but

• Méthodes de recherche heuristique– Meilleur premier :

– Principe : Dès que l'on rencontre un chemin meilleur qu'auparavant, c'est celui là que l ’on

approfondit


– Algorithme :

Début1 empiler la racine2 répéterSi sommet de pile <>nœud but alors- dépiler le premier élément- empiler ses fils s'il en a dans la file et trier la pile entière parordre croissant des distances calculées au butSinon ne rien faireJusqu'à ce que la pile soit vide ou sommet pile = nœud but

3 la recherche aboutit si le nœud but a été atteintFin



– Propriétés :• Complétude : Non • Complexité en temps : O(bm)• Complexité en espace : O(bm)• Optimalité : Non


Résolution de problèmes• Méthodes de recherche

heuristique– Algorithme A* :

– Principe : améliorer l’algorithme du “ Meilleur premier ” en calculant le plus court chemin pour passer d'un état initial à un état final

Soient :* n0 : la racine du graphe* G : le nœud solution* c(ni,nj) : le coût pour aller du nœud ni au nœud nj

On définit - g (n) = c(n0,n) : le coût pour aller du nœud racine n0 au nœud n- h (n) = c(n,G) : l ’estimation heuristique du coût pour aller du nœud n au nœud solution G

On obtient alors la fonction d ’évaluation du coût du chemin en passant par le noeud n : f(n) = g(n) + h(n)



– Exemple



– Définitions

- Heuristique consistante : Pour tout x, pour tout y descendant de x :h (x) <= h (y) + c (x,y)

- Heuristique admissible : Pour tout x, h (x) <= h* (x) où h* (x) est la valeur optimale de x à G

• Méthodes de recherche heuristique– Algorithme A* :

– Algorithme :Début

Initialement, la file des chemins partiels contient le chemin d'ordre zéro,de longueur nulle et reliant la racine à nulle part2. Repetersi le premier chemin de la file n'aboutit pas au but alorsle supprimer de la fileformer les nouveaux chemins obtenus en prolongeant d'un niveau le cheminsuppriméinsérer ces nouveaux chemins dans la filele coût de chaque chemin étant la somme de la distance déjà parcourue etd'une estimation minorante de la distance restant à parcourir.trier la file par coûts croissantssi deux chemins ou plus atteignent le même noeud ne conserverque celui ayant la longueur minimalefinsiJusqu'à ce que la file soit vide ou que le noeud but soit atteint


• Méthodes de recherche heuristique– Algorithme A* :

– Propriétés :• Complétude : Oui • Complexité : linéaire si h est consistante• Optimalité : Oui si h est admissible



• Programmes de jeux de stratégie

Caractéristique des jeux :

– jeux de plateaux à 2 joueurs (les échecs, les dames, le tic-tac-toc), – jeux à information totale,– jeux avec deux adversaires effectuent à tour de rôle des déplacements,

chacun considérant les défaillances de l'adversaire comme ses propres succès– à chaque tour, le joueur doit imaginer comment l'adversaire va réagir, puis

comment le lui répondre, et ainsi de suite– jeux trop complexe pour envisager une solution exhaustive (les échecs ont un

facteur de branchement = 35)– Tous les déplacements ne sont contrôlés par l’ordinateur– Le jeu commence à partir d'un état initial spécifié et se termine à une position

qui, en utilisant un critère simple, peut être déclarée gagnante pour un joueur et perdante pour l'autre, ou encore comme un match nul



Composante de base d ’un programme de jeux :

- Générateur de mouvements

génère les mouvements valides à partir de l'état courant

- Test de terminaison

décide si l'état courant est un gain, une perte, un nul ou rien de particulier

- Fonction d'évaluation (fonction de gain)

évalue les gains d'un état donné indépendamment des coups passés ou

futurs

- Stratégie de contrôle

fournit les éléments nécessaires pour choisir entre différentes options

celle qui semble la plus prometteuse


• Programmes de jeux de stratégieExemple de jeu : les échecs

F6 G5

C6 B4

H7 H6

E5 E4

…

F8 B4

1

21

31

41

5

12

5

4

3


• Programmes de jeux de stratégieExemple de jeu : les échecs

Situation courante

Quel coup choisir ?

? ?



Arbre de jeu :

- Arbre de jeu : une représentation explicite de toutes les actions possibles de jeu (espace d’états)- Nœud racine : position initiale du jeu- Nœuds niveau 1 : positions que le premier joueur peut

atteindre en un déplacement- Nœuds niveau 2 : positions résultant de la réplique du second joueur- Nœuds terminaux : représentent un nœud gagnant, un nœud perdant ou un match nul- Chemin racine ==>nœud terminal : une partie complète du

jeu

Résolution de problèmes• Programmes

de jeux de stratégie

Arbre de jeu :


• Méthode du MiniMax Caractéristiques :

– Méthode qui schématise le processus décisionnel que devrait suivre tout joueur : supposer que chaque joueur va, à chaque moment, prendre la décision qui est la meilleure pour lui

– Méthode qui transcrit le principe de rendre ses chances minimales quand on considère le jeu du point de vue de l ’adversaire, et maximales quand on réfléchit pour soi

– Méthode où le premier joueur est appelé Max et son adversaire Min– Technique qui amène l'ordinateur à passer en revue toutes les possibilités

pour un nombre limité de coups et à leur assigner une valeur qui prenne en compte les bénéfices pour le joueur et pour son adversaire. Le meilleur coup étant alors celui qui maximise ses bénéfices tout en minimisant ceux de son adversaire


• Méthode du MiniMax Caractéristiques :

– On supposera dans cette technique que :• aucune partie ne comporte un nombre infini de coups• à chaque position, il existe un nombre fini de coups légaux• à chaque position p, il existe un nombre fini F(p) tel que toute partie commençant à

partir de p ne comporte pas plus de F(p) coups

– Le but de cette technique est de construire un algorithme qui, étant donné une position p, et un joueur, choisissent un coup valable et optimal pour ce joueur

– Méthode universellement utilisée (échecs, dames, othello, bridge,... )


• Méthode du MiniMax Principe :

- Pour chaque demi-coup des noirs possibles, l ’ordinateur va envisager toutes les réponses possibles des blancs et pour chaque réponse de blancs, il va envisager toutes les répliques possibles des noirs et etc.

- On développe l'arbre de jeu à partir d ’une position courante p en explorant toutes les positions possibles à partir de p et jusqu ’à une profondeur donnée et on fait remonter à la racine une valeur qui est calculée récursivement de la façon suivante :

MiniMax(p)=eval(p) si p est une position terminale (une feuille)

MiniMax(p)=max(MiniMax(s1), ..., MiniMax(sn)) si p est une position joueur avec successeurs s1, ..., sn (un nœud max)

MiniMax(p)=min(MiniMax(f1), ..., MiniMax(fm)) si p est une position opposant avec successurs f1, ..., fm (un nœud min)

– MiniMax(p) est la meilleure valeur possible (meilleur coup) à partir de la position p, si l'opposant joue de façon optimale

-1 4 -3 8 7 -5

Position courante p

Positions terminales

Résolution de problèmes• Méthode du MiniMax

Principe :

Evaluation des nœuds

max

min

max -1 4 -3 8 7 -5


Principe : Application du Min/Max

4 8

4

7 -5

-5

4


• Méthode du MiniMax Implémentation :

– un type de données position qui permet de représenter les états possibles du jeu

– une fonction pour évaluer les positions terminales – une fonction qui sert à déterminer si une position est une position joueur ou

opposant (qui c ’est qui joue? L ’ordinateur ou le joueur?)– une fonction qui prenne une position p et retourne la liste de tous les coups

jouables à partir de p et jusqu’à une profondeur n– une fonction qui détermine si le jeu est terminé ou pas– une fonction qui détermine le gagnant : l ’ordinateur, le joueur ou match nul


• Méthode du MiniMax Exemple de jeu : jeux de Nîmes

On dispose d'une pile d'allumettes. Il y a 2 joueurs. Chaque joueur peut, à son tour, séparer une pile en 2 piles inégales. Le jeu se termine lorsqu'unjoueur ne peut plus jouer et il perd

Fonction d ’évaluation :eval(f) = -1 si Min gagne 1 si Max gagne

-1

1

-1

-1

-1 1

-1 1 -1 1

1 1 1

1


• Méthode du MiniMax Raisonnement de l’ordinateur :

– Profondeur 1

• A : position initiale du jeu, niveau maximisant (ordinateur qui joue)

10


• Méthode du MiniMax Raisonnement de l’ordinateur :

– Profondeur 2

• B : niveau minimisant (adversaire qui joue)

3

3

5

5

2


Raisonnement de l’ordinateur :

– Profondeur 3

5

5

11 8 4

4

12 2

2

3

3

11 5

5


• Méthode du MiniMax Fonction d’évaluation :

– Fonction primordiale qui renvoi un score qui doit être représentatif de la position :

• score > 0 : avantage pour la machine (MAX)

• score < 0 : avantage pour le joueur (MIN)

• score = 0 : partie équilibrée

– Fonction utilisée pour calculer le meilleur coup

– Fonction qui doit être le plus fiable et le plus rapide possible

• Méthode du MiniMax– Algorithme :

Fonction MiniMax(p)

1. si p est terminal alors Score <- eval(p)2. sinon pour i de 1 à j faire // j = nombre de successeurs de p (a) Générer fi ie successeurs de p

(b) si = 1 alors Score <- MiniMax(f1)

sinon // i >= 2 si p noeud min alors Score <- min(Score, MiniMax(fi))

si p noeud max alors Score <- max(Score, MiniMax(fi))

3. retourner Score


• Méthode du MiniMax

– Propriétés :

• Complétude : Oui si l ’arbre de jeu est fini• Complexité : O(bm)• Optimalité : Oui si l ’adversaire est optimal



• Méthode du MiniMax

Complexité combinatoire :

Pour un jeu avec 10 demi-coups possibles :

niveau 1 : 10 niveau 2 : 100 niveau 3 : 1000 niveau 4 : 10000 niveau 5 : 100000 niveau 6 : 1 million niveau 7 : 10 millionsniveau 8 : 100 millions

Tic-Tac-Toe : 39 (19683) nœudsEchecs : 35100 noeuds


Complexité combinatoire :

– Solutions

• MiniMax avec profondeur limitée (prédictions sur 2 ou 4 niveaux max)

• Elagage -


• Elagage -

Exemple :

– Profondeur 3

5

5

6 8 4 3

5

Résultat :11 positions étudiés16 positions éliminéessoit un gain de 60%

Résolution de problèmes• Elagage -

Principe :

• Etendre l'arbre de jeu jusqu'à une profondeur N par recherche en profondeur• Chaque nœud Max garde la trace d'une -valeur = valeur de son meilleur successeur trouvé jusqu'ici• Chaque nœud Min garde la trace d'une -valeur = valeur de son plus mauvais successeur trouvé jusqu'ici• Ne plus générer les successeurs d'un nœud dès qu'il est évident que ce nœud ne sera pas choisi (compte tenu des nœuds déjà examinés)

– Interrompre la recherche d'un nœud Min si sa -valeur -valeur de son nœud-parent : coupure – Interrompre la recherche d'un nœud Max si son -valeur -valeur de son nœud-parent : coupure


Coupure :

Coupure :

Min

-valeur

-valeur

Max

-valeur

-valeur


Algorithme :

Minimax_alpha_beta(P,)DébutSoient P1, P2, …, Pn successeurs de PSi n = 0 Alors retourner eval(P) // P est terminalSinon k1 Si P est un nœud Max Alors Coupure faux Tant que k <= n et Coupure <> Vrai Faire max[Minimax_alpha_beta(P, Si Alors Coupure Vrai // élagage de l’arbre Fin Si k k+1 Fin Tant que Si coupure = Vrai Alors Retourner Sinon RetournerFin Si Sinon // Nœud Min Fin SiFin SiFin

Coupure faux Tant que k <= n et Coupure <> Vrai Faire min[Minimax_alpha_beta(P, Si Alors Coupure Vrai // élagage de l’arbre Fin Si k k+1 Fin Tant que Si coupure = Vrai Alors Retourner Sinon RetournerFin Si


• Elagage -

– Propriétés :

• Complétude : Oui si l ’arbre de jeu est fini• Complexité : O(bm/2)

doubler la profondeur de recherche (8 niveaux de prédictions pour les échecs)

• Optimalité : Oui si l ’adversaire est optimal

Documents

Chapitre II Résolution de problèmes EPSI / Montpellier - Cycle CSII 2A Intelligence Artificielle