2024-Epita-Info-MpPcPsi-Corrigé

Concours CPGE EPITA-IPSA-ESME

2024 Épreuve de Sciences du numérique MP-PC-PSI-PT-TSI Le sujet est composé d’un problème et d’un questionnaire à choix multiples. Le questionnaire à choix multiples devra être inséré dans votre copie.

Les fonctions à produire dans ce sujet devront être rédigées en langage Python et se limiter aux éléments décrits ci-après. Il est possible d’écrire des fonctions auxiliaires non explicitement demandées à condition de les documenter et de les définir avant d’en faire usage.

Éléments du langage Python autorisés

Types de base

— Opérations sur les entiers (int) : +, -, *, //, **, % avec des opérandes positifs.

— Opérations sur les flottants (float) : +, -, *, /, **.

— Opérations sur les booléens (bool) : not, or, and.

— Comparaisons ==, !=, <, >, <=, >=.

Types structurés

— Structures indicées immuables (chaînes, n-uplets) :

— longueur len ;

— accès ;

— concaténation + ;

— répétition * ;

— extraction de tranche (slicing).

— Listes :

— création par description complète, par compréhension ou par append successifs ;

— longueur len ;

— accès ;

— concaténation + ;

— extraction de tranche (slicing) ;

— répétition * ;

— pop sans paramètres.

— Dictionnaires : création, accès, insertion, longueur len.

Structures de contrôle

— Instruction d’affectation avec =, += ou -= et dépaquetage de n-uplets : (x,y)=(4,2).

— Instruction conditionnelle : if, elif, else.

— Boucle while (sans else). break, return dans un corps de boucle.

— Boucle for (sans else) et itération sur range(a, b), une chaîne, un n-uplet, une liste, un dictionnaire au travers des méthodes keys et items.

— Définition d’une fonction def f(p 1 , …, p n ), return.

Remarques particulières :

— Le mot clé in pourra être utilisé dans une boucle for (for x in …) mais pas pour effectuer un test d’appartenance (if x in …).

— L’usage de modules n’est pas autorisé ; en particulier l’usage de la fonction deepcopy du module copy est proscrit.

Problème – Jeu de reversi

Déroulé du jeu et premières fonctions

Le jeu de reversi se compose d’un plateau carré de n = 8 cases de côté ainsi que de jetons blancs et noirs. Deux joueurs s’affrontent à tour de rôle en posant un jeton sur le plateau.

Le joueur qui possède les jetons noirs commence la partie et sera appelé {J_1} tandis que son adversaire sera appelé {J_2}.

On considère dans ce problème que le plateau de jeu est initialement rempli comme représenté par la figure 1.

Les lignes sont traditionnellement numérotées de 1 à 8 et les colonnes des lettres a à h.

Dans ce sujet l’implémentation considèrera que les lignes et les colonnes sont numérotées de 0 à 7, en préservant l’ordre de nommage de la numérotation traditionnelle. Ainsi la case (8, a) sera représentée informatiquement par le couple (7,0).

On décide de représenter le plateau de jeu p par une liste de listes. Le contenu de la case (i,j) sera représenté par la valeur de p[i][j]. Cette valeur sera 0 lorsque la case est vide, 1 lorsqu’un jeton noir y est présent et -1 lorsqu’un jeton blanc s’y trouve.

Ainsi la valeur de p[3][4] représente donc la valeur de la case (4, e) de valeur 1. Les joueurs seront représentés par la couleur de leurs jetons, ainsi {J_1} sera représenté par la valeur 1 et {J_2} par la valeur -1.

On appellera joueur actif le joueur dont c’est le tour de jouer. Ce joueur doit poser un jeton sur une case jouable, c’est-à-dire une case libre lui permettant de faire une capture (voir ci-après) ; dans le cas où il n’existe pas de telle case, l’opposant rejoue.

Si plus personne ne peut jouer, le jeu s’arrête. La figure 3 présente une configuration du plateau de jeu où les coups jouables par {J_1} ont été représentés par un •.

