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 unMakefile
. 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 unMakefile
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 directementSDL
ouGTK+
, 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 programme2048_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 pointsn
. Les autres lignes représentent le plateau de jeu. Ici c’est l’état initial, donck
etn
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!