L3 MIASHS, Algorithme et Programmation 3, année 2023

Vous devez rendre un unique fichier sur Moodle
Les notebooks ne seront pas corrigés (uniquement les fichiers *.py)
Vous pouvez utiliser un ou plusieurs fichiers
N’oubliez pas de commenter votre code
Un bout de code qui ne fonctionne sera corrigé si et seulement s’il est commenté.
Toute communication est interdite et entraine directement un 0 à l’UE et un signalement pour triche

Puissance 4

Le but du jeu est d’aligner une suite de 4 pions de même couleur sur une grille comptant 6 rangées et 7 colonnes. Chaque joueur dispose de 21 pions d’une couleur (par convention, en général jaune ou rouge). Tour à tour, les deux joueurs placent un pion dans la colonne de leur choix, le pion coulisse alors jusqu’à la position la plus basse possible dans ladite colonne à la suite de quoi c’est à l’adversaire de jouer. Le vainqueur est le joueur qui réalise le premier un alignement (horizontal, vertical ou diagonal) consécutif d’au moins quatre pions de sa couleur. Si, alors que toutes les cases de la grille de jeu sont remplies, aucun des deux joueurs n’a réalisé un tel alignement, la partie est déclarée nulle.

(source wikipedia

Nous allons créer une modelisation de ce jeu. Pour ce faire, on va stocker les données dans une tuple de tuple de booléen ou de None.

Créez une classe Grille qui possède les champs et méthodes suivantes:

un champ grille_data qui pointe vers le tuple de tuple
Une initialisation, qui initilise la grille avec que des None
ajout_jeton(self, colonne:Int, couleur:bool) : ajoute un jeton de couleur jaune (False) ou rouge (True) à la colonne colonne et retourne une nouvelle Grille si cela est valide et None sinon.
check(self): retourne True si la couleur rouge à gagné, False si la couleur jaune a gagné et None sinon.
Une jolie représentation en texte de la grille

Je vous donne la classe Joueur.

import random

class Joueur:
    def __init__(self, grille: Grille, couleur:bool):
        self.grille = grille
        self.couleur = couleur

    def play(self):
        next_grille = None 
        while next_grille is None:
            next_grille = self.grille.ajout_jeton(random.randint(0, 7), self.couleur)
        return next_grille

Écrire un script qui simule une partie en affichant la grille après chaque coup de chaque joueur.
Créer une class JoueurHumain qui étend Joueur et surcharge play pour permettre un choix humain.

Vous pouvez utiliser la fonction input pour demander un input à l’utilisateur en ligne de commande.

Faire une fonction main qui lance une partie entre un joueur humain et un joueur artificiel qui joue au hasard.

Une inteligence imbatable

On va améliorer le joueur artificiel qui n’est pas très drôle. On va pour cela devoir explorer l’espace des configurations. Une configuration est l’état de la grille à un moment donnée de la partie. Elle contient donc les informations suivantes:

Le prochain joueur
L’état de la grille

Modéliser une configuration par une classe Configuration qui étend grille en ajoutant l’information manquante. Elle doit par ailleurs implémenter:

une methode configuration_suivante qui retourne un iterateur sur les configuration que l’on peut avoir au coup d’après
une propriété est_gagnante qui retourne si le prochain joueur peut gagner en jouant.

Implementer un JoueurNiveauUn qui étend Joueur qui va regarder s’il existe une configuration gagnante et la selectionne.
Implementer un JoueurNiveauDeux qui va regarder s’il existe une configuation qui lui permette de gagner à coup sur au coup suivant.
On définit une configuration éventuellement gagnante par recurrence comme suit:

S’il existe un choix tel que le joueur qui choisit gagne la partie.
S’il existe un choix tel que le joueur qui choisit arrive dans une configuration éventuellement gagante.

Implémenter un JoueurAbsolu qui va systématiquement choisir une configuration éventuellement gagnante si elle existe et sinon jouer au hasard.
Montrer que JoueurAbsolu gagne a coup sur s’il commence.

Compiled the: ven. 05 sept. 2025 16:27:47 CEST