Mines Informatique Commune MP PC PSI 2026Sujet et rapport du jury

ÉCOLE NATIONALE DES PONTS et CHAUSSÉES, ISAE-SUPAERO, ENSTA, TÉLÉCOM PARIS, MINES PARIS - PSL, MINES SAINT-ÉTIENNE, MINES NANCY, IMT ATLANTIQUE, ENSAE PARIS, CHIMIE PARISTECH - PSL.

Jeu Quixo à deux joueurs.

1 Présentation

• -le joueur choisit l'un de ses cubes ou un cube neutre; le cube choisi est obligatoirement situé sur les bords du plateau (cases blanches sur la figure 1(a)),
• -le cube est ensuite replacé, en le passant à la marque du joueur s'il était neutre, pour pousser les autres cubes jusqu'à boucher la case libérée précédemment (figure 1(b)). Il est interdit de remettre le cube à sa place d'origine.

Figure 1 - Illustration du plateau de jeu

2 Jeu à deux joueurs humains

Figure 2 - Situation de jeu - Le joueur 1 doit jouer

• -alig(jeu:[[int]], joueur:int, i:int, n:int) -> bool qui renvoie True si un alignement de n pions du joueur passé en argument est trouvé sur la ligne i et False sinon;
• -acol(jeu:[[int]], joueur:int, j:int, n:int) -> bool qui renvoie True si un alignement de n pions du joueur passé en argument est trouvé sur la colonne j et False sinon;
• -adiag1(jeu: [[int]], joueur:int, n:int) -> bool qui renvoie True si un alignement de n pions du joueur passé en argument est trouvé sur la diagonale partant de (0, 0) et False sinon;
• -adiag2(jeu: [[int]], joueur:int, n:int) -> bool qui renvoie True si un alignement de n pions du joueur passé en argument est trouvé sur la diagonale partant de (0, 4) et False sinon.

3 Jeu contre un ordinateur

Figure 3 - Situation de jeu - Le joueur 1 doit jouer

Heuristique d'évaluation

• -si le plateau est gagnant alors on renvoie 100 + profondeur pour le joueur 1 et -100 - profondeur pour le joueur 2. La valeur 100 est conventionnelle. Elle est choisie uniquement pour favoriser les branches gagnantes.
• -sinon, on construit une valeur en fonction du joueur considéré :
  • -en ajoutant 5 fois le nombre d'alignements de 4 pions du joueur;
  • -en ajoutant 20 si la case centrale appartient au joueur;
  • -en ajoutant le nombre de pions du joueur et en soustrayant le nombre de pions de son adversaire ;
  • -en ajoutant la profondeur ;
  • -la fonction renvoie la valeur si le joueur considéré est le joueur 1 et l'opposé de cette valeur sinon.

Élagage "alphabeta"

Figure 4 - Illustration de l'élagage avec les coupures alpha et beta.

alphabeta(noeud, alpha, beta, profondeur)
    si noeud est une feuille ou profondeur atteinte alors
        renvoyer la valeur de l'heuristique du noeud
    profondeur = profondeur - 1
    si noeud de type Max alors
        v = -infini
        pour tout fils de noeud faire
            v = max(v, alphabeta(fils, alpha, beta, profondeur))
            si v >= beta alors #coupure beta
                renvoyer v
            alpha = max(alpha, v)
    sinon
        v = infini
        pour tout fils de noeud faire
            v = min(v, alphabeta(fils, alpha, beta, profondeur))
            si alpha >= v alors #coupure alpha
                renvoyer v
            beta = min(beta, v)
    renvoyer v

def alphabeta(jeu:[[int]], joueur:int, alpha:float, \
                    beta: float, profondeur:int) -> tuple:
    if ..................................... : #à compléter
        .......................................
        return eval, None
    profondeur = profondeur - 1
    meilleur_depl = None
    if joueur == 1: #noeud Max
        v = -math.inf
        for depl in deplacements_possibles(jeu, joueur):
            jeu_c = copy.deepcopy(jeu)
            deplacement_case(...................................)
            v = max(v, alphabeta(......................................)[0])
            if v >= beta:
                return v, meilleur_depl
            if v > alpha:
                alpha = v
                meilleur_depl = depl
    else: #noeud Min
        v = math.inf
        for depl in deplacements_possibles(jeu, joueur):
            jeu_c = copy.deepcopy(jeu)
            deplacement_case(.........NON DEMANDE................)
            v = min(v, alphabeta(............NON DEMANDE................)[0])
            if alpha >= v:
                return v, depl
            if v < beta:
                beta = v
                meilleur_depl = depl
    return v, meilleur_depl

4 Gestion d'une base de données

• -Partie avec les attributs :
  • -id l'identifiant d'une partie, clé primaire, de type entier ;
  • -id_joueur1 l'identifiant du joueur 1, clé étrangère, de type entier ;
  • -id_joueur2 l'identifiant du joueur 2, clé étrangère, de type entier ;
  • -id_gagnant l'identifiant du gagnant, clé étrangère, de type entier ;
  • -date la date de la partie, de type chaîne de caractères ;
  • -nbtours le nombre de tours de la partie, de type entier.
• -Joueur avec les attributs :
  • -id l'identifiant du joueur, clé primaire, de type entier ;
  • -nom le nom du joueur, de type chaîne de caractères ;
  • -prenom le prénom du joueur, de type chaîne de caractères.