Projet : 2048

Contenu

Projet : 2048#

Ce sujet est composé de quatre sections. La première section décrit le jeu et ses règles. La seconde section décrit en détail les consignes de base du projet pour obtenir une note correcte (12/20). La troisième section décrit les extensions possibles pour viser le 20. L’une d’entre elles est de créer un joueur automatique de 2048 le plus performant possible. Enfin, la quatrième section (facultative) donne les consignes pour faire participer votre joueur automatique au tournoi qui nous essaierons d’organiser en fin de semestre et dont les résultats seront rendus publics!

Description et règles du 2048#

2048 est un jeu vidéo de type puzzle, variante du jeu de taquin. Il a été développé par Gabriele Cirulli en 2014 (19 ans à l’époque) et publié en ligne sous licence libre.

Les règles du jeu

Le jeu se joue sur un plateau \(4×4\) où chaque case est soit vide, soit contient une puissance de \(2\), inscrite sur une tuile. Le joueur peut déplacer les tuiles en les faisant glisser toutes ensemble dans une même direction (haut, bas, droite, gauche). Les tuiles ne peuvent dépasser les bords du plateau. Si deux tuiles de même valeur (\(2^k\)) sont adjacentes pendant le glissement, alors elles se combinent en une unique tuile étiquetée par la somme des valeurs (\(2^{k+1}\)). Chaque combinaison de tuiles rapporte au joueur un nombre de points équivalent à la valeur de la tuile après la combinaison. Après chaque déplacement, une nouvelle tuile apparaît aléatoirement sur un des emplacements vides. Cette nouvelle tuile a pour valeur soit \(2\), soit \(4\), avec probabilités respectives \(\frac{9}{10}\) et \(\frac{1}{10}\). Le jeu débute avec deux tuiles posées sur le plateau, tirées selon les probabilités mentionnées ci-dessus.

Le but du jeu est de créer une tuile portant le numéro 2048. Cependant, on pourra continuer à jouer après avoir atteint le but, en créant des tuiles avec des numéros plus grands et ainsi améliorer son score. Le jeu se termine lorsque toutes les tuiles sont occupées et que plus aucun mouvement ne permet de combiner de tuiles.

Consignes de base du projet#

Après le démineur et le yams, vous allez implanter \(2048\)! Vous devrez rendre un programme en C++ respectant les consignes décrites plus bas et permettant de jouer à 2048 et rédiger un rapport. Enfin, vous devrez présenter votre travail lors d’une soutenance orale incluant une démonstration. Pour les modalités pratiques, consultez la page sur les projets.

Niveau \(0\) : Pour obtenir jusqu’à 12/20#

L’objectif ici est de modéliser et d’implanter le jeu \(2048\) en mode console. Le joueur saisira chaque déplacement (haut, bas, gauche et droite) par l’intermédiaire de caractères de votre choix. (par exemple z, s, q et d ou encore h, b, g et d). Le plateau sera affiché en début de partie et après chaque tour de jeu. Voici un exemple d’exécution dans le terminal après quelques tours de jeu :

*************************
* 128 *  4  *     *     *
*************************
*  2  * 16  *  4  *  2  *
*************************
*     *     *     *     *
*************************
*  2  *     *     *     *
*************************

Entrer commande: h

*************************
* 128 *  4  *  4  *  2  *
*************************
*  4  * 16  *     *     *
*************************
*     *     *     *     *
*************************
*  2  *     *     *     *
*************************

Entrer commande: g

*************************
* 128 *  8  *  2  *     *
*************************
*  4  * 16  *     *     *
*************************
*     *     *  4  *     *
*************************
*  2  *     *     *     *
*************************
Entrer commande: ...

Le programme devra impérativement respecter la structure suivante. Un fichier 2048.cpp contiendra une fonction main qui lancera le jeu. On modélisera un plateau de jeu par un type Plateau (un alias du type vector<vector<int>>). Les règles et les actions du jeu seront implantées dans un fichier modele.cpp par les fonctions déclarées dans le fichier modele.hpp. Il est néanmoins possible d’ajouter des fonctions au fichier modele.hpp si besoin est, par exemple pour gérer le score de la partie.

Barème#

La note 12/20 pourra être obtenue si :

