| |
| pg108:tp5 [2022/09/07 09:43] – créée 78.229.230.2 | pg108:tp5 [2022/09/07 09:44] (Version actuelle) – 78.229.230.2 |
|---|
| ===== Problème : Puissance 4 ===== | ===== Nombres et leur représentation ===== |
| |
| |
| L'objectif de ce projet, est de (re)développer le jeu "Puissance 4" en C. Ce jeu se compose d'une grille de 7 colonnes par 6 rangées. Chacun leur tour, les joueurs glissent des jetons (jaune ou rouge dans la version originale) dans une des colonnes ou il reste de la place (le jeton occupe alors la position la plus basse). Le gagnant est celui qui arrive à aligner 4 jetons de sa couleur. | ==== Table ASCii ==== |
| |
| | * Écrivez un programme qui affiche la table ASCii pour les codes caractères de 32 à 127. Pour chaque code de caractère, il faudra afficher successivement sur la même ligne : |
| | - La valeur décimale |
| | - la valeur hexadécimale |
| | - le caractère |
| | * Modifiez votre programme pour que, si un argument est fourni en ligne de commande, il soit interprété comme le code d'un caractère à afficher au format décimal. Le programme n'affiche alors que la ligne spécifique à ce code de caractère. |
| | * Modifiez votre programme pour que, si deux arguments sont fournis en ligne de commande, ils soient interprétés comme les valeurs minimales et maximales de l'intervale des codes ASCii à afficher. |
| |
| ==== Environnement de départ ==== | Pour améliorer la lisibilité, il est possible de passer des paramètres de formatage à la fonction //printf//. |
| | - //%4d// signifie qu'il faut afficher une valeur en base décimale en utilisant au moins 4 caractères (Les caractères inutiles sont des espaces) |
| | - //%5X// fonctionne de la même manière pour la base hexadécimale (5 caractères minimum dans ce cas-ci). |
| | - //%06d// signifie qu'il faut afficher sur un nombre minimal de 6 caractères, mais en remplaçant les espaces par des //0// |
| | Mettez votre programme à jour pour que les colonnes //décimal//, //hexadécimal// et //caractère// soit bien alignées. |
| |
| Nous utiliserons des variables globales pour simplifier la structure logicielle. Ces variables seront : | ---- |
| * //NomJoueur1// : une chaîne de caractère dont la taille maximale est 30 | |
| * //NomJoueur2// : une chaîne de caractère dont la taille maximale est 30 | |
| * //JoueurEnCours// : un entier de type char qui indique le numéro du joueur dont c'est le tour. | |
| * //GrilleDeJeu// : un tableau de 42 cases (7x6) de type char. Chaque case //i// correspond à un emplacement (c,r) de la grille de jeu tel que : | |
| * 0 =< c =< 6 | |
| * 0 =< r =< 5 | |
| * i = r*7+c. | |
| |
| Pour chaque case de //GrilleDeJeu//, la valeur 0 signifie qu'elle est vide, la valeur 1 signifie qu'elle contient un jeton du joueur 1, la valeur 2 signifie qu'elle contient un jeton du joueur 2. Les autres valeurs sont interdites. | ==== Affichage de flottants ==== |
| |
| ==== Initialisation ==== | Écrivez un programme qui affiche un tableau de valeurs réparties sur 6 colonnes de 10 lignes. Ces valeurs dépendent de trois arguments passés en ligne de commande : respectivement //start//, //h_mul// et //v_inc//. |
| | - //start// représente la valeur en haut à gauche |
| | - Chaque élément de la première ligne est égal à son voisin de gauche multiplié par //h_mul// |
| | - Chaque élément de la première colonne est égal à son voisin du dessus additionné de //v_inv// |
| | - Chaque élément du reste du tableau est égal au produit du premier élément de sa colonne par le premier élément de sa ligne. |
| | - La structure du tableau doit être apparente (valeurs de lignes et de colonnes alignées). |
| |
| Ecrivez la fonction //init// qui demande le nom de chacun des deux joueurs, qui stocke ces noms dans les variables NomJoueur1 et NomJoueur2, et qui initialise GrilleDeJeu pour qu'elle ne contienne que des 0. | |
| |
| ==== Affichage ==== | ---- |
| |
| Écrivez la fonction //display// qui affiche la grille de jeu, puis le nom du joueur qui doit placer son jeton. (Les jetons du joueur 1 seront symbolisés par des 'X', et les jetons du joueur 2 seront symbolisés par des 'O'. Les cases vides seront symbolisées par des '.') | ==== [facultatif] Conversion binaire/entier ==== |
| |
| A ce stade, vous devriez être en mesure de tester votre programme (donc faites-le) | Écrivez un programme qui récupère une valeur binaire en argument et qui affiche dans le terminal la valeur décimale équivalente. |
| | |
| A fin de debuggage, Il peut être utile de prévoir l'affichage d'un quatrième symbole dans la grille permettant de déterminer si une valeur autre que 0, 1 ou 2 y a été stockée. | |
| | |
| == astuces UNIX (avancées) == | |
| | |
| Les terminaux UNIX sont compatibles avec le standard //VT100//. Ce standard définit des séquences (dites d'//échappement//) permettant une mise en forme basique du texte. Par exemple, il est possible de changer la couleur de texte, ou de modifier la position du curseur (entre autres). Ces commandes commencent toutes par le caractère non affichable numéro 27 (27=0x1B, donc noté \x1B dans une chaîne de caractères). Les commandes suivantes pourraient vous être utiles : | |
| * "\x1B[2J" : effacer le terminal | |
| * "\x1B[H" : placer le curseur en haut à gauche du terminal | |
| * "\x1B[1m" : afficher le texte en gras | |
| * "\x1B[93m" : afficher le texte en jaune | |
| * "\x1B[93m" : afficher le texte en rouge | |
| | |
| Les possibilités sont nombreuses, pour les connaître en détail, cherchez les commandes VT100 dans votre moteur de recherche préféré (ça donnera aussi de bons résultats avec un moteur de recherche que vous n'aimez pas...). | |
| ==== Phase de jeu ==== | |
| | |
| Écrivez la fonction //colonne_de_joueur// qui demande une colonne dans laquelle placer un jeton. Le joueur doit répondre un numéro de colonne entre 1 et 7 (inclus). Si le joueur a répondu une valeur de colonne incorrecte, la fonction lui demande un autre numéro de colonne (jusqu'à obtenir un numéro de colonne correct. | |
| | |
| La fonction //colonne_de_joueur// revoie un valeur compatible C, c'est à dire que le numéro de colonne est entre 0 et 6. Vous pouvez temporairement afficher cette valeur pour faciliter le debuggage. | |
| | |
| __Après avoir testé__ la fonction //colonne_de_joueur//, modifiez-la pour qu'elle place le jeton dans la grille de jeu. Vous pouvez tester cette fonction en l'appelant dans une boucle infinie après l'initialisation (la fonction //affichage// doit également être dans la boucle infinie). | |
| | |
| __Après avoir testé__ la modification précédente, modifiez-la pour qu'elle vérifie également si la colonne demandée n'est pas pleine. Si c'est le cas, la fonction considère que la colonne n'est pas valide. | |
| | |
| N'oubliez pas de **TESTER** vos fonctions aussi souvent que possible !!! | |
| | |
| ==== finalisation d'une version basique ==== | |
| | |
| A ce stade, il ne manque pas grand chose pour obtenir une version jouable à deux. Mais le programme est incapable de repérer la fin du jeu... Finalisez le programme pour qu'il soit jouable. | |
| | |
| Pour repérer la fin du jeu, vous le ferez de façon manuelle en interrompant l’exécution avec ctrl-C. | |
| | |
| ==== Détection d'une grille pleine ==== | |
| | |
| A partir de maintenant, nous allons nous intéresser à détecter la fin du jeu. Pour cela, nous allons utiliser la variable JoueurEnCours. Si elle vaut 11, c'est que le joueur 1 a gagné, si elle vaut 12, c'est le joueur 2 qui a gagné, si elle vaut 10, c'est une égalité, la grille est pleine sans qu'aucun des joueurs n'aie réussi à aligner 4 jetons. | |
| | |
| Ecrivez la fonction //detecte_plein// qui vérifie si la grille est pleine. Si c'est le cas, la fonction renvoie 1 et modifie //JoueurEnCours//, sinon, elle renvoie 0. | |
| | |
| Modifiez votre programme pour qu'il tienne compte de //JoueurEnCours// pour la fin de la boucle principale. Une fois sorti de la boucle, le programme doit bien entendu afficher le nom du vainqueur, ou préciser qu'il y a égalité. | |
| | |
| ==== Détection d'un vainqueur ==== | |
| | |
| Pour vérifier si quelqu'un a gagné, il n'y a pas le choix, il faut vérifier toutes les possibilités. Pour cela, nous allons créer la fonction //TestVainqueur//. | |
| Cette fonction reçoit la grille de jeu comme argument et effectuera ses tests sur la grille de jeu. Si la fonction trouve un vainqueur, elle renvoie le numéro du vainqueur, sinon, elle renvoie 0. | |
| | |
| == lignes horizontales d'abord == | |
| | |
| Créez la fonction //TestLigne// qui teste si, quelque part dans la grille, il y a 4 jetons en ligne horizontale. Cette fonction est destinée à être une sous-fontion de //TestVainqueur//. Le test doit s'effectuer sur une grille reçue en paramètre, pas directement sur //GrilleDeJeu//. | |
| | |
| Testez si ce test fonctionne. | |
| | |
| == lignes verticales ensuite == | |
| | |
| Créez la fonction //TestColonne// qui teste si, quelque part dans la grille, il y a 4 jetons en ligne verticale. Cette fonction est le pendant de //TestLigne// et fonctionne de la même façon. | |
| | |
| == UNIX, pour gagner en productivité == | |
| | |
| Testez (Encore). Vous remarquez que les tests deviennent un peu pénibles, car il devient assez long de produire la situation à valider. Pour vous en sortir, il y a la possibilité d'utiliser une redirection UNIX. Écrivez à l'avance toutes les réponses dans un fichier texte (une réponse par ligne). Vous pouvez alors utiliser la redirection au lieu de taper directement les réponses grâce à la syntaxe suivante : | |
| | |
| ./puissance4 < fichier_de_test | |
| | |
| == diagonales (pente positive) == | |
| | |
| Ce sera la fonction //TestDiagPos//. Pour le test des diagonales de pente positive, l'algorithme est proche de celui de //TestColonne//, mais au lieu de tester les séries (x,y) = (k,i) (ou k est la colonne testée, de 0 à 6), on teste les séries (x,y) = (k+i, i) ou k identifie la diagonale testée (de -2 à 3). Il faut également tenir compte du fait que cette façon de parcourir les éléments d'une diagonale àmène à des coordonnées de case qui n'existe pas, et qu'il faudra donc repérer pour les ignorer. | |
| | |
| **TESTEZ** cette fonction | |
| | |
| == diagonales (pente négative) == | |
| Ce sera la fonction //TestDiagNeg//, elle s'intéressera aux coordonnées de la forme (x,y)=(k+i, 5-i) pour k de -2 à 3. | |
| | |
| Une fois cette fonction testée, le jeu est jouable à deux joueurs. | |
| ==== jeu contre le programme ==== | |
| | |
| Pour jouer contre l'ordinateur, nous considérerons qu'il suffit de ne pas donner de nom pour le deuxième joueur. | |
| Il faut ensuite déterminer quelle est la colonne que doit choisir //l'ordinateur// (en fait votre programme) à son tour de jeu. | |
| | |
| == La méthode aléatoire == | |
| | |
| Pour mettre en place le jeu contre le programme, nous utiliserons une méthode de choix aléatoire. A défaut d'être intelligente, cette méthode est rapide et permettra de se concentrer sur les modifications du programme déjà existant. | |
| | |
| | |
| * Écrivez une fonction //CalculeColonneAleatoire// qui renvoie un entier. Cette fonction tire une valeur aléatoire à l'aide de la fonction //rand()// disponible dans stdlib.h (consultez //man 3 rand// pour plus d'informations). Cette valeur sera ramenée entre 0 et 6 grâce à la fonction modulo (%). Tant que la colonne correspondant à cette valeur est pleine dans GrilleDeJeu, la valeur sera augmentée de 3 puis ramenée entre 0 et 6 par un modulo, sinon, la valeur est renvoyée. | |
| * Ajoutez une variable globale //Joueur2Virtuel// de type char. Si cette valeur est différente de 0, cela signifie que le jeu se fait contre l'ordinateur. | |
| * modifiez la fonction //init// pour qu'elle détermine la valeur de //Joueur2Virtuel// en fonction de //NomJoueur2//. | |
| * modifiez la fonction //colonne_de_joueur// pour que, si on joue contre le programme et que c'est au programme de jouer, le numéro de colonne ne soit pas demandé à l'utilisateur, mais fourni par la fonction //CalculeColonneAleatoire//. | |
| | |
| Testez vos modifications (vous ne devriez pas avoir de problème pour gagner contre le programme) | |
| | |
| == La méthode min-max == | |
| | |
| Une méthode plus pertinente (à défaut d'être efficace) consiste à tester toutes les possibilités. Cette méthode (communément appelée min-max) simule donc ce qu'il se produit pour un jeton dans chaque colonne. Pour anticiper la suite du jeu, toutes les ripostes du joueur sont également testées, et ainsi de suite. La succession de coups est testée grâce à une fonction récursive. Dans chaque cas, la fonction retourne un résultat indiquant si la suite de coups à mené à une victoire, une défaite, ou ni l'un ni l'autre. | |
| | |
| L'explosion combinatoire des cas à envisager rend inenvisageable une exploration exhaustive des évolutions possibles. On s'arrête alors à quelques coups (7 dans notre cas). Cette technique est essentiellement défensive et considère que le joueur humain est de très bon niveau, elle amène donc un comportement qui cherche à ne pas perdre plutôt qu'à élaborer une stratégie de victoire. | |
| | |
| L'écriture de cette fonction dépasse très largement le niveau d'exigence de cet exercice. Cette partie est donc fournie dans les fichiers {{ AI_player.c}} et {{ AI_player.h}}. //AI_player.c// contient la fonction //CalculColonneAI// qui a besoin d'accéder à //TestVainqueur// et à //GrilleDeJeu//. L'objectif de cet exercice est donc d'effectuer une compilation multi-fichiers avec le fichier //AI_player.c//. Écrivez votre fichier d'entête (.h) et modifiez votre programme pour que la compilation fonctionne avec deux fichiers C séparés. | |
| | |
| //AI_player.c// est écrit de telle sorte que votre fichier d'en-tête se nomme //Puissance4.h//. Modifiez cette ligne au besoin. | |
| | |
| ==== jeu adaptatif ==== | |
| | |
| La technique Min-Max donne déjà de très bons résultats, cependant, elle reste limitée face à un joueur expérimenté. Pour résoudre ce dilemme, il est possible de rendre l'algorithme adaptatif. La technique consiste à modifier le tableau //priority// dans AI_player.c pour qu'elle s'adapte au joueur que le programme affronte. Ce tableau permet de pondérer les choix à effectuer lorsque la recherche Min-Max ne parvient pas à identifier un cas unique. Plus la valeur d'un élément est élevée, plus la case correspondante sera favorisée. | |
| | |
| La technique est simple, mais se montre tout de même efficace : En fin de partie, les cases correspondant à une pièce du vainqueur voient leur valeur augmentée, celles correspondant à une pièce du perdant sont diminuées. | |
| | |
| Pour implanter cette technique, il faut bien sûr que //priority// soit stocké dans un fichier pour être modifié, et non plus en dur dans le programme. | |
| | |
| - modifiez vos fichiers pour que //priority// soit maintenant un tableau de //float// déclaré dans votre programme (seul AI_player.h n'a pas besoin d'être modifié). | |
| - modifiez votre partie du programme pour que //priority// soit chargé depuis le fichier {{priority.txt}} (que vous aurez téléchargé) au début du programme. | |
| - Ajoutez les fonctions de mise à jour de //priority// en fin de partie | |
| * en cas de défaite, la valeur est réduite selon la formule suivante : v = v*0.9 | |
| * en cas de victoire, la valeur est augmentée selon la formule suivante : v = 2 + v*0.9 (cette valeur est bien augmentée et converge vers 20 si v est inférieur à 20) | |
| - enregistrez //priority// dans le fichier //priority.txt// après mise à jour. Vous pouvez faire cet modification/enregistrement, même sur une partie entre deux joueur humains, le programme gagnera ainsi de l'expérience même lorsqu'il joue pas. | |
| | |
| ==== enjoy ==== | |
