Composition d'informatique X-ENS MP : algorithmes de recherche pour jeux à un joueur (Rubik's Cube, taquin, solitaire)
Afficher ou masquer la section
Le sujet étudie différents algorithmes de recherche pour trouver des solutions optimales en nombre de coups à des jeux à un joueur comme le Rubik's Cube, le solitaire ou le taquin. Il progresse du parcours en largeur vers la recherche itérée en profondeur, puis vers une variante guidée par une fonction minorante, appliquée au jeu du taquin.
1Partie I : notion de jeu à un joueur et parcours en largeurIntroduction d'un exemple simple de jeu, preuve de correction et traduction en Caml d'un premier algorithme de parcours en largeur.
2Partie II : recherche itérée en profondeurÉtude d'un algorithme alternatif au parcours en largeur, avec comparaison de la complexité spatiale entre les deux méthodes.
3Partie III : recherche itérée en profondeur guidéeIntroduction d'une fonction minorant le nombre de coups restants pour réduire le nombre d'étapes de la recherche.
4Partie IV : application au jeu du taquinMise en œuvre de l'algorithme de la partie III sur le taquin, avec la difficulté du retour sur trace.
Difficile. Le rapport indique une moyenne de 9,72 sur 20 avec un écart type de 3,78, et signale que plusieurs questions (3, 9, 12) ont été très mal traitées, voire ignorées.
Deux tiers des copies environ (moyenne ± écart-type)
Votre note sur 20 à ce sujet, en conditions de concours.
Source : rapport du jury. Notes publiées par le concours (après harmonisation le cas échéant). Courbe : estimation par une loi normale.
Ce qu'a observé le jury
5 erreurs relevées
Complexités données à l'unité près · Preuves de correction non rigoureuses · Minoration du cardinal de A oubliée
Afficher ou masquer la section
Beaucoup de candidats sont parvenus jusqu'à la dernière question, mais aucun n'a su traiter toutes les questions correctement. Le jury regrette un manque de rigueur récurrent dans les preuves de correction et dans la traduction du pseudo-code en Caml.
Les erreurs les plus sanctionnées
1
Complexités données à l'unité près
Une proportion non négligeable de candidats donne des complexités à l'unité près, ce qui a peu de sens en informatique quand on attend seulement des estimations asymptotiques.
« Une proportion non négligeable de candidats donne des complexités à l’unité près, ce qui a peu de sens en informatique »
2
Preuves de correction non rigoureuses
Trop de copies se contentent de justifier la correction d'un algorithme en le paraphrasant en français ou en indiquant qu'on voit bien que, sans hypothèse de récurrence correctement identifiée.
3
Minoration du cardinal de A oubliéeQ3
À la question 3, très peu de candidats minorent correctement le cardinal de l'ensemble A, alors que la majoration est plus souvent trouvée.
4
Caml sans instruction return
Beaucoup de candidats semblent ignorer que Caml ne dispose pas d'une instruction return, ce qui rend la gestion des valeurs de retour incorrecte.
5
Retour sur trace mal réalisé au taquinQ17
La difficulté de la question 17 tient à la nécessité de bien revenir en arrière sur les choix infructueux ; très peu de candidats réalisent correctement ce retour sur trace.
Ce qui a été bien réussi
La question 1, très simple, a été traitée par la quasi-totalité des candidats avec un bon taux de réussite.
Beaucoup de candidats identifient correctement l'invariant que l'ensemble A contient exactement les états à profondeur p.
La question 14, plus simple qu'elle n'en a l'air, a été bien réussie.
Conseils du jury
Donner des estimations de complexité asymptotiques plutôt que des décomptes à l'unité près.
Rédiger des preuves de correction rigoureuses avec un invariant de boucle correctement identifié et formulé.
Soigner la présentation du code (couleur, indentation) et éviter de nommer des fonctions auxiliaires aux, aux2, aux3.
Synthèse rédigée par WikiPrépa à partir du rapport officiel du jury (à télécharger en PDF). Les citations sont extraites du rapport.
COMPOSITION D'INFORMATIQUE - A - (XULCR)
(Durée : 4 heures)
L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.
Le langage de programmation sera obligatoirement Caml.
Jeux à un joueur et solutions optimales
Nous nous intéressons ici à des jeux à un joueur où une configuration initiale est donnée et où le joueur effectue une série de déplacements pour parvenir à une configuration gagnante. Des casse-tête tels que le Rubik's Cube, le solitaire, l'âne rouge ou encore le taquin entrent dans cette catégorie. L'objectif de ce problème est d'étudier différents algorithmes pour trouver des solutions à de tels jeux qui minimisent le nombre de déplacements effectués.
La partie I introduit la notion de jeu à un joueur et un premier algorithme pour trouver une solution optimale. Les parties II et III proposent d'autres algorithmes, plus efficaces. La partie IV a pour objectif de trouver une solution optimale au jeu du taquin.
Les parties I, II et III peuvent être traitées indépendamment. Néanmoins, chaque partie utilise des notations et des fonctions introduites dans les parties précédentes. La partie IV suppose qu'on a lu entièrement l'énoncé de la partie III.
Complexité
Par complexité en temps d'un algorithme A on entend le nombre d'opérations élémentaires (comparaison, addition, soustraction, multiplication, division, affectation, test, etc) nécessaires à l'exécution de A dans le cas le pire. Par complexité en espace d'un algorithme A on entend l'espace mémoire minimal nécessaire à l'exécution de A dans le cas le pire. Lorsque la complexité en temps ou en espace dépend d'un ou plusieurs paramètres κ_0, ⋯, κ_(r − 1), on dit que A a une complexité en O(f(κ_0, ⋯, κ_(r − 1))) s'il existe une constante C > 0 telle que, pour toutes les valeurs de κ_0, ⋯, κ_(r − 1) suffisamment grandes (c'est-à-dire plus grandes qu'un certain seuil), pour toute instance du problème de paramètres κ_0, ⋯, κ_(r − 1), la complexité est au plus Cf(κ_0, ⋯, κ_(r − 1)).
BFS()
$A \leftarrow\left\{e_{0}\right\}$
$p \leftarrow 0$
tant que $A \neq \emptyset$
$B \leftarrow \emptyset$
pour tout $x \in A$
si $x \in F$ alors
renvoyer VRAI
$B \leftarrow s(x) \cup B$
$A \leftarrow B$
$p \leftarrow p+1$
renvoyer FAUX
Figure 1 - Parcours en largeur.
Partie I. Jeu à un joueur, parcours en largeur
Un jeu à un joueur est la donnée d'un ensemble non vide E, d'un élément e_0 ∈ E, d'une fonction s : E → P(E) et d'un sous-ensemble F de E. L'ensemble E représente les états possibles du jeu. L'élément e_0 est l'état initial. Pour un état e, l'ensemble s(e) représente tous les états atteignables en un coup à partir de e. Enfin, F est l'ensemble des états gagnants du jeu. On dit qu'un état e_p est à la profondeur p s'il existe une séquence finie de p + 1 états
e_0 e_1…e_p
avec e_(i + 1) ∈ s(e_i) pour tout 0 ≤ i < p. Si par ailleurs e_p ∈ F, une telle séquence est appelée une solution du jeu, de profondeur p. Une solution optimale est une solution de profondeur minimale. On notera qu'un même état peut être à plusieurs profondeurs différentes.
Voici un exemple de jeu :
E, = ℕ^⋆; e_0, = 1; s(n), = {2n, n + 1}
Question 1. Donner une solution optimale pour ce jeu lorsque F = {42}.
Parcours en largeur. Pour chercher une solution optimale pour un jeu quelconque, on peut utiliser un parcours en largeur. Un pseudo-code pour un tel parcours est donné figure 1.
Question 2. Montrer que le parcours en largeur renvoie VRAI si et seulement si une solution existe.
Question 3. On se place dans le cas particulier du jeu (1) pour un ensemble F arbitraire pour lequel le parcours en largeur de la figure 1 termine. Montrer alors que la complexité en temps et en espace est exponentielle en la profondeur p de la solution trouvée. On demande de montrer que la complexité est bornée à la fois inférieurement et supérieurement par deux fonctions exponentielles en p.
$\operatorname{DFS}(m, e, p)$
si $p>m$ alors
renvoyer FAUX
si $e \in F$ alors
renvoyer VRAI
pour chaque $x$ dans $s(e)$
si $\operatorname{DFS}(m, x, p+1)=$ VRAI alors
renvoyer VRAI
renvoyer FAUX
Figure 2 - Parcours en profondeur (partie II), limité par une profondeur maximale m.
Programmation. Dans la suite, on suppose donnés un type etat et les valeurs suivantes pour représenter un jeu en Caml :
Question 4. Écrire une fonction bfs: unit -> int qui effectue un parcours en largeur à partir de l'état initial et renvoie la profondeur de la première solution trouvée. Lorsqu'il n'y a pas de solution, le comportement de cette fonction pourra être arbitraire.
Indication : On pourra avantageusement réaliser les ensembles A et B par des listes, sans chercher à éliminer les doublons, et utiliser une fonction récursive plutôt qu'une boucle while.
Question 5. Montrer que la fonction bfs renvoie toujours une profondeur optimale lorsqu'une solution existe.
Partie II. Parcours en profondeur
Comme on vient de le montrer, l'algorithme BFS permet de trouver une solution optimale mais il peut consommer un espace important pour cela, comme illustré dans le cas particulier du jeu (1) qui nécessite un espace exponentiel. On peut y remédier en utilisant plutôt un parcours en profondeur. La figure 2 contient le pseudo-code d'une fonction DFS effectuant un parcours en profondeur à partir d'un état e de profondeur p, sans dépasser une profondeur maximale m donnée.
Question 6. Montrer que DFS(m, e_0, 0) renvoie VRAI si et seulement si une solution de profondeur inférieure ou égale à m existe.
Recherche itérée en profondeur. Pour trouver une solution optimale, une idée simple consiste à effectuer un parcours en profondeur avec m = 0, puis avec m = 1, puis avec m = 2, etc., jusqu'à ce que DFS(m, e_0, 0) renvoie VRAI.
Question 7. Écrire une fonction ids: unit → int qui effectue une recherche itérée en profondeur et renvoie la profondeur d'une solution optimale. Lorsqu'il n'y a pas de solution, cette fonction ne termine pas.
Question 8. Montrer que la fonction ids renvoie toujours une profondeur optimale lorsqu'une solution existe.
Question 9. Comparer les complexités en temps et en espace du parcours en largeur et de la recherche itérée en profondeur dans les deux cas particuliers suivants :
il y a exactement un état à chaque profondeur p;
il y a exactement 2^p états à la profondeur p.
On demande de justifier les complexités qui seront données.
Partie III. Parcours en profondeur avec horizon
On peut améliorer encore la recherche d'une solution optimale en évitant de considérer successivement toutes les profondeurs possibles. L'idée consiste à introduire une fonction h : E → ℕ qui, pour chaque état, donne un minorant du nombre de coups restant à jouer avant de trouver une solution. Lorsqu'un état ne permet pas d'atteindre une solution, cette fonction peut renvoyer n'importe quelle valeur.
Commençons par définir la notion de distance entre deux états. S'il existe une séquence de k + 1 états x_0 x_1⋯x_k avec x_(i + 1) ∈ s(x_i) pour tout 0 ≤ i < k, on dit qu'il y a un chemin de longueur k entre x_0 et x_k. Si de plus k est minimal, on dit que la distance entre x_0 et x_k est k.
On dit alors que la fonction h est admissible si elle ne surestime jamais la distance entre un état et une solution, c'est-à-dire que pour tout état e, il n'existe pas d'état f ∈ F situé à une distance de e strictement inférieure à h(e).
On procède alors comme pour la recherche itérée en profondeur, mais pour chaque état e considéré à la profondeur p on s'interrompt dès que p + h(e) dépasse la profondeur maximale m (au lieu de s'arrêter simplement lorsque p > m ). Initialement, on fixe m à h(e_0). Après chaque parcours en profondeur infructueux, on donne à m la plus petite valeur p + h(e) qui a dépassé m pendant ce parcours, le cas échéant, pour l'ensemble des états e rencontrés dans ce parcours. La figure 3 donne le pseudo-code d'un tel algorithme, appelé IDA ^⋆, où la variable globale min est utilisée pour retenir la plus petite valeur ayant dépassé m.
Question 10. Écrire une fonction idastar: unit → int qui réalise l'algorithme IDA* et renvoie la profondeur de la première solution rencontrée. Lorsqu'il n'y a pas de solution, le comportement de cette fonction pourra être arbitraire. Il est suggéré de décomposer le code en plusieurs fonctions. On utilisera une référence globale min dont on précisera le type et la valeur retenue pour représenter ∞.
Question 11. Proposer une fonction h admissible pour le jeu (1), non constante, en supposant que l'ensemble F est un singleton {t} avec t ∈ ℕ^⋆. On demande de justifier que h est admissible.
Question 12. Montrer que, si la fonction h est admissible, la fonction idastar renvoie toujours une profondeur optimale lorsqu'une solution existe.
$\mathrm{DFS}^{\star}(m, e, p) \xlongequal{\text { def }}$
$c \leftarrow p+h(e)$
si $c>m$ alors
si $c<$ min alors
$\min \leftarrow c$
renvoyer FAUX
si $e \in F$ alors
renvoyer VRAI
pour chaque $x$ dans $s(e)$
si $\mathrm{DFS}^{\star}(m, x, p+1)=$ VRAI alors
renvoyer VRAI
renvoyer FAUX
Figure 3 - Pseudo-code de l'algorithme IDA*.
Partie IV. Application au jeu du taquin
Le jeu du taquin est constitué d'une grille 4 × 4 dans laquelle sont disposés les entiers de 0 à 14, une case étant laissée libre. Dans tout ce qui suit, les lignes et les colonnes sont numérotées de 0 à 3 , les lignes étant numérotées du haut vers le bas et les colonnes de la gauche vers la droite. Voici un état initial possible :
0
2
3
0
2
3
1
6
_1
14
5
8
4
^2
12
7
9
^2
10
13
11
0
On obtient un nouvel état du jeu en déplaçant dans la case libre le contenu de la case située au-dessus, à gauche, en dessous ou à droite, au choix. Si on déplace par exemple le contenu de la case située à droite de la case libre, c'est-à-dire 12, on obtient le nouvel état suivant :
2
3
1
6
14
5
8
4
12
7
9
10
13
11
0
Le but du jeu du taquin est de parvenir à l'état final suivant :
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Ici, on peut le faire à l'aide de 49 déplacements supplémentaires et il n'est pas possible de faire moins.
Question 13. En estimant le nombre d'états du jeu du taquin, et la place mémoire nécessaire à la représentation d'un état, expliquer pourquoi il n'est pas réaliste d'envisager le parcours en largeur de la figure 1 pour chercher une solution optimale du taquin.
Fonction h. On se propose d'utiliser l'algorithme IDA* pour trouver une solution optimale du taquin et il faut donc choisir une fonction h. On repère une case de la grille par sa ligne i (avec 0 ≤ i ≤ 3, de haut en bas) et sa colonne j (avec 0 ≤ j ≤ 3, de gauche à droite). Si e est un état du taquin et v un entier entre 0 et 14 , on note e_v^i la ligne de l'entier v dans e et e_v^j la colonne de l'entier v dans e. On définit alors une fonction h pour le taquin de la façon suivante:
Question 14. Montrer que cette fonction h est admissible.
Programmation. Pour programmer le jeu de taquin, on abandonne l'idée d'un type etat et d'une fonction suivants, au profit d'un unique état global et modifiable. On se donne pour cela une matrice grid de taille 4 × 4 contenant l'état courant e ainsi qu'une référence h contenant la valeur de h(e).
grid: int vect vect
h: int ref
La matrice grid est indexée d'abord par i puis par j. Ainsi grid. (i). (j) est l'entier situé à la ligne i et à la colonne j. Par ailleurs, la position de la case libre est maintenue par deux références :
li: int ref
lj: int ref
La valeur contenue dans grid à cette position est non significative.
Question 15. Écrire une fonction move: int → int → unit telle que move ij déplace l'entier situé dans la case ( i, j ) vers la case libre supposée être adjacente. On prendra soin de bien mettre à jour les références h, li et lj. On ne demande pas de vérifier que la case libre est effectivement adjacente.
Déplacements et solution. De cette fonction move, on déduit facilement quatre fonctions qui déplacent un entier vers la case libre, respectivement vers le haut, la gauche, le bas et la droite.
let haut () = move (!li + 1) !lj;;
let gauche () = move !li (!lj + 1);;
let bas () = move (!li - 1) !lj;;
let droite () = move !li (!lj - 1);;
Ces quatre fonctions supposent que le mouvement est possible.
Pour conserver la solution du taquin, on se donne un type deplacement pour représenter les quatre mouvements possibles et une référence globale solution contenant la liste des déplacements qui ont été faits jusqu'à présent.
type deplacement = Gauche | Bas | Droite | Haut
solution: deplacement list ref
La liste !solution contient les déplacement effectués dans l'ordre inverse, i.e., la tête de liste est le déplacement le plus récent.
Question 16. Écrire une fonction tente_gauche: unit → bool qui tente d'effectuer un déplacement vers la gauche si cela est possible et si le dernier déplacement effectué, le cas échéant, n'était pas un déplacement vers la droite. Le booléen renvoyé indique si le déplacement vers la gauche a été effectué. On veillera à mettre à jour solution lorsque c'est nécessaire.
On suppose avoir écrit de même trois autres fonctions
tente_bas : unit -> bool
tente_droite: unit -> bool
tente_haut : unit -> bool
Question 17. Écrire une fonction dfs: int → int → bool correspondant à la fonction DFS* de la figure 3 pour le jeu du taquin. Elle prend en argument la profondeur maximale m et la profondeur courante p. (L'état e est maintenant global.)
Question 18. En déduire enfin une fonction taquin: unit → deplacement list qui renvoie une solution optimale, lorsqu'une solution existe.
Note : Trouver une solution au taquin n'est pas très compliqué, mais trouver une solution optimale est nettement plus difficile. Avec ce qui est proposé dans la dernière partie de ce sujet, on y parvient en moins d'une minute pour la plupart des états initiaux et en une dizaine de minutes pour les problèmes les plus difficiles.
Questions fréquentes
3 questions
Sur quels chapitres porte la composition d'informatique X-ENS MP 2017 ?
Afficher ou masquer la section
Sur quels chapitres porte la composition d'informatique X-ENS MP 2017 ?
+
Le sujet porte sur les algorithmes de recherche pour jeux à un joueur : parcours en largeur, recherche itérée en profondeur et sa variante guidée par une fonction minorante, appliqués au Rubik's Cube et au taquin.
Quelles erreurs le jury a-t-il le plus relevées à l'X-ENS informatique MP 2017 ?
+
Des complexités données à l'unité près au lieu d'estimations asymptotiques, des preuves de correction non rigoureuses, et une traduction fantaisiste du pseudo-code en Caml, notamment autour de l'absence de return.
Oui, la moyenne s'établit à 9,72 sur 20 avec un écart type de 3,78, et plusieurs questions ont été très mal traitées ou ignorées par une large majorité des candidats.
Pas de description pour le moment
Commentaires• X ENS Option Informatique MP 2017
Connectez-vous pour participer aux discussions
Partagez vos avis, posez des questions et échangez avec la communauté
Même chapitre : Preuves de correction et…Centrale Informatique MPI 2023Centrale · 2023Corrigé
Même année, MinesMines Option Informatique MP 2017Mines · 2017Corrigé
Même année, E3AE3A Option Informatique MP 2017E3A · 2017Corrigé