On parle de capture, lorsqu’il existe un alignement d’au moins un jeton adverse (en ligne, en colonne ou en diagonale) compris entre un jeton du joueur actif et le jeton qu’il s’apprête à poser.

Lorsqu’une capture a lieu, l’ensemble des jetons adverses de l’alignement sont retournés ; c’est-à-dire qu’ils changent de couleur et donc de propriétaire. La direction d’une capture sera orientée à partir du jeton posé et dans la direction de l’alignement des jetons à retourner.

On représentera les directions de capture par un couple (dx,dy) conformément au tableau de la figure 2 :

Dans la configuration de la figure 3, {J_1} peut par exemple :

— poser un jeton noir en (2, e).

Il capturera alors les 2 jetons adverses situés en (3, e) et en (4, e) (selon la direction (1,0)).

— poser un jeton noir en (3, d).

Dans ce cas il y aura une capture selon deux alignements : l’alignement entre (3, d) et (5, d), de direction (1,0), capturera un jeton et celui entre (3, d) et (5, f ), de direction (1,1), en capturera un autre. La figure 4 représente le plateau une fois ces captures effectuées.

On notera qu’une capture peut donc s’effectuer selon plusieurs directions.

Le jeu se termine lorsque plus aucun joueur ne peut jouer, en général cela se produit lorsque le plateau est entièrement rempli mais il est également possible que {J_1} et {J_2} n’aient plus de case jouable.

Est considéré comme gagnant le joueur possédant le plus de jetons de sa couleur. On définit alors le score d’un plateau comme étant la différence entre le nombre de ses jetons noirs et le nombre de ses jetons blancs.

On considère à présent les cases vides ayant au moins une case voisine occupée par un jeton. Ces cases seront appelées cases frontières (voir figure 4). On remarquera que les cases jouables font nécessairement partie des cases frontières.

Implémentation d’une intelligence artificielle

On souhaite à présent concevoir des fonctions permettant de jouer seul contre la machine.

Faute de temps, il n’est pas envisageable (du moins dès le début du jeu) d’explorer tous les plateaux possibles. Cela nous conduit à devoir évaluer la qualité d’un plateau de jeu alors qu’il reste des coups jouables.

On se dote d’une fonction d’évaluation f s’appliquant à un plateau de jeu et retournant un entier représentant une évaluation quantifiée du plateau. Plus la note est élevée, plus elle est avantageuse pour {J_1} ; dans le cas contraire elle est avantageuse pour {J_2}.

Une première idée pour évaluer un plateau serait d’utiliser le résultat de la fonction score. La présence de jetons sur certaines positions stratégiques du plateau est également un indicateur intéressant à prendre en considération.

Par exemple, tout jeton posé dans un coin du plateau ne pourra plus être retourné. Dès lors on choisit d’évaluer un plateau par la fonction d’évaluation {f:p\mapsto\sum\limits_{i=0}^7\sum\limits_{j=0}^7p[i][j]F[i][j]} où F[i][j] est une valeur quantifiant l’importance de la capture de la case située en ligne i et colonne j.

Ainsi si on considère que la capture des coins du plateau est importante, on attribuera une forte valeur à F[0][0], F[0][7], F[7][0] et F[7][7]. Dans ce sujet on ne cherche pas à déterminer F ; on prendra alors simplement f comme paramètre de nos fonctions.

On souhaite à présent développer un algorithme envisageant tous les plateaux possibles, n coups à l’avance. La figure 5 présente un arbre d’exploration à 3 coups d’avance. Les nœuds de l’arbre, représentés par un •, correspondent chacun à une configuration du plateau.

Lorsqu’il est possible de passer d’un plateau à un autre en jouant en case {c_{i,j}}, on relie les deux nœuds correspondant par une arête d’étiquette {c_{i,j}}.

Les {c_{i,j}} représentent donc les cases jouables pour le joueur actif.