la structure du jeu respecte la structure imposée ci-dessus;
les fichiers de votre projet compilent;
le jeu est fonctionnel;
le jeu respecte les règles du \(2048\);
le score est mis à jour à chaque mouvement;
l’implantation respecte la structure donnée;
toutes les fonctions sont spécifiées, documentées et testées.

lors de l’affichage, les colonnes sont bien alignées, quelles que soient les valeurs de chaque tuile :

    Correct                        Pas correct
    *************************       *****************
    * 128 * 128 *     *     *       * 128 * 128 *   *   *
    *************************       *****************
    *  2  * 16  *  4  *  2  *       * 2 * 16 * 4 * 2 *
    *************************       *****************
    *     *     *     *     *       *   *   *   *   *
    *************************       *****************
    *  2  *     *     *     *       * 2 *   *   *   *
    *************************       *****************

le rapport est bien rédigé (orthographe, etc.) et comprend :
- une présentation du jeu,
- une documentation de votre application
la soutenance est soignée et inclut une brève démonstration de votre jeu.

Remarque : Le plagiat sera sanctionné.

Extensions pour améliorer sa note#

Niveau 1 : «gagner des points avec un minimum d’efforts»#

Ce niveau propose différentes améliorations (faciles) :

Comme sur le jeu original, rajoutez un peu de couleur à notre triste console. (\(\sim 1\)pt)
On aimerait jouer en utilisant directement les flèches (haut, bas, gauche et droite) du clavier, sans avoir à appuyer sur entrée à chaque fois. Étudiez différentes solutions envisageables et ajoutez cette fonctionnalité. (\(\sim 1\)pt)
Encore une fois pour des raisons de jouabilité, on aimerait que l’affichage d’un plateau se fasse à la place du plateau précédent, plutôt que en dessous. Autrement dit, on souhaiterait que l’écran se rafraîchisse. Étudiez différentes solutions et ajoutez la fonctionnalité. (\(\sim 1\)pt)
L’utilisation de variables globales dans un code est déconseillée car elle réduit la modularité et la flexibilité du programme. Calculez le score du jeu non pas avec une variable globale mais avec une structure de données qui associe le plateau Plateau et le score. (\(\sim 1\)pt)

Pour les trois premiers points, une solution envisageable est d’utiliser la bibliothèque ncurses. Un exemple minimal d’utilisation est fourni dans le fichier ncurses_min.cpp. Pour le compiler, il faut ajouter le paramètre de compilation -lncurses pour inclure la bibliothèque ncurses au moment de l’édition de lien. Sous myDocker, il faut en plus les options suivantes :

clang++ $CPPFLAGS $LDFLAGS ncurses_min.cpp -lncurses -o ncurses_min

Explication

CPPFLAGS et LDFLAGS sont les variables standard du shell pour définir les options à passer au compilateur et à l’éditeur de lien respectivement. L’environnement conda utilisé sur myDocker utilise ces variables pour pointer vers les endroits où sont installés les entêtes et binaires des bibliothèques.

Pour de la documentation sur ncurses, voir par exemple cette introduction ou ce «comment faire».

Attention

L’utilisation de certaines bibliothèques nécessite d’ajouter des paramètres de compilation. Si tel est le cas, le rapport devra expliciter la procédure de compilation.

Niveau 2 : «passer la barre des \(16\)»#

Ce niveau propose des améliorations plus difficiles, de l’ordre des bonnes pratiques de programmation :

Votre projet comportant un certain nombre de fichiers, la compilation manuelle – en appelant directement g++ – commence à être peu pratique. Une solution classique pour automatiser cela est d’utiliser un Makefile. Mettez cette solution en œuvre pour votre projet. (\(\sim 2\)pt)

Attention

Deux choix s’offrent à vous: créer un (petit) Makefile (simple) adapté à votre projet ou trouver un Makefile générique qui compile tout. Pour mériter les points de la question, l’important est de comprendre ce qui se passe (n’oublions pas la soutenance!).
Utilisez de plus un gestionnaire de version comme git pour gérer les sources de votre projet (voir par exemple ce tutoriel git). (\(\sim 1\)pt)

Niveau 3 : «Aller plus loin!»#

Chacune des extensions suivantes peut rapporter environ deux points (dans la limite de 20!). Vous pouvez aussi proposer d’autres extensions à votre enseignant.

Cette fois-ci, c’est au programme de décider comment déplacer les tuiles! Implantez une IA ou un joueur automatique de 2048 à votre manière. Même des règles simples peuvent permettre à votre IA de marquer des points. Les IA les plus élaborées seront davantage récompensées. Si vous choisissez de faire cette extension, vous pourrez aussi participer au tournoi que nous espérons organiser en fin de semestre. Pour cela, merci de lire attentivement et de respecter les consignes pour le tournois.
Implantez des variantes du jeu, comme l’une de celles décrites sur https://phenomist.wordpress.com/2048-variants/ ou, encore mieux, la vôtre. Et créer un menu en début de jeu pour choisir la variante.
La console est un peu triste, vive les graphiques! En utilisant la SFML, ou directement SDL ou GTK+, proposer une version de \(2048\) avec une interface graphique.
Vous en voulez encore? Une application android ou iOS pour votre portable, c’est possible?

La note maximale est sûrement de \(20\), mais des points se cachent encore dans la soutenance de votre projet. Ceux qui atteignent le dernier niveau assurent (presque) le \(20\), mais tout n’est pas perdu pour les autres. Soutenance bien préparée et travail soigné seront récompensés!

Pour participer au tournoi d’IA#

Attention

Nous ne savons pas encore si nous pourrons organiser le tournois cette année.

Cette section ne concerne que les groupes ayant décidé d’implanter un joueur automatique à leur jeu. Afin de faire concourir vos programmes sur un pied d’égalité, nous utiliserons notre implantation du jeu. Votre programme (le joueur automatique) se contentera de lire un fichier configuration.txt contenant la configuration du jeu à une itération donnée \(k\), et écrira dans un autre fichier mouvements.txt le mouvement à effectuer pour l’itération \(k+1\).

Notre programme se chargera de lire le mouvement choisi par votre programme et de mettre à jour le fichier configuration.txt contenant la nouvelle position de jeu.

Voici les consignes à respecter :

Le programme principal de votre joueur automatique devra s’appeler 2048_IA.cpp. Sa compilation devra être documentée et automatisée dans un Makefile, de sorte que la commande suivante:
```
make 2048_IA
```
génère un binaire s’appelant 2048_IA.

La compilation de votre programme 2048_IA.cpp ne doit pas faire intervenir de bibliothèque externe qu’il faudrait installer (pas de librairies graphiques par exemple). Votre commande de compilation doit fonctionner dans le terminal sur myDocker.
Le programme 2048_IA est en charge d’une seule itération du joueur: en fonction d’une configuration du plateau de jeu, il doit indiquer le coup à jouer. Plus précisément: au lancement, le programme 2048_IA lit la configuration du plateau sur son entrée standard. Cette configuration se présente sous la forme suivante :
```
    0 0
    0,0,0,0;
    2,0,0,0;
    0,2,0,0;
    0,0,0,0;
```
La première ligne contient le numéro de l’itération k et le nombre de points n. Les autres lignes représentent le plateau de jeu. Ici c’est l’état initial, donc k et n valent 0 (ligne 1) et seulement deux tuiles sont placées. Voici un exemple de configuration où, après 6 mouvements le joueur automatique a marqué 20 points :
```
    6 20
    0,0,0,0;
    0,2,0,0;
    2,0,0,0;
    8,4,0,0;
```
Votre programme devra alors afficher le mouvement à effectuer sous la forme d’un trigramme (trois lettres) faisant office de pseudonyme pour le joueur automatique et d’une lettre donnant le mouvement (H, B, G et D pour Haut, Bas, Gauche et Droite). Par exemple, pour le pseudonyme “BOB” et un mouvement vers la droite :
```
    BOB D
```
Si un mouvement est invalide (non reconnu ou bien ne changeant pas l’état du jeu), alors le numéro de l’itération k est incrémenté sans changer le plateau de jeu ou le score.
Dans le dossier du projet, vous trouverez ultérieurement une feuille tests_tournois.md. Suivez les instructions pour exécuter un exemple de simulation et testez si les entrées sorties de votre programme sont conformes aux contraintes du tournoi listées ci-dessus.

Toutes les améliorations de votre IA sont bonnes à prendre. On peut commencer par une IA qui essaie de ne pas perdre, qui marque les points quand c’est possible ou bien qui anticipe plusieurs actions pour combiner un maximum de tuiles! Arriver dans le haut du podium en fin de semestre vous garantira quelques points bien mérités. Bonne chance!