3 RSI: Intelligence Artificielle
TD 5
Exercice 1 - Algorithme MINIMAX.
Soit un jeu à deux joueurs opposant les joueurs A et B. Trouvez le coup que A doit jouer grâce à
l’algorithme MINIMAX à partir des arbres de jeu suivants :
A1
c1 c2 c3
B1 B2 B3
A2 A3 A4 A5 A6 A7
5 1 13 -1 0 27 11 0 5 9 2 19 5 32
A1
c1 c2 c3
B1 B2 B3
A2 A3 A4 A5 A6 A7
B4 B5 B6 B7 B8 B9 B10 B11 B12 B13 B14 B15
2 10 -1 3 12 5 20 13 0 1 -4 -3 -5 10 7 16 2 4 2 -2 1 5 5 13 11 0
A1
c1 c2 c3 c4
B1 B2 B3 B4
A2 A3 A4 A6 A7 A6 A7
B4 B5 B6 B7 B8 B9 B12 B13 B14 B15 B12 B13 B14 B15
8 7 23 5 17 20 13 14 11 4 5 6 0 5 10 9 -2 14 20 18 17 15 2 8 12 -2 20 19
1
2. Comment ces étiquettes pourraient-elles être modifiées pour pouvoir être utilisées dans un jeu à
trois joueurs où les joueurs jouent toujours dans le même ordre ?
Exercice 4 - MINIMAX et ALPHA-BÉTA.
Soit un jeu à deux joueurs opposant les joueurs A et B (c’est au tour du joueur A), on considère
l’arbre de jeu suivant :
A1
c1 c2 c3
B1 B2 B3
A2 A3 A4 A5 A6 A7
B4 B5 B6 B7 B8 B9 B10 B11 B12 B13 B14 B15
3 9 1 8 6 12 20 0 13 2 4 1 5 2 8 21 14 2 4 7 7 5 8 13 11 4
Vous répondrez aux questions suivantes :
1. En employant l’algorithme MINIMAX, donnez le coup (c1 , c2 ou c3 ) que doit choisir le joueur
A pour maximiser ses chances de gagner.
2. Quelles branches de l’arbre peuvent être coupées grâce à l’algorithme ALPHA-BÉTA ? Vous
indentifierez les branches en donnant :
– le type de coupe (α ou β),
– les noeuds père-fils concernés (ex. : A1 , A2 , B1 , etc.).
Voici l’exemple (fictif) d’une coupe possible : (β, A4 , B8 ).
3. Quelle est la proportion de positions qui n’ont pas besoin d’être examinées grâce à l’utilisation
de cet algorithme ?
4. Répondez aux mêmes questions avec l’arbre de jeu suivant. Vous effectuerez dans un premier
temps un parcours main gauche, puis un parcours main droite. Que pensez-vous du choix de
l’ordre d’examen des coups sur l’efficacité de l’algorithme ALPHA-BÉTA ?
A1
c1 c2
B1 B2
A2 A3 A4 A5 A6 A7
B4 B5 B6 B7 B8 B9 B10 B11 B12 B13 B14 B15 B16
5 -1 -3 4 9 2 0 13 0 -4 8 12 -1 7 6 4 0 7 -2 -3 18 5 1 8 8 5 15 7
Chargé de TD/TME : DZOGANG Fabon 3
Responsable du cours : GANASCIA Jean-Gabriel
Exercice 5 - Jeu d’Awélé.
Considérons le jeu d’Awélé (http ://[Link]/wiki/Awélé) Répondez aux questions suiv-
antes :
1. Proposez une fonction d’évaluation qui pourrait être utilisée par un joueur Sud artificiel avec
l’algorithme MINIMAX.
2. Soit la configuration courante du jeu suivante (c’est à Sud de jouer) :
NORD
12 11 10 9 8 7
2 1 1 1 1
1 6 1
1 2 3 4 5 6
SUD
Dérivez l’arbre de recherche issu de ce tablier à une profondeur 1 (soit 2 demi-coups). Vous
numéroterez les coups pouvant être effectués par Sud et par Nord. Donnez ensuite l’évaluation
de toutes les feuilles de cet arbre suivant la fonction d’évaluation proposée en 1.
3. Considérons tout d’abord un ordre décroisant sur les coups à examiner. Donnez, en utilisant
l’algorithme ALPHA-BÉTA et en considérant un ordre croissant sur les coups à examiner, le
coup que doit jouer Sud.
4. Donnez le coup que doit jouer Sud, mais en examinant cette fois les coups dans l’ordre exactement
inverse. Que pensez-vous du choix de l’ordre d’examen des coups sur l’efficacité de l’algorithme
ALPHA-BÉTA ?
Exercice 6 - Nought and crosses (Tic-Tac-Toe alias le “morpion”).
On s’intéresse à la modélisation du jeu de tic-tac-toe à deux joueurs. Dans ce jeu, on dispose au
départ d’une grille vide 3x3. Supposons que MAX marque des crois (X) et MIN des cercles (O), et
que MAX joue le premier. Les deux joueurs inscrivent à tour de rôle une crois (joueur MAX) et un
cercle (joueur MIN). Le gagnant est le premier qui forme un alignement de trois marques identiques.
1. Combien de positions p différentes du morpion existe-t-il ?
2. En tenant compte des symétries, à combien ce nombre se réduit-il ?
3. Développez l’arbre de recherche pour deux demi-coups.
4. Déterminez une fonction heuristique h adaptée à la stratégie MINIMAX.
Chargé de TD/TME : DZOGANG Fabon 4
Responsable du cours : GANASCIA Jean-Gabriel