Dans cet exemple, {J_1} commence à jouer et dispose de 3 cases possibles pour poser son jeton.

S’il joue en case {c_{1,1}}, on suppose que la partie s’arrête (par exemple lorsque plus aucun joueur ne dispose de coup jouable) et que {J_1} dispose de moins de jetons que {J_2}, auquel cas il perd la partie. Il peut aussi jouer en case {c_{1,2}} ou en case {c_{1,3}}.

Dans ce cas, {J_2} joue à son tour et dispose dans tous les cas de 2 cases jouables. {J_1} peut alors jouer à son tour une troisième fois. On a alors envisagé 3 coups d’avance et on arrête ici notre exploration. Afin de décider du meilleur coup à jouer, on doit évaluer les 9 feuilles de l’arbre.

Dans le cas où {J_1} perd, on évaluera le plateau à {-\infty}, dans le cas où {J_1} gagne, on évaluera le plateau à {+\infty}. Dans les autres cas, on fera appel à la fonction d’évaluation f pour évaluer le plateau de jeu.

Pour des raisons d’implémentation on choisira pour {+\infty} la valeur 10000 et pour {-\infty} la valeur -10000 en faisant l’hypothèse que la fonction f renvoie des entiers strictement compris entre ces deux valeurs.

Lors du tour de chaque joueur, l’algorithme considèrera que chaque joueur joue le coup qui lui est le plus avantageux au regard de l’évaluation du plateau obtenue. La figure 6 représente l’arbre des évaluations déduites (de bas en haut) par l’algorithme.

Finalement dans notre exemple le joueur {J_1} aura intérêt à jouer en case {c_{1,3}}.

Evaluation statistique des parties

On associe à tout plateau {p} son encodage défini par la quantité : {\sum\limits_{i=0}^7\sum\limits_{j=0}^7(p[i][j]+1)3^{8i+j}}

On stocke à présent dans une base de données quelques informations sur les parties jouées et on fera l’hypothèse que les encodages de plateaux peuvent, malgré leur taille, être stockés dans notre base de données. On répartit ces informations en 3 tables dont on présente des extraits ci-après.

La première ligne représente les noms des champs et les suivantes les enregistrements. La clé primaire de chaque table est indiquée en première colonne. Les clés étrangères seront soulignées. Une première table joueurs permet de stocker les informations personnelles des joueurs :

Une seconde table parties permet de stocker les statistiques d’une partie terminée. joueurs_idJ1 permet de déterminer le joueur ayant les jetons noirs, joueurs_idJ2 celui ayant les jetons blancs et joueurs_idGagnant permet d’identifier le joueur ayant remporté la partie.

Ainsi les valeurs des champs joueurs_idJ1, joueurs_idJ2 et joueurs_idGagnant sont des clés étrangères du champ idJoueur de la table joueurs. Le champ score contiendra le score du plateau de fin de partie.

Une troisième table plateaux recense les informations des plateaux de jeu pour lesquels l’intelligence artificielle a eu à se prononcer.

On stocke alors l’identifiant idPartie de la partie concernée dans parties_idPartie qui sera donc une clé étrangère, codePlateau contiendra l’encodage du plateau analysé, profondeur la profondeur de l’analyse, evaluation le résultat de l’évaluation du plateau et joueurActif vaudra 1 si le joueur actif joue les jetons noirs et -1 sinon.

Enfin, les champs caseX et caseY contiendront les numéros de ligne et de colonne du meilleur coup à jouer trouvé.

QCM – MP-PC-PSI-PT-TSI

Dans ce questionnaire à choix multiples, chaque question comporte une ou plusieurs bonnes réponses. Chaque réponse correcte fait gagner des points, mais chaque réponse fausse annule tous les points de la question.

Les questions sont majoritairement formulées au pluriel par commodité d’expression. Cela n’implique pas nécessairement qu’elles admettent plusieurs réponses correctes. On considère les deux fonctions Python suivantes :