5.1- TP - Jeux : attracteurs et min-max
Dans ce TP, on programme les outils du cours : le graphe d'un jeu, le calcul des positions gagnantes (attracteurs), puis l'algorithme min-max. Et on fait jouer l'ordinateur !
I. Le jeu des allumettes
On reprend le jeu du cours : il y a
Un état est un couple (n, j) : n est le nombre d'allumettes restantes, et j (1 ou 2) le joueur qui doit jouer. Le graphe du jeu est représenté par un dictionnaire, qui associe à chaque état la liste de ses successeurs.
Question 1
Écrivez une fonction successeurs(etat, k) qui renvoie la liste des états atteignables en un coup depuis etat, quand on peut retirer entre 1 et k allumettes. Par exemple, successeurs((5, 1), 3) vaut [(4, 2), (3, 2), (2, 2)] (dans n'importe quel ordre), et successeurs((0, 2), 3) vaut [].
Loading editor...
Question 2
Écrivez une fonction graphe_allumettes(n_max, k) qui renvoie le graphe du jeu : un dictionnaire dont les clés sont tous les états (n, j) pour n_max et
Affichez le graphe pour n_max = 5 et k = 3 avec la fonction dessiner ci-dessous, et comparez avec celui du cours.
Loading editor...
a) Les attracteurs
On rappelle la définition du cours, où
Le rang d'un état de l'attracteur est le plus petit
Question 3
Écrivez une fonction attracteur(graphe, S1, F1) qui renvoie un dictionnaire associant à chaque état de l'attracteur son rang. S1 et F1 sont des ensembles (set) d'états.
On calcule les ensembles
Loading editor...
Question 4
Calculez l'attracteur pour n_max = 20 et k = 3, et affichez la liste des n tels que (n, 1) est une position gagnante pour J1. Retrouvez-vous le résultat du cours (
Recommencez avec k = 2, puis k = 4. Quelle règle générale conjecturez-vous ?
Loading editor...
Question 5
Affichez le graphe pour n_max = 6 et k = 2, avec les positions gagnantes de J1 en rouge (dessiner(graphe, rouges)).
Loading editor...
b) Une stratégie gagnante
Question 6
Écrivez une fonction coup_gagnant(graphe, rangs, etat) qui, pour un état contrôlé par J1 dans l'attracteur (et pas final), renvoie un successeur de rang strictement plus petit (voir le cours). Pour un état qui n'est pas dans l'attracteur, elle renvoie un successeur quelconque.
Loading editor...
Pour tester votre stratégie, on la fait jouer contre un adversaire qui joue au hasard. La fonction partie ci-dessous joue une partie depuis (n, 1), et renvoie le numéro du gagnant ; avec bavard=True, elle affiche la partie.
Question 7
Faites jouer votre stratégie (J1) contre au_hasard(graphe) (J2), depuis (10, 1) avec k = 3, en affichant la partie. Puis jouez 1000 parties, depuis des positions gagnantes et perdantes : votre stratégie gagne-t-elle toujours depuis une position gagnante ? Et depuis une position perdante ?
Loading editor...
II. Chomp
Au Chomp, on représente une tablette par le tuple des longueurs de ses lignes, de haut en bas : par exemple, (4, 4, 2) est une tablette de 3 lignes, dont la dernière n'a plus que 2 carrés. Une ligne n'est jamais plus longue que la ligne au-dessus, et on ne garde pas les lignes vides. La tablette de départ (m, m, ..., m) (
Le carré empoisonné est le carré (0, 0), en haut à gauche. Manger le carré (i, j) (ligne i, colonne j) mange aussi tous les carrés (i', j') avec
Pour ne pas avoir à manger le carré empoisonné, on considère que la partie s'arrête dès qu'il ne reste que lui : la tablette (1,) est finale, et le joueur qui doit jouer a perdu.
Question 8
Écrivez une fonction coups_chomp(tablette) qui renvoie la liste des tablettes qu'on peut obtenir en un coup (en mangeant n'importe quel carré sauf (0, 0)). Par exemple, coups_chomp((2, 1)) contient (1, 1) (on a mangé le carré (0, 1)) et (2,) (on a mangé le carré (1, 0)).
Loading editor...
Question 9
Écrivez une fonction graphe_chomp(n, m) qui renvoie le graphe du jeu (un dictionnaire, comme pour les allumettes) : les états sont des couples (tablette, joueur), et on part de l'état (tablette de départ, 1). On ne met dans le graphe que les états atteignables depuis le départ : faites un parcours (en largeur ou en profondeur) à partir de l'état de départ.
Loading editor...
Question 10
Calculez l'attracteur de J1 pour une tablette attracteur : quel est l'ensemble F1 ?). La position de départ est-elle gagnante pour J1 ? Si oui, quel premier coup doit-il jouer ?
Vérifiez avec le widget du cours (option « Montrer les coups gagnants »), puis faites jouer votre stratégie contre un joueur au hasard.
Loading editor...
Loading editor...
Question 11
Pour toutes les tablettes
Loading editor...
III. Le morpion et min-max
Le morpion est trop gros pour qu'on dessine son graphe, mais on peut l'explorer avec min-max. Un plateau est une liste de 9 cases, numérotées de 0 à 8 de gauche à droite et de haut en bas, contenant "X", "O" ou " " (case vide). J1 joue les X, J2 les O.
Loading editor...
LIGNES = [(0, 1, 2), (3, 4, 5), (6, 7, 8), # lignes
(0, 3, 6), (1, 4, 7), (2, 5, 8), # colonnes
(0, 4, 8), (2, 4, 6)] # diagonales
def afficher(plateau):
for i in range(3):
print(" " + " | ".join(plateau[3 * i:3 * i + 3]))
if i < 2:
print("---+---+---")
afficher(["X", "O", " ", " ", "X", " ", " ", " ", "O"])Question 12
Écrivez une fonction gagnant(plateau) qui renvoie "X" ou "O" si ce joueur a aligné trois symboles, et None sinon. Puis une fonction coups(plateau) qui renvoie la liste des indices des cases vides.
Loading editor...
Question 13
Écrivez la fonction heuristique(plateau) du cours : le nombre de lignes encore possibles pour X (qui ne contiennent aucun O), moins le nombre de lignes encore possibles pour O (qui ne contiennent aucun X).
Loading editor...
Question 14
Écrivez une fonction récursive minmax(plateau, joueur, p) qui renvoie la valeur joueur ("X" ou "O") de jouer :
- si X a gagné :
1000; si O a gagné :-1000; si le plateau est plein (match nul) :0; - sinon, si
p == 0: l'heuristique ; - sinon, le maximum (si c'est à X de jouer) ou le minimum (si c'est à O) des valeurs à profondeur
p - 1des plateaux obtenus en jouant chaque coup possible.
Attention : pour essayer un coup, on peut modifier le plateau, faire l'appel récursif, puis annuler le coup (remettre " " dans la case).
Loading editor...
Question 15
Écrivez une fonction meilleur_coup(plateau, joueur, p) qui renvoie l'indice de la case où joueur doit jouer d'après min-max à profondeur p : celui qui maximise (pour X) ou minimise (pour O) la valeur à profondeur p - 1 du plateau obtenu.
Loading editor...
La fonction match fait jouer deux joueurs l'un contre l'autre : chacun est une fonction qui prend le plateau et son symbole, et renvoie la case choisie.
Question 16
Faites jouer ia(2) contre hasard, puis hasard contre ia(2). Jouez 100 parties dans chaque cas (avec bavard=False) : combien l'IA en gagne-t-elle ? En perd-elle ? Et avec ia(4) ? Que se passe-t-il quand ia(4) joue contre elle-même ?
Loading editor...
Loading editor...
Question 17
Quelle est la valeur du plateau vide à profondeur 9 (c'est-à-dire sans heuristique : on explore tout le jeu) ? Le calcul peut prendre quelques secondes. Que signifie ce résultat ?
Loading editor...
Bonus - Mémoïsation
Beaucoup de plateaux sont atteints par des ordres de coups différents, et minmax les recalcule à chaque fois. Écrivez une version minmax_memo qui garde dans un dictionnaire la valeur de chaque couple (plateau, joueur) déjà calculé (attention : une liste ne peut pas être une clé de dictionnaire, utilisez tuple(plateau)). Comparez le nombre d'appels et le temps de calcul pour le plateau vide à profondeur 9.
Loading editor...
Entrez le code donné en cours pour accéder à la solution :