Skip to main content Informatique en prépa - Lycée Malherbe 

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 allumettes ; chacun son tour, un joueur en retire entre 1 et (sans dépasser le nombre d'allumettes restantes) ; celui qui prend la dernière allumette a perdu.

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 [].

Python

Loading editor...

Vérification : successeurs
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).
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 , chacun associé à la liste de ses successeurs.

Affichez le graphe pour n_max = 5 et k = 3 avec la fonction dessiner ci-dessous, et comparez avec celui du cours.

Python
code masqué : pas besoin de le lire pour suivre, exécutez-le simplement
Python

Loading editor...

Vérification : graphe_allumettes
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).

a) Les attracteurs

On rappelle la définition du cours, où est l'ensemble des états contrôlés par J1 et l'ensemble des états finals gagnants pour J1 :

Le rang d'un état de l'attracteur est le plus petit tel que .

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 les uns après les autres : à chaque étape, on cherche tous les états qui ne sont pas encore dans l'attracteur et qui vérifient la condition (en regardant les rangs déjà connus), puis on leur donne tous le rang . On s'arrête quand une étape n'ajoute aucun état.

Python

Loading editor...

Vérification : attracteur
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).
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 ( n'est pas de la forme ) ?

Recommencez avec k = 2, puis k = 4. Quelle règle générale conjecturez-vous ?

Python

Loading editor...

Réponse
Question 5

Affichez le graphe pour n_max = 6 et k = 2, avec les positions gagnantes de J1 en rouge (dessiner(graphe, rouges)).

Python

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.

Python

Loading editor...

Vérification : coup_gagnant
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).

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.

Python
code masqué : pas besoin de le lire pour suivre, exécutez-le simplement
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 ?

Python

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 est (m, m, ..., m) ( fois).

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 et : chaque ligne d'indice est raccourcie à au plus carrés.

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)).

Python

Loading editor...

Vérification : coups_chomp
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).
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.

Python

Loading editor...

Vérification : graphe_chomp
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).
Question 10

Calculez l'attracteur de J1 pour une tablette (avec votre fonction 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.

Python

Loading editor...

Python

Loading editor...

Question 11

Pour toutes les tablettes avec , la position de départ est-elle gagnante pour J1 ? Cela confirme-t-il le résultat de l'exercice 2 du cours ?

Python

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.

Python

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.

Python

Loading editor...

Vérification : gagnant
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).
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).

Python

Loading editor...

Vérification : heuristique
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).
Question 14

Écrivez une fonction récursive minmax(plateau, joueur, p) qui renvoie la valeur du plateau, quand c'est à 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 - 1 des 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).

Python

Loading editor...

Vérification : minmax
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).
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.

Python

Loading editor...

Vérification : meilleur_coup
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).

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.

Python
code masqué : pas besoin de le lire pour suivre, exécutez-le simplement
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 ?

Python

Loading editor...

Python

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 ?

Python

Loading editor...

Réponse
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.

Python

Loading editor...


Entrez le code donné en cours pour accéder à la solution :