Cliquez sur le lien src.zip (boutton gauche), puis sur le boutton «Extraire», enfin sélectionnez le répertoire de votre projet (TD1) lorsque l'outil de décompression vous le demandera et cliquez à nouveau sur le boutton «Extraire».
Dans Visual Studio Code, tapez la combinaison de touches [Ctrl]+[,] (la second touche c'est `virgule'), indiquez vm args dans la barre de recherche. L'item Java>Debug>settings: Vm Args apparaît avec une barre de texte dans laquelle vous devez écrire -ea (pour enable asserts).
Nommez les classes, variables et méthodes exactement comme le demande l'énoncé.
Pour des questions relatives à la syntaxe de Java, consultez ce mémento.
Pour obtenir la description d'une classe Java standard, consultez internet. Il suffit souvent d'effectuer une recherche en indiquant Java suivi du nom de la classe dont vous souhaitez la documentation (e.g. Java LinkedList ou Java Array).
La documentation officielle (internet) est ici : Java 11.
Afin de minimiser les risques d'erreurs de manipulation lors des
dépôts de fichiers, toutes
les classes que vous avez à modifier sont réunies dans un même
fichier TD1.java que vous devez déposer après chaque
question.
(On rappelle néanmoins qu'en dehors de circonstances
exceptionnelles, on écrit plutôt des classes différentes dans des
fichiers différents, tant pour la lisibilité du code que pour
l'efficacité de la compilation.)
La bataille est un jeu de cartes qui oppose deux joueurs. Au début de chaque partie, on sépare aléatoirement les 52 cartes du jeu en deux paquets de même taille attribués à chacun des deux adversaires. L'issue d'une partie est entièrement déterminée par la répartition initiale des cartes. C'est donc un jeu sans intérêt mais qui, en contrepartie, peut être entièrement automatisé. Le but de ce TD est d'écrire un programme qui mélange les cartes et décide, en fonction de la répartition initiale, si la partie se termine et quel est le gagnant (le «match nul» est possible). En particulier le programme devra être capable de simuler une partie.
Un jeu de cartes standard contient 52 cartes, chacune étant caractérisée par
Dans ce qui suit, nbVals désigne le nombre de valeurs différentes dans le jeu de cartes, soit 13 en principe, mais on se laisse la possibilité d'en utiliser plus ou moins dans les tests. En revanche, on s'engage à toujours utiliser 4 couleurs. Le paquet contient donc 4 cartes de chaque valeur, soit 4*nbVals cartes au total. Par convention, on numérotera les valeurs de 1 à nbVals.
La couleur des cartes n'est pas prise en compte au jeu de Bataille. Un paquet de cartes (Deck en anglais) est donc une file d'entiers (on prend au dessus, on ajoute en dessous) dont tous les éléments sont compris entre 1 et nbVals et dans laquelle un même entier apparaît au plus 4 fois. Un paquet contient donc au plus 4*nbVals cartes.
On représente un paquet de cartes au moyen d'une liste chaînée d'entiers (i.e. LinkedList<Integer>) encapsulée dans la classe Deck qui contient déjà :
Dans la classe Deck, complétez les méthodes suivantes :
Testez votre code en exécutant Test1.java.
Déposez le fichier TD1.java :
Le mélange américain, ou riffle shuffle en anglais, est une technique couramment utilisée pour battre les cartes (c'est-à-dire permuter aléatoirement les éléments d'un paquet) :
|
Source : Wikipedia |
La coupe du paquet en deux sous-paquets se fait de manière aléatoire environ au milieu du tas de cartes. On va donc préférer un tirage aléatoire suivant la loi binomiale plutôt que la loi uniforme. La loi binomiale de paramètre n (dans cet exercice, n est la taille du paquet de cartes) est obtenue en comptant le nombre de tirages « pile » obtenus sur n lancers d'une pièce équilibrée (chanque lancer renvoie « pile ou face »). La méthode double Math.random(), qui renvoie une valeur choisie au hasard dans l'intervalle [0,1[, permet de simuler un tel lancer.
Dans la classe Deck, complétez la méthode int cut() pour qu'elle renvoie le nombre de cartes du « premier » paquet, tiré aléatoirement en suivant la loi binomiale.
Testez votre code en exécutant Test21a.java. Ce dernier calcule la déviation en « norme sup » entre la distribution théorique de la loi binomiale (de paramètre n) et celle que l'on obtient empiriquement à partir de m appels à la méthode cut (sur un jeu de n cartes). Pour n = 52 et m = 100000 la déviation dépasse rarement 0.0025.
Dans la classe Deck, complétez la méthode Deck split() pour qu'elle supprime et renvoie les c premières cartes du paquet, la valeur c étant donnée par un appel à la méthode cut.
Testez votre code en exécutant Test21b.java. Ce programme effectue (une centaine de fois) la coupe d'un jeu de 52 cartes et vérifie que les deux paquets obtenus redonnent le paquet complet.
Déposez le fichier TD1.java modifié ici :
Lors du riffle, la prochaine carte à tomber est la première de l'un des deux tas de cartes produits par la coupe. On décide que la probabilité qu'elle appartienne au premier est a/(a+b) où a et b désignent les nombres de cartes respectifs des deux tas, ce qui reflète assez bien ce qui se passe en pratique. Notez que les paramètres a et b doivent être mis à jour chaque fois qu'une carte tombe.
Dans la classe Deck, complétez la méthode void riffleWith(Deck d) pour qu'elle fusionne les cartes du paquet d avec celles du paquet courant. Au final, le paquet d est vide et le résultat de la fusion est dans le paquet courant.
Indication : créer un troisième paquet f, vide au départ, à partir duquel on appelle la méthode pick jusqu'à épuisement des paquets d et this. Au terme de cette étape, le champ f.cards contient le résultat du riffle. Il ne reste plus qu'à mettre le champ this.cards à jour.
Testez votre code en exécutant Test22.java, ce dernier effectue :
Déposez le fichier TD1.java modifié ici :
La distribution des cartes après un mélange américain n'est pas uniforme puisqu'une fois la coupe faite, l'ordre des cartes de chacun des deux tas est préservé par le riffle.
En revanche, en itérant le processus suffisamment de fois (de l'ordre de log n fois pour un jeu de n cartes) on obtient une distribution (presque) parfaitement aléatoire, comme l'ont démontré D. Bayer et P. Diaconis dans un article devenu célèbre.
En pratique, 7 mélanges américains suffisent à brasser convenablement un jeu de 52 cartes.
Dans la classe Deck, complétez la méthode void riffleShuffle(int m) pour qu'elle effectue m mélanges américains (split puis riffle) sur le jeu de cartes courant.
Testez votre code en exécutant le programme Test23.java. Ce dernier répète un million de fois l'expérience suivante :
Empiriquement, un paquet est déclaré suspect dès qu'il contient au moins :
Toujours empiriquement, sur un million de mélanges, on obtient rarement 5 paquets suspects. Si cela se produit, recommencez le test. Si les symptômes persistent, consultez votre code.
Déposez le fichier TD1.java modifié ici :
Note culturelle : La vitesse de convergence vers la distribution uniforme n'est cependant pas constante et on observe en particulier un seuil au-delà duquel la distribution devient très uniforme tandis qu'en deçà, elle reste très concentrée. Cette dernière propriété est la clef de voûte de nombreux tours de cartes. La troisième section de l'article de Diaconis, Graham et Kantor fournit de plus amples détails sur ce point. À noter que Diaconis fut lui-même un célèbre magicien avant de devenir probabiliste.
Les règles de la bataille sont simples : au début de la partie, les cartes sont distribuées entre les deux joueurs, qui les mettent en tas devant eux (sans les regarder). À chaque tour, chaque joueur prend la carte sur le dessus de son tas. Le joueur qui a la carte de plus haute valeur remporte les deux cartes et les place sous son tas. En cas d'égalité, on dit qu'il y a bataille et chaque joueur prend alors deux nouvelles cartes sur le dessus de son tas, la première en la posant sur le pli sans la regarder et la seconde pour la comparer à celle de l'adversaire. En cas de nouvelle bataille, on répète ce processus; sinon, le joueur gagnant emporte le pli. La partie est interrompue après n plis (n fixé à l'avance) ou dès qu'un des joueurs n'a plus de carte. C'est le joueur ayant le plus de cartes à la fin de la partie qui est le gagnant (il y a égalité si les deux joueurs ont le même nombre de cartes).
On modélise une partie de bataille par la classe Battle, qui contient :
Complétez le constructeur Battle(int nbVals) pour qu'il initialise une partie de bataille, autrement dit ce constructeur doit :
Testez votre code en exécutant Test31.java.
Déposez le fichier TD1.java ici :
Dans la classe Battle, complétez la méthode boolean isOver() pour qu'elle renvoie true si un des joueurs n'a plus de cartes et false sinon.
Dans la classe Battle, complétez la méthode boolean oneRound() pour qu'elle simule un pli :
La valeur renvoyée par la méthode indique si le pli s'est bien déroulé :
NB : la méthode peut renvoyer true même si l'un des joueurs n'a plus de cartes en main, par exemple si celui-ci a perdu le pli en retournant sa dernière carte. De même, il se peut que les deux joueurs soient à court de cartes (cela se produit lorsque les deux joueurs ont la même main au début du pli).
Testez votre code en exécutant Test32.java.
Déposez le fichier modifié TD1.java ici :
Dans la classe Battle, complétez la méthode int winner() pour qu'elle renvoie 1 (respectivement 2) lorsque le premier (respectivement le second) joueur a strictement plus de cartes en main que son adversaire, ou bien 0 si les deux joueurs ont le même nombre de cartes en main.
À l'aide de la méthode winner, complétez la méthode int game(int turns) pour qu'elle simule une partie en fixant à turns le nombre maximal de plis joués, et qui renvoie 1 ou 2 pour indiquer le vainqueur, ou bien 0 si les deux joueurs ont le même nombre de cartes en main à la fin de la partie (i.e. si les deux joueurs sont à court de cartes ou bien à la fin du dernier tour).
Testez votre code en exécutant Test33.java.
Déposez le fichier modifié TD1.java ici :
Jusqu'ici nous avons uniquement considéré des parties de bataille avec un nombre fini de coups fixé à l'avance. Nous allons lever cette limitation.
Pour cela, il faut ajouter au simulateur un mécanisme qui détecte les parties infinies. On désigne par Sk l'état de la partie au tour k, c'est-à-dire la paire des paquets détenus par les deux joueurs au tour k.
Une partie est infinie lorsque la suite des états S0, S1, … , Sk, … est infinie. Puisqu'il n'y a qu'un nombre fini d'états distincts possibles et que l'état Sk+1 est entièrement déterminé par l'état Sk, une telle suite est nécessairement périodique à partir d'un certain rang.
On va jouer simultanément deux parties b1 et b2. Au début des deux parties, les joueurs ont les mêmes cartes en main, mais la partie bis (i.e. b2) joue deux plis à chaque fois que la partie originale (i.e. b1) en joue un. En d'autres termes, on calcule d'une part la suite S0, S1, …, Si, … (partie originale) et d'autre part la suite S0, S2, …, S2i, … (partie bis). La partie est infinie si et seulement s'il existe un entier i tel que Si = S2i : c'est l'algorithme du lièvre et de la tortue, dû à Floyd.
On rappelle qu'on a fourni une méthode Battle copy() qui renvoie un clone d'un objet de la classe Battle. L'original et son clone occupent des emplacements mémoire disjoints, donc une modification de l'un n'affecte pas l'autre.
Pour tester si deux batailles sont identiques, on testera l'égalité des chaînes de caractères les représentant avec b1.toString().equals(b2.toString()).
Dans la classe Battle, complétez la méthode int game() pour qu'elle joue simultanément une partie tortue (qui sera jouée par le clone) et une partie lièvre i.e. à vitesse double (qui sera jouée par l'original, autrement dit par this) ayant le même état initial et qui renvoie :
Si la partie s'achève, this doit contenir son état final.
Testez votre code en exécutant Test41.java.
Déposez le fichier modifié TD1.java ici :
Dans la classe Battle, complétez la méthode static void stats(int nbVals, int nbGames) pour qu'elle simule nbGames parties de bataille, chacune à nbVals valeurs, à l'issue desquelles s'affiche le nombre de victoires de chaque joueur, de parties infinies, et de parties nulles.
Testez votre code en exécutant plusieurs fois Test42.java. Ce dernier lance la méthode stats avec un jeu de 44 cartes (11 valeurs), puis avec un jeu de 48 cartes (12 valeurs), et enfin avec un jeu de 52 cartes (13 valeurs). Que remarquez-vous ?
Avec notre implémentation actuelle, player1 pose toujours sa carte avant player2 sur le pli. On va modifier la classe Battle de sorte que player1 et player2 posent à tour de rôle leur carte en premier sur le pli. Pour cela, ajoutez un champ boolean turn à la classe Battle, initialisé à true dans les constructeurs, et modifiez la méthode boolean oneRound() de sorte que chaque fois que les deux joueurs doivent poser une carte sur le pli, player1 commence si turn est true, alors que player2 commence si turn est false, et turn change de valeur. Relancez Test42.java.
Déposez le fichier TD1.java modifié ici :