Corrigé Mines-Ponts 2026 Informatique commune MP-PC-PSI — Partie 3 (Q12 à Q19) : Jeu contre l'ordinateur : minimax, heuristique d'évaluation, élagage alpha-bêta

Sujet officiel du concours Mines-Ponts, session 2026, épreuve Informatique commune MP-PC-PSI. Corrigé rédigé par Ibrahim Alame.

Sujet officiel (PDF, site du concours)

Énoncé

Mouvements. Un mouvement est une liste [i_d, j_d, i_n, j_n] (départ, arrivée). La fonction deplacements_possibles(jeu, joueur) du cahier réponse parcourt $j = 0, \dots, 4$ en traitant la case $(0, j)$ puis la case $(4, j)$ , puis $i = 1, 2, 3$ en traitant $(i, 0)$ puis $(i, 4)$ ; arrivées ajoutées, pour chaque case prenable : $(0, j) \to (0, 0)$ [si $j \neq = 0$ ], $(0, 4)$ [si $j \neq = 4$ ], $(4, j)$ ; $(4, j) \to (4, 0)$ [si $j \neq = 0$ ], $(4, 4)$ [si $j \neq = 4$ ], $(0, j)$ ; $(i, 0) \to (i, 4)$ , $(0, 0)$ , $(4, 0)$ ; $(i, 4) \to (i, 0)$ , $(0, 4)$ , $(4, 4)$ .

Figure 3 — Situation de jeu, le joueur 1 doit jouer.

Arbre du cahier réponse. Carrés : tours du joueur MAX ; ronds : tours du joueur MIN ; les $16$ feuilles portent le score de chaque configuration atteinte en $4$ tours.

Évaluation (profondeur : tours restant à explorer). Plateau gagnant : $100 + profondeur$ (joueur 1 gagnant) ou $- 100 - profondeur$ (joueur 2). Sinon, pour le joueur considéré : $5 \times$ (nombre d'alignements de $4$ ) $+ 20$ s'il occupe la case centrale $+$ (ses pions $-$ ceux de l'adversaire) $+$ profondeur ; on renvoie cette valeur pour le joueur 1, son opposée pour le joueur 2.

Élagage alpha-bêta. Sous un nœud MAX qui vaut déjà au moins $a$ , un fils MIN dont un fils vaut au plus $a$ n'a plus besoin d'être exploré (coupure alpha) ; symétriquement sous un nœud MIN (coupure bêta).

Figure 4 — Coupures alpha et bêta.

alphabeta(jeu, joueur, alpha, beta, profondeur) renvoie (valeur, meilleur déplacement) ; lignes 3--4 : feuille ou profondeur atteinte, on évalue ; lignes 12--13 : jouer depl sur la copie jeu_c, puis récursion ; le joueur 1 est MAX.

Q12. Nombre exact de mouvements du joueur 1 sur le plateau initial ; une situation où ce nombre est minimal, et ce nombre.
Q13. Compléter l'arbre par la stratégie minimax.
Q14. Faisabilité du minimax pour ce jeu : nombre de mouvements dans le pire des cas sur $3$ tours depuis la situation initiale.
Q15. Que renvoie deplacements_possibles sur la figure 3 pour le joueur 1 (dans l'ordre) ?
Q16. Écrire alignement_4(jeu, joueur), nombre d'alignements de $4$ du joueur, avec alig, acol, …
Q17. Écrire evaluation(jeu, joueur, profondeur).
Q18. Reprendre l'arbre de Q13 avec l'élagage alpha-bêta, de gauche à droite : nœuds calculés et coupures.
Q19. Compléter les lignes 3, 4, 12 et 13 de alphabeta.

Corrigé

Q12. Plateau initial. Tous les cubes sont neutres, donc les $16$ cubes du bord sont prenables. Un coin se réinsère à $2$ endroits (l'autre extrémité de sa ligne et de sa colonne), une case de bord hors coin à $3$ endroits (Q4, Q7) :

$4 \times 2 + 12 \times 3 = 44 mouvements.$

La fonction deplacements_possibles du cahier réponse, exécutée sur le plateau vide, renvoie bien une liste de longueur $44$ .

Situation minimale. Si tous les cubes du bord sont à l'adversaire, le joueur n'a aucun mouvement ; mais alors la ligne $0$ est entièrement à l'adversaire, qui a déjà gagné, et la partie est finie. Dans une partie en cours, aucune des quatre lignes du bord (lignes $0$ et $4$ , colonnes $0$ et $4$ ) n'est entièrement à l'adversaire : il faut donc au moins un cube prenable sur chacune. Un cube touche au plus deux de ces lignes (s'il est dans un coin) : il faut au moins deux cubes prenables, deux coins opposés au mieux, soit $2 \times 2 = 4$ mouvements. Exemple pour le joueur 1 (X) : tout le bord est O sauf les coins $(0, 0)$ et $(4, 4)$ , qui sont X, avec le centre neutre (aucun alignement de cinq, ni pour X, ni pour O) :

deplacements_possibles renvoie alors $4$ mouvements, et gagnant est faux pour les deux joueurs. Le nombre minimal est donc $4$ ( $0$ si l'on admet une position déjà gagnée par l'adversaire). Vérification exhaustive exécutée : sur les $3^{16}$ remplissages possibles du bord (intérieur neutre), aucun plateau sans alignement de cinq ne donne moins de $4$ mouvements, et seules les deux paires de coins opposés l'atteignent.

Q13. Minimax : on remonte depuis les feuilles ; un nœud MIN (rond) prend le minimum de ses fils, un nœud MAX (carré) le maximum.

ronds du bas : $min (12, 13) = 12$ , $min (11, 14) = 11$ , $min (16, 17) = 16$ , $min (15, 16) = 15$ , $min (17, 4) = 4$ , $min (2, 3) = 2$ , $min (5, 24) = 5$ , $min (26, 22) = 22$ ;
carrés : $max (12, 11) = 12$ , $max (16, 15) = 16$ , $max (4, 2) = 4$ , $max (5, 22) = 22$ ;
ronds : $min (12, 16) = 12$ , $min (4, 22) = 4$ ;
racine : $max (12, 4) = 12$ .

La valeur du jeu est $12$ : MAX joue le premier coup (branche de gauche), et le chemin en gras est la partie jouée si chacun joue au mieux. Le $26$ de droite est un leurre : MIN n'y laisserait jamais aller.

Q14. Pire des cas. Au premier tour, $44$ mouvements (Q12). Au deuxième tour, le cube X posé au premier tour (toujours au bord) n'est plus prenable par le joueur 2 : au plus $44 - 2 = 42$ mouvements (s'il est dans un coin) ; de même au troisième tour. D'où une majoration

$44 \times 42 \times 42 = 77616 \leq 4 4^{3} = 85184 \approx 8, 5 \times 1 0^{4} feuilles.$

100 % gratuit

La suite du corrigé est sur Adloun

Le corrigé rédigé en entier, question par question, et le tuteur pour poser des questions sur ce sujet.

Voir le corrigé complet, gratuitement

Inscription gratuite en 30 secondes (e-mail, nom d'utilisateur, mot de passe, classe ou profil), sans carte bancaire : arrivée directe sur le corrigé.

Toutes les parties de l'épreuve

Corrigé complet gratuit →