INF 411 - TD 1

Bataille


Votre opinion sur le cours de ce lundi

 Login :  Mot de passe :

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 d'une répartition initiale, si la partie se termine et quel est le gagnant dans ce cas. En particulier le programme devra être capable de simuler une partie.

Préambule

Création d'un workspace dédié aux travaux dirigés du cours INF411

  1. Créez un nouveau répertoire INF411 (par exemple avec la commande mkdir ~/INF411 dans un terminal).
  2. Lancez Eclipse et choisissez le répertoire INF411 dans la fenêtre Workspace launcher qui devrait apparaître au lancement. Sinon, utilisez le menu File -> Switch Workspace.

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

Allez dans le menu File -> New -> Java Project, nommez le projet TD1 puis cliquez sur Finish.

Pour plus d'informations concernant Eclipse, consultez ce tutoriel.

Consignes de programmation

Nommez les classes, variables et méthodes exactement comme le demande l'énoncé.

Indentez votre code (en utilisant Ctrl+Shift+F) et commentez-le (en utilisant // ou /* ... */).

Pour des questions relatives à la syntaxe de Java, consultez ce mémento.

Activer assert dans votre machine virtuelle Java

Cliquez sur Window -> Preferences puis sur l'onglet Java -> Installed JREs de la fenêtre qui apparaît. Cliquez sur la machine virtuelle que vous utilisez (il ne devrait y en avoir qu'une seule installée). Cliquez sur le bouton Edit. Dans la barre Default VM argument écrivez -ea (pour enable assert). Cliquez sur Finish.

Documentation

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 locale (intranet) est ici : Java 1.8.

Récupération des sources

Téléchargez le fichier src.zip, décompressez-le, et placez les fichiers dans le répertoire src de votre projet TD1.


Avertissement : tout votre code doit être fait 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.)

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 contrepartie, 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 sur le 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 « pile ou face » d'une pièce équilibrée. 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) une 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.

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 (une centaine de fois) une coupe suivie d'un riffle des deux paquets obtenus, en vérifiant à chaque fois que le résultat de la manipulation contient bien chacun des deux paquets, dans l'ordre.

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 Test23.java. Ce dernier répète un million de fois l'expérience suivante :

  1. il crée un nouveau jeu de 52 cartes,
  2. il mélange ce jeu via la méthode riffleShuffle(7),
  3. il vérifie 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 extrêmement 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 :

Dans la classe Battle, complétez le constructeur Battle(int nbVals) pour qu'il construise une nouvelle partie de bataille, en construisant un nouveau paquet de 4*nbVals cartes (avec le constructeur Deck(int nbVals)), en le mélangeant (avec la méthode riffleShuffle(7)) et en le distribuant aux deux joueurs.

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,
  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. Nous allons maintenant manipuler aussi des parties de bataille qui durent indéfiniment.

On souhaite donc 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