TD 1

Bataille


Votre opinion sur le cours de ce lundi

 Login :  Mot de passe :

Préambule

Création d'un espace de travail pour les travaux dirigés du cours

Créez un nouveau répertoire CSC_41011, depuis le navigateur de fichiers de votre système d'exploitation, ou avec la commande mkdir ~/CSC_41011 dans un terminal. Ce répertoire sera votre espace de travail, il contiendra tous les TDs du cours.

Création d'un projet dédié au TD1

  1. Lancez Visual Studio Code (VS Code par la suite), par exemple en exécutant la commande code dans le terminal, ou en cliquant sur un raccourci; la touche [Alt] fait apparaître / disparaître la barre du menu horizontale.
  2. Dans VS Code tapez la combinaison de touches [Ctrl]+[Shift]+[P] (ou [Alt]+[V] puis cliquez sur command Palette) puis tapez «java: create» dans la barre qui apparaît et sélectionnez Create Java Project et l'option No build tools.
  3. Une fenêtre s'ouvre et vous invite à choisir votre espace de travail, c'est-à-dire le répertoire CSC_41011 que vous avez créé en suivant les instructions du paragraphe précédent.
  4. Indiquez le nom de votre projet (TD1) dans la barre de texte.

Récupération des sources

Cliquez avec le bouton gauche sur le lien src.zip, puis sur «Extraire», enfin sélectionnez le répertoire de votre projet (c'est-à-dire le répertoire TD1 qui se trouve dans le répertoire CSC_41011) lorsque l'outil de décompression vous le demandera et cliquez à nouveau sur «Extraire».

Activer assert dans votre machine virtuelle Java

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).

Consignes de programmation

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.

Documentation

Pour obtenir la description d'une classe Java standard, utiliez un moteur de 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.


Avertissement : tout votre code doit être écrit dans le fichier TD1.java

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.)

Le jeu de Bataille

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 : le but de ce TD est d'écrire un programme qui mélange les cartes, simule le déroulement de la partie, et indique le gagnant (le «match nul» est possible).

1. Paquets de cartes

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 nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

2. Le mélange américain

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) :
  1. On coupe arbitrairement le jeu de cartes en deux tas (que l'on coince entre le pouce et l'index de chaque main),
  2. puis on laisse tomber les cartes une à une sur la table de manière à les entrelacer (c'est le riffle).
La manipulation est illustrée par l'image de droite (cliquez dessus pour accéder à un tutoriel vidéo) et expliquée en détail dans cette page Wikipedia. On va implémenter dans la classe Deck une méthode qui effectue ce mélange.
Un mélange américain
Source : Wikipedia

2.1. La coupe

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 :

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

2.2. Le Riffle

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)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 :

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

2.3. Combiner le tout

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 :

  1. créer un nouveau jeu de 52 cartes,
  2. mélanger ce jeu via la méthode riffleShuffle(7),
  3. vérifier si le paquet obtenu est suspect.

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 :

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

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.

3. Simulation d'une partie de bataille

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).

3.1. Début de partie

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 :

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

3.2. Déroulement d'un pli

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 :

  1. chaque joueur tire une carte et la met dans le pli (d'abord le joueur player1, ensuite le joueur player2),
  2. le joueur ayant retourné la carte la plus forte remporte le pli, qu'il ajoute à la fin de son paquet sans changer l'ordre des cartes de ce pli,
  3. en cas d'égalité il y a « bataille » :

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 :

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

3.3. Déroulement de la partie.

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 :

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

4. Parties infinies (optionnel mais passionnant)

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.

4.1. Implémentation

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 :

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

4.2. Statistiques

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 :

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer