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

Aller 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 (Ctrl+Shift+F) et commentez-le.

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

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.

1. Paquets de cartes

Un jeu de cartes standard contient 52 cartes, chacune étant caractérisée par

Ici 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, donc le paquet contient 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 une classe Deck qui contient déjà :

Téléchargez la classe Deck puis ajoutez les méthodes suivantes :

Testez votre code en exécutant le programme Test1.java.

Déposez le fichier Deck.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 par 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

Ajoutez à la classe Deck une méthode int cut() qui renvoie le nombre de cartes du "premier" paquet, ce dernier étant choisi aléatoirement. En pratique, la coupe se fait environ au milieu du tas de cartes, c'est pourquoi on préfère 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 "face" obtenus sur n lancers 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.

Testez votre code en exécutant le programme 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.

Ajoutez à la classe Deck une méthode Deck split(), qui supprime et renvoie les c premières cartes du deck, la valeur c étant donnée par un appel à la méthode cut.

Testez votre code en exécutant le programme Test21b.java. Ce programme effectue 100 coupes successives d'un jeu de 52 cartes puis vérifie que la concaténation des deux paquets de la coupe redonne un jeu complet (aucune carte n'a été supprimée ou dupliquée).

Déposez le fichier Deck.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.

Ajoutez à la classe Deck une méthode void riffleWith(Deck d) qui fusionne les cartes du paquet d avec celles du deck appelant (i.e. this). Au final, le paquet d est vide et le résultat de la fusion est dans le paquet this.

Testez votre code en exécutant le programme Test22.java. Ce dernier effectue une centaine de coupes suivies d'un riffle avec les deux paquets obtenus en vérifiant à chaque fois que le résultat de la manipulation contient bien les deux paquets dans l'ordre.

Déposez le fichier Deck.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.

Ajoutez une méthode void riffleShuffle(int m) à la classe Deck, qui 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. Attention : la cause du problème peut être une implémentation non probabiliste de la méthode riffleWith. En effet, les tests de la question 2.2 vérifient uniquement qu'aucune carte n'a disparu ni n'est apparue.

Déposez le fichier Deck.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 fournit une classe Battle modélisant une partie de bataille. Elle contient

Téléchargez la classe Battle puis ajoutez un constructeur Battle(int nbVals) qui établit un état initial en construisant un nouveau jeu de cartes, en le mélangeant et en le distribuant aux deux joueurs.

Testez votre code en exécutant le programme Test31.java.

Déposez le fichier Battle.java ici :

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

3.2. Déroulement d'un pli

Ajoutez à la classe Battle une méthode boolean isOver() qui renvoie true si un des joueurs n'a plus de cartes et false sinon.

Ajoutez ensuite une méthode boolean oneRound() qui simule un pli :
  1. chaque joueur tire une carte et la met dans le pli,
  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 répond à la question « la partie peut-elle continuer ? ».
Si durant le pli, un joueur doit tirer une carte alors qu'il n'en a plus en main, la méthode renvoie immédiatement false (i.e. la partie s'arrête), sinon elle renvoie true (i.e. la partie continue).

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 le programme Test32.java.

Déposez le fichier modifié Battle.java ici :

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

3.3. Déroulement de la partie.

Écrire une méthode int winner() qui 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, écrire une méthode int game(int turns) qui 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 le programme Test33.java.

Déposez le fichier modifié Battle.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 ignoré le fait qu'une partie de bataille puisse durer indéfiniment, autrement dit que le simulateur puisse boucler.

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 si 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 donne une méthode Battle copy() qui fournit un clone d'un Battle. L'original et son clone occupent des emplacements mémoire disjoints, donc une modification de l'un n'affecte pas l'autre.

On fournit aussi une méthode boolean equals(Battle b) qui renvoie true si et seulement si la partie courante (i.e. this) est identique à b.

Définir une méthode public int game() qui 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 être son état final.

Testez votre code en exécutant le programme Test41.java.

Déposez le fichier modifié Battle.java ici :

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

4.2. Statistiques

Ajoutez à la classe Battle une méthode static void stats(int nbVals, int nbGames) qui 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 le programme Test42.java. Ce dernier lance la méthode stats avec un jeu de 8 cartes (2 valeurs), puis avec un jeu de 12 cartes (3 valeurs), et enfin avec un jeu de 52 cartes (13 valeurs). Que remarquez-vous ?

Déposez le fichier Battle.java modifié ici :

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


Nous vous proposons une solution. Bien sûr, ce n'est pas la seule!