Voir le rapport
Contents
1. mettre jour le jeu avec cette position simulation de jeu e calculer la valeur du nouveau jeu appel r cursif MinMax e d faire le jeu undo calculer le max ou min sur toutes les valeurs renvoy es Vous devrez donc tre m me de stocker un ensemble de positions De plus vous devez avoir un m canisme d undo Pour cela la liste cha n e est votre amie En effet une partie tout moment peut se d crire comme une suite de coups donc de positions jou es Imaginons que vous ayez d fini une liste cha n e de type LIFO Last In First Out voir dernier TD de C Jouer un coup revient faire un push de la position indiqu e dans la liste des coups D faire undo un coup revient faire un pop dans la liste des coups De plus cette structure peut galement vous permettre de stocker la liste des coups accessibles partir de la position courante LICENCE INFORMATIQUE P Module Environnement de Programmation EPDP 1 Page 12 sur 23 Ea OKS X Xmorpion 3 3 Travail r aliser Vous commencerez donc par d finir un module LIFOList permettant de g rer une liste chain e de positions Un type Position pourra tre d fini afin de stocker un num ro de ligne et de colonne Les fonctions crire pour cette liste seront les classiques newList deleteList popList pushList Vous crirez ensuite le module Game qui d finit la structure Game Cette structure contiendra tout ce qui est n cessaire pour d crir2. Bon jeu 1 Pour compiler le programme sous Atlas ou Linux cf la fin page LICENCE INFORMATIQUE 7 Module Environnement de Programmation EPDP 1 Page 17 sur 23 e ee X Xmorpion 2 Descriptif des fonctions Partie Algorithmique seen Morpion c et Morpion h Morpion c est un programme qui prend en param tres les Z informations sur le jeu e nombre de lignes nlines e nombre de colonnes ncolumns e nombre de cases aligner nalign e premier joueur player Ces param tres sont initialis s dans la ligne de commande par la commande suivante Syntaxe morpion lt lignes gt lt colonnes gt lt nombre de pions aligner gt lt Player gt Une fois les param tres rentr s le programme cr e une structure Game qui permet de jouer contre l ordinateur On entre le coup de l humain gr ce son num ro de ligne et de colonne Ce programme sert principalement tester les fonctions algorithmiques Il n est pas indispensable au bon d roulement du jeu mais conseill Les fonctions implant es dans ce programme sont void message erreur affiche un message d erreur en cas de case non jouable e int message gagne affiche un message en cas de victoire int avert gain teste si l alignement r aliser pour la victoire est plus important que la dimension du tableau int saisi position int a int b Permet de g rer l interfa age de r cup ration de coup de l homme int Ordi int
3. l exception de la case 0 0 Le probl me vient apparemment d une erreur d indice dans la fonction iswin mais on n a pas pu la trouver ce jour Gestion des v nements La touche q permet toujours de quitter le jeu et l ordre d apparition des crans cran de bienvenue plateau de jeu r sultats avec d sactivation du clavier cran de fin et sortie de l application sont maintenant g r s sans probl me Les fonctions de PIA Celles ci fonctionnent en mode texte avec morpion c Cependant le module Game c actuel est un m lange des deux Game c pr c dants ce qui ne lui assure plus de compatibilit avec morpion c Jouabilit Xmorpion inclut certaines fonctions de la partie algorithmique isWin et isFull mais pas son IA On ne peut donc pas jouer contre l ordi ce param tre est n anmoins accept par la ligne de commande Cependant une partie deux est tout fait possible et la victoire ou le match nul sera d tect g r et affich LICENCE INFORMATIQUE P Module Environnement de Programmation EPDP 1 Page 16 sur 23 ee X Xmorpion Explications du programme 1 Mode d emploi du jeu D marrer le jeu Si le programme est compil lancez dans le terminal la commande Xmorpion lt lignes gt lt colonnes gt lt nalign gt lt config gt lt Player gt Xmorpion prend les param tres suivants lt lignes gt nombre de lignes lt colonnes gt nombre de colonnes lt nalign
4. e et permis aussi de re voir en d tail certaines notions du langage C e 7 Anorpion LICENCE INFORMATIQUE P Module Environnement de Programmation EPDP 1 Page 15 sur 23 e ee X Xmorpion 2 R partition des t ches La r partition des taches fut assez ais e en fonction des go ts de chacun Partie Graphique e Dimitri Dupuis Latour XGame Xmorpion Rapport PDF Myriam No l Menu c et h pourinitialiser le jeu Partie Algorithmique e Christophe Desaint LIFOList Arnaud Grausem MinMax is Full isWin e Pierre Emmanuel Pign de Known issues Faisons le point sur ce qui fonctionne et ne fonctionne pas encore Passage des arguments Au lancement du programme on peut mettre un nombre incorrect d arguments des arguments avec des lettres au lieu d entiers des arguments contradictoires on joue seul mais on veut tre le joueur 2 on veut aligner plus de ligne qu il n y a de cases et tout est g r Donc c est OK Tableaux carr s d un nombre quelconque de cases lls sont cr es normalement les conditions de victoires ou de match nul y sont reconnues tout le temps Donc OK Tableaux pas carr s Ils sont cr es normalement et on s y d place sans probl mes Le match nul est d tect sans probl me Mais le programme ne d tecte pas toujours les victoires en diagonales et anti diagonales lorsque les diagonales gagnantes ont une case sur la premi re ligne ou la premi re colonne
5. la lisibilit de votre code ainsi que les commentaires que vous pourrez y faire ou que vous crirez dans le document joint seront pris en compte dans la note finale Vous me rendrez le projet comme d habitude sous format lectronique document joint y compris Pr venez moi avant de commencer r diger ce document pour m indiquer quel logiciel vous utiliserez pour ce faire afin de vous assurer que je pourrai le relire Le projet est rendre pour le vendredi 25 f vrier report au vendredi 4 mars 2005 LICENCE INFORMATIQUE P Module Environnement de Programmation EPDP 1 Page 4 sur 23 F 60e X Xmorpion 1 Pr sentation du projet L objectif de ce projet est d crire un jeu de morpion Je rappelle que ce jeu se joue deux chaque adversaire jouant tour de r le pour cocher une case Le plateau comporte trois lignes et trois colonnes de cases Le jeu se remporte en alignant trois cases verticalement horizontalement ou diagonalement Votre programme offrira la possibilit de jouer deux ou seul contre l ordinateur De plus le jeu sera g n ral dans le sens o vous donnerez la possibilit de jouer sur un plateau pouvant comporter plus de trois lignes et colonnes et o le nombre de cases aligner pour gagner pourra tre de trois comme dans la version classique ou plus Ceci vous permettra d avoir une bonne base pour un jeu de puissance 4 1 1 Les modules crire Comme dit plus haut il y a deu
6. a int b fonction qui fait jouer l ordinateur en utilisant minimax qui utilise les coups possibles int ecrit coup cpu crit le coup jou par l ordinateur dans le tableau de jeu e int deroulement fonction qui g re l alternance des joueurs LICENCE INFORMATIQUE P Module Environnement de Programmation EPDP 1 Page 18 sur 23 ee X Xmorpion Game c et Game h Game c est un module qui permet de g rer la partie algorithmique du jeu Il impl mente plusieurs fonctions et structure n cessaires au bon d roulement du jeu struct Game Cr e une structure permettant de conna tre les informations sur le jeu tout moment du jeu En effet elle permet de conna tre le dernier joueur avoir jou de savoir quelle case est occup e et par qui gr ce au tableau d entier ainsi que toutes les informations n cessaires au jeu nombre de colonne de ligne et de cases aligner du morpion extern Game newGame int nlines int ncolumns int nalign int p alloue une structure Game pour un tableau de jeu de nlines lignes et ncolumnes colonnes que l on gagne en alignant nalign cases Le type Player sera d finir par nos soins et devra permettre d indiquer quel joueur joue en premier extern Game deleteGame Game g lib re la place m moire allou e pour une structure Game et renvoie un pointeur vers NULL e int alloueTab int nl int nc met jour le jeu en cochant la case active Le fait de savoir qu
7. au minimum e une structure pour stocker les informations graphiques sur le jeu et g rer son affichage appel e XGame ci dessous e une structure pour stocker le jeu lui m me et les fonctions associ es implantant les algorithmes d intelligence artificielle appel e Game ci dessous Nous allons pr sent entrer dans le vif du sujet vos claviers et vos neurones LICENCE INFORMATIQUE P Module Environnement de Programmation EPDP 1 Page 7 sur 23 r eee X Xmorpion 2 Partie graphique Dans un premier temps le but final de cette partie sera d crire un programme Xmorpion permettant deux joueurs de s affronter La taille du tableau de jeu en nombre de lignes et colonnes sera configurable ainsi que le nombre de cases aligner 2 1 Le module XGame Le c ur de votre programme sera une structure nomm e xGame Cette structure et les fonctions associ es permettant de la manipuler seront d finies dans le module xGame form des fichiers xGame h pour l en t te et xGame c pour le code La structure xGame doit contenir tout ce qui permet de d crire un jeu Id alement elle contiendra un pointeur vers une structure Game voir la partie algorithmique mais comme dans un premier temps les deux parties doivent tre ind pendantes vous aurez crire un minimum de choses concernant la structure Game Cette criture peut tre faite en commun entre les deux quipes et permettra de d finir une base d interface a
8. gt nombre de cases aligner n cessairement plus petit ou gal lignes et colonnes lt config gt c est la configuration ou aussi le nombre de joueur on Joue lou 2 lt Player gt c est le joueur qui commence S il n y a qu un joueur c est n cessairement le premier joueur 0 0 w7 000 X Xmorpion cran de bienvenue Si les param tres sont valides vous aurez cet alors cet cran Il est utile et pas uniquement pour faire joli Il permet de familiariser Yy l utilisateur avec deux concepts touchant mor pion l interface de ce jeu rod l faut placer le pointeur de la souris dans la Arnaud Grausem fen tre pour que celle ci r ponde TETUN ETES On l invite utiliser les fl ches pour qu il amp comprennent que c est par cet interface qu il communique avec le jeu et pas avec la souris Il faut donc presser une fl che Dimitri Dupuis Latour Plateau de jeu La fen tre est alors recadr e la dimension de votre plateau de jeu Le joueur qui commence est indiqu en haut Tout au long du jeu le joueur qui la main sera indiqu cet endroit On y verra aussi des messages d erreur case occup e ou le message de fin de match Les fl ches vous permettent de d placer la case active symbolis e par une bordure rouge Une fois votre case choisie pressez Enter c est au tour de l autre joueur maintenant sauf si votre case n tait pas libre 090 X Xmorpion
9. param tre une profondeur de r cursion maximale et vous proposerez une fonction permettant d valuer la valeur d une position non terminale de jeu Dans ce but il faudra s rement introduire des score interm diaires entre les gains de l un ou l autre joueur Vous pourrez donc utiliser un gros score de type 100000 ce qui vous laissera de la place pour qualifier les situations interm diaires Pour la r daction de ces parties il sera s rement b n fique d inverser les quipes l quipe qui aura fait la premi re partie graphique se chargera d am liorer l algorithme MinMax et l autre quipe charg e originellement de la partie algorithmique effectuera l int gration LICENCE INFORMATIQUE P Module Environnement de Programmation EPDP 1 Page 14 sur 23 F eee X Xmorpion Organisation du Travail 1 Mise en place du travail Formation des deux groupes D s que l quipe f t form e on a rapidement pu former les deux quipes Algo et graphismes dans la mesures o certains taient tr s tent s par l une ou l autre des sp cialit s Comme il tait conseill chacun a d abord lu et relu plusieurs fois l nonc pour bien le comprendre notamment les fonctions de Xresource et bien s en impr gner Une fois que l on avait saisi le fonctionnement du jeu on a d fini les fonctions communes aux deux groupes dont on aurait besoin Les prototypes de ces fonctions isFull isWin ainsi que la structures Gam
10. 000 X Xmorpion Rapport de projet Myriam No l Arnaud Grausem Christophe Dessaint Pierre Emmanuel Pign de amp Dimitri Dupuis Latour Programmation en C NAINY a ee X Xmorpion Table des Mati res Pr face Bienvenue dans Xmorpion Enonc TP Not 2 Microprojet C 1 Pr sentation du travail 2 Partie Graphique 3 Partie Algorithmique 4 Int gration Organisation du Travail 1 Mise en place du travail 2 R partition des t ches Explications du programme 1 Mode d emploi du jeu 2 Descriptif des fonctions sl Anorpion LICENCE INFORMATIQUE P Module Environnement de Programmation EPDP 1 Page 2 sur 23 60e X Xmorpion Pr face Bienvenue dans Xmorpion Vue d ensemble des fonctionnalit s de Xmorpion Xmorpion permet de jouer au jeu du morpion seul contre l ordinateur ou deux De plus et contrairement au morpion traditionnel il n est pas limit des tableaux de 3x3 ni m me des carr s d ailleurs On peut ainsi jouer sur des tableaux de 3x8 ou m me 6x6 Laissez libre cours votre imagination eee X Xmorpion Morpion Traditionnel 60e X Xmorpion Q OIXJO Q Q Q Morpion volu Xmorpion vous laisse jouer comme vous I entendez LICENCE INFORMATIQUE PA Module Environnement de Programmation EPDP 1 Page 3 sur 23 Le eee X Xmorpion nonc TP Not 2 Microprojet C Organisation du t
11. VOUS Xmorpion c Ce programme vous montre d j comment ouvrir une fen tre graphique dans laquelle on peut dessiner et comment g rer les v nements e Exposition v nement qui est g n r automatiquement quand la fen tre est au moins partiellement recouverte ou d couverte Il faut en g n ral lancer une fonction qui redessine le contenu de la fen tre C est le r le de la fonction prawit Dans le code que je vous donne prawit redessine le tableau du jeu avec des cases coch es A votre charge de changer le code par un appel une fonction de dessin du jeu que vous crirez dans le module xcame c e Touche appuy e lorsque vous appuyez sur une touche alors que votre curseur de souris est dans la fen tre la fen tre re oit un v nement clavier Le code de xmorpion c appelle alors automatiquement la fonction KkeyPressed J ai ins r un embryon de code vous permettant de voir comment r agir diverses touches frapp es j ai mis un case pour chaque touche que vous serez amen s g rer dans le cadre du projet en particulier j ai li tout appui sur la touche q ou Q la sortie du programme appel la fonction Exitapp vous de programmer les autres touches J ai mis dans le code de xmorpion c les endroits o vous devriez ins rer du code de mani re vous guider dans votre modification de ce fichier Peu de modifications sont r aliser L essentiel de votre travail consiste crire des modules
12. akefile linux depend g n re automatiquement un fichier qui indique les d pendances des fichiers c quels h y sont inclus Donc la premi re fois que vous compilez ou lorsque vous ajoutez un nouveau module sous Linux il convient de taper make f Makefile linux depend avant de taper make f Makefile linux Les sections qui suivent d crivent les deux parties ind pendantes que vous aurez programmer par sous quipe Une troisi me section vous aide pour l int gration Prenez garde tout lire avant de vous lancer dans la programmation car m me si les deux parties sont ind pendantes dans un premier temps il vous faudra garder toujours l esprit l tape finale d int gration Pour la simplifier il est donc sage de se mettre d accord sur un minimum de structures discutez donc de ce que vous mettrez dans vos structures principales avant de pianoter sur vos claviers A noter que la d marche ainsi que les algorithmes que je propose ne sont pas forc ment optimaux Comme dans tout projet il vaut mieux d buter par quelque chose de simple m me si sub optimal mais qui marche avant de se lancer dans les optimisations Vous avez tout loisir de proposer des fonctions o une architecture plus ad quates Les seules contraintes que je mets sont e un code principal fichier contenant la fonction main c est dire Xmorpion c et morpion c minimaliste I ne doit pas contenir de fonctions nouvelles et les fonctions seront compl t es
13. e furent d finies ensemble puis regroup s dans le fichier d en t te Game h fichier qui servit aux deux groupes avant l int gration finale Difficult s rencontr es Le d veloppement fut rendu difficile par le fait que l on a pu faire fonctionner X11 que sur un seul des ordinateurs du groupe et que donc les compilations interm diaires et finales durent se faire uniquement sur celui ci De plus les salles machines furent ferm es juste avant la date de remise du TP cause de vols qui s y seraient produits De ce fait l int gration na pas pu tre pouss e son terme chacunes de leur c t la partie algo et la partie graphique compilent et s ex cutent en mode texte pour la partie algo Mais lorsqu il a fallu int grer les deux seuls les tests de fin de partie isWin et isFull purent tre int gr s Cela permet n anmoins de jouer graphiquement une partie deux joueurs sans probl mes Notions abord es Malgr cela nous sommes assez content du r sultat dans la mesure o ce TP nous a permis enfin de cr er un programme graphique a change des programmes en mode texte De plus on a pu d couvrir ou approfondir certaines notions la librairie X11 la programmation v nementielle avec les EventsHandler la programmation modulaire bien r diger les headers les ifndef make et les makefile l algorithme MinMax qui d apr s la litt rature circulant sur internet est un algorithme tr s connu
14. e un jeu nombre de lignes de colonnes nombre de cases aligner pour gagner dernier joueur avoir jou Pour ce joueur et de m me que dans XGame vous pourrez d finir un type Player Afin de d crire le jeu courant vous utiliserez deux champs un premier champ sous forme de tableau bidimensionnel de la taille du tableau de jeu en nombre de lignes et colonnes Chaque case sera de type Player en prenant garde d finir dans votre num ration un cas None c t de HUMAN et COMPUTER Le tableau tant petit nous ne sommes pas contraints ici par des consid rations de performance Un tableau classique pas forc ment lignes contigu s est donc tout fait adapt une liste cha n e de positions qui garde en m moire tous les coups jou s La fonction updateGame mettra jour le jeu en cochant la case donn e en param tre liste cha n e tableau de cases et dernier joueur La fonction undoGame fera de m me mais l envers aucune case n est pass e en param tre dans ce cas on obtient la position par un popList sur la liste des coups jou s Vous aurez galement besoin de d finir des fonctions externes comme isWin et isFul1 pour savoir si le jeu est termin par un gain ou une partie nulle ou encore isAccessiblePosition pour savoir si une position donn e peut tre coch e dans le jeu Des fonctions internes devront tre crites pour le calcul MinMax notamment un nextMoves qui renvoie la liste des positio
15. el est le joueur courant sera g r e de mani re interne int isWin Game g int joueur fonction caract risant les conditions de victoire int isFull Game g fonction caract risant le cas du match nul e int isAccessiblePosition Game g int i int j fonction permettant de savoir quelle case est libre void updateGame Game g int i int j int joueur met jour le jeu avec le joueur ayant jou et la case qui a t jou e et stocke la position jou e dans la pile void undoGame dejoue un coup void nextMoves Game g stocke dans la pile les coups accessibles e int minimax Game g int joueur int mi int mj fonction g n rant l IA du jeu LIFOList c et LIFOList h LIFOList c est un module impl mentant des fonctions g rant une pile LIFO struct Position Cr e une structure position dont les l ments sont un entier ligne un entier colonne et un pointeur vers une position struct LIFO cr e une structure lifo dont les l ments sont un pointeur vers la position de t te de la liste extern lifo newList lifo liste alloue une structure liste extern position popList lifo liste position p d pile une position de la liste et renvoie la position d pil e extern void deleteList lifo liste lib re la place m moire allou e pour une structure lifo extern void pushList int i int j lifo liste empile une position sur une liste donn e LICENCE INFORMATIQUE P Module Environnemen
16. ion des fen tres lancement du jeu cr ation des eventsHandler Drawlt affiche le plateau de jeu les messages les crans d entr e et de sortie et redimensionne les fen tre quand il le faut Beaucoup de ces actions sont d l gu es drawxGame KeyPressed d place la case active et v rifie qu elle reste dans les limites du tableau D s qu il y a victoire ou match nul le clavier est bloqu c est dire que seul la touche Q est activable Sans cela le jeu continuait et l affichage devenait chaotique car a n a pas de sens de continuer le jeu alors que la partie est finie Xresource c et Xresource h Le module xresource c et h d finit les fonctions d affichage graphique utilis es par le programme ces fonctions sont bas es sur la librairie X11 Ces deux fichiers n ont pas t modifi s de plus ni les timers ni les timeout n ont t s utilis s M me si on aurait pu LICENCE INFORMATIQUE P Module Environnement de Programmation EPDP 1 Page 20 sur 23 e ee X Xmorpion XGame c et XGame h Le module xGame stocke les informations graphiques du jeu dans sa structure XGame et g re son affichage La structure XGame contient e Game g pointeur sur une structure Game qui g re tout ce qui n est pas graphique e XPoint caseActive Pixmap bkg cross circle border credits diff rentes images dont l cran d ntr e int bkgwidth bkgheight int case_width case_height int b
17. modifier dans la version avec arbres tronqu s On peut alors donner r cursivement une valeur chaque n ud en remontant dans l arbre pour un n ud H V n min pefils n V p pour un n ud O V n max pefils n V p LICENCE INFORMATIQUE P Module Environnement de Programmation EPDP 1 Page 11 sur 23 e ee X Xmorpion 3 2 Implantation de MinMax En pratique l arbre est virtuel c est dire que vous n allez pas commencer par calculer l arbre entier du jeu et le garder en m moire mais bien d estimer pour chaque position sa valeur de mani re r cursive l arbre n tant jamais stock dans son entier en m moire Bien s r ce n est pas optimal surtout que si on se d brouille bien l arbre n est pas si gros que a pour un petit jeu de morpion Cependant la taille de l arbre grandit tr s vite Pire la complexit du calcul est exponentielle et vous vous apercevrez que le calcul rapide pour une taille de jeu 3 x 3 devient tr s lente pour un jeu 3 x 4 Il conviendra donc de modifier l algorithme ce que nous verrons plus tard Enfin nous n avons pas vu les structures arborescentes seulement les listes chain es qui posent a priori d j suffisamment de probl mes tant donn une position courante nous voulons donc calculer sa valeur La formule est r cursive par nature La d marche que je vous propose est la suivante e obtenir la liste des positions accessibles pour chaque position accessible
18. ns accessibles partir d une situation de jeu donn e Enfin vous crirez un programme morpion c qui prend en param tres les informations sur le jeu nombre de lignes de colonnes de cases aligner premier joueur cr e une structure Game et permet de jouer contre l ordinateur Le jeu sera affich sous format texte apr s chaque coup un coup sera entr par l humain par son num ro de ligne et de colonne LICENCE INFORMATIQUE P Module Environnement de Programmation EPDP 1 Page 13 sur 23 F eee X Xmorpion 4 Partie int gration Cette partie est la partie finale o vous allez int grer tous ce que vous avez fait afin d avoir un programme graphique qui permet de jouer au morpion contre un joueur ou contre l ordinateur Deux choses seront faire dans cette partie modifier XGame pour int grer la structure Game et purer le module XGame de tous les aspects calculatoires d j pr sents dans Game am liorer l algorithme MinMax En effet vous vous apercevrez que le temps de calcul devient prohibitif m me pour des petits tableaux de jeu type 5 x 5 Une mani re d am liorer les choses est de faire appel l algorithme AlphaBeta mais m me celui ci montre assez vite ses limites La seule solution est de tronquer l arbre de jeu autrement dit la profondeur de r cursion dans le calcul MinMax ce qui revient savoir valuer une position de jeu non terminale Vous modifierez la fonction MinMax pour qu elle prenne en
19. order_width border_height int borderwidth int debut marque le d but du jeu vaut 0 tant que l on est sur l cran d intro 1 apr s int fin marque la fin du jeu fin de la partie 1 ecran de sortie 2 sortie de l application 3 int config 1 pour un joueur contre l ordi 2 pour 2 joueurs face face char msg le message afficher comme le joueur 1 a la main ou Match nul l Le module XGame contient lui extern XGame newXGameQ int nlines int ncolumns int nalign int p int config alloue une structure XGame extern XGame deleteXGame XGame xg lib re la place m moire allou e pour une structure XGame et renvoie un pointeur vers NULL extern int updateXGame XGame xg coche la case active extern int setActiveXGame XGame x rend active la case situ e sur la ligne line et La colonne column c est dire que cette case sera coch e sur le joueur appuie sur la touche de retour chariot extern int drawXGame XGame xg Widget draw int x int y dessine le tableau du jeu dans la fen tre X draw LICENCE INFORMATIQUE AT Module Environnement de Programmation EPDP 1 Page 21 sur 23 e ee X Xmorpion Game c et Game h Le module Game stocke dans sa structure Game toutes les les informations du jeu autres que graphiques et g re le bon d roulement du jeu Il a d j t d crit dans la partie algorithme Remarques sur l affichage La fonction drawXGame e
20. phe un n ud est une position e les fils d un n ud sont les positions autoris es pour le joueur suivant un n ud est terminal si la partie est gagn e par l un des joueurs ou si le tableau est plein toutes les cases sont coch es match nul Une partie se code donc comme une suite de coups chacun tant fils du pr c dent L algorithme MinMax permet de donner une valeur chaque n ud du graphe et ainsi en comparant les valeurs de tous les n uds fils d une position donn e d terminer quel est le meilleur coup jouer Cet algorithme n est pas le plus performant ni le plus efficace Sa complexit est de plus assez importante comme vous vous en apercevrez mais son principe est simple et il fonctionne bien pour le morpion Une fois que vous aurez cod cet algorithme le codage futur hors TP d algorithmes plus compliqu s devrait tre simplifi Le but de l algorithme MinMax est donc d attribuer une valeur chaque n ud Dans une partie deux joueurs Humain et Ordinateur chaque n ud est soit H soit O selon que le dernier joueur avoir coch une case est l Humain ou l Ordinateur Tous les fils dun n ud H sont O et vice versa On commence par attribuer tout n ud terminal la valeur V n pour les n uds O gagnants V n pour les n uds H gagnants V n 0 pour les n uds H ou O nuls En pratique l infini tant difficile coder on utilisera les valeurs 1
21. qui seront utilis s par xmorpion c J ai encapsul toutes les fonctions li es l interface graphique dont vous devriez avoir besoin J utilise volontairement la librairie Xwindow directement m me pas de Motif afin que le code puisse tre compil sur tout syst me multifen trage bas Unix qui utilisent tous Xwindow Toutes les fonctions sont document es dans Xresource h Il y a deux structures qui ne sont pas utilis es dans xmorpion c les timers et les timeouts Un timer est un objet qui est charg d appeler une fonction intervalles r guliers jusqu ce qu on l arr te explicitement Un timeout est un objet charg d appeler une fonction une et une seule fois apr s un intervalle de temps qui court partir du lancement du timeout Ces structures peuvent tre utiles si vous voulez g rer des aspects temporels A priori vous n avez pas les employer dans ce projet LICENCE INFORMATIQUE P Module Environnement de Programmation EPDP 1 Page 6 sur 23 r eee X Xmorpion Enfin je vous donne galement le Makefile vous permettant de taper juste make pour recombpiler votre projet Tapez make clean pour nettoyer les fichiers o et le binaire noter que ce Makefile fonctionne sous atlas Si vous voulez compiler sous Linux je vous fournis un Makefile pour Linux tapez alors make f Makefile linux Attention il y a deux autres cibles e make f Makefile linux clean efface tous les fichiers o nettoyage e make f M
22. ravail Vous r aliserez ce travail par quipes de quatre Vous accompagnerez le code d un texte d crivant vos structures et fonctions sorte de manuel utilisateur de votre code et me pr cisant qui a fait quoi lors d un travail en groupe il est tr s important d analyser le probl me et de se rendre compte des difficult s de chaque question La mani re dont vous vous serez r parti le travail sera donc prise en compte En particulier dans ce projet il y a deux grandes parties une partie algorithmique et une partie graphique C est en g n ral une bonne id e de bien s parer les calculs de l affichage Cela correspond deux styles de programmation tr s diff rents et en tudiant un peu le probl me on se rend souvent compte que les deux parties sont d corr l es Je vous demanderai donc de faire deux quipes de deux une quipe charg e de la partie algorithmique et une quipe charg e de la partie graphique Normalement des programmeurs exp riment s commencent par r diger de mani re commune l interface entre les diff rentes parties d un projet savoir dans ce cas un fichier en t te h pour la partie algorithmique Comme pour beaucoup d entre vous l exp rience est encore manquante chaque quipe de deux va plut t commencer par faire un programme s par puis vous passerez dans une deuxi me tape l int gration en commen ant par d finir ce fichier d en t te Il va de soi que comme d habitude
23. rs plusieurs images par seconde et cr ant ainsi l illusion du mouvement Peut tre pour une version 22 2 On va essayer de joindre ces fichiers et ou le mov avec le rapport si la taille des pi ces jointes n est pas trop limit e En tous cas ils existent LICENCE INFORMATIQUE PA Module Environnement de Programmation EPDP 1 Page 22 sur 23 ee X Xmorpion Autres fichiers Makefile Le fichier Makefile sert compiler les sources en un ex cutable UNIX Ce fichier est celui recherch lorsque l on invoque la commande make On dispose de 3 Makefile e Makefile linux pour compiler sous Linux e Makefile sun pour compiler sous Sun machine atlas e Makefile qui est une copie de Makefile sun e Pour compiler se placer dans le r pertoire o est le Makefile et faire successivement gmake depend cela cr e un fichier depend inc qui d finit automatiquement les d pendances entre les fichiers o et les fichiers c h et xpm En effet une r gle de Makefile du style c o ne d finit une d pendance qu entre le o et le c et pas les h gmake cela compile tous les fichiers objets o et fait l dition de liens pour g n rer le binaire uniquement si c est n cessaire gmake clean si vous souhaitez faire le m nage en effa ant tous les o et le fichier depend inc Pour compiler sous Atlas il faut ajouter son login la ligne setenv LD_LIBRARY_PATH usr local dp gnu gettext lib lib
24. st parsem e de constantes num riques telles que xg gt borderwidth 5 j xg gt case_width 5 Pour essayer d expliquer pourquoi il y a des 1 5 13 diss min s un peu partout sans raison apparentes voici un sch ma qui montre comment est construite mon interface H w Xmorpion Bordure Noire 2 Pixels Case Active 68x68 pixels 2 pixels d paisseur Croix ou Rond 64x64 pixels Grile lpixel caract res 13 pixels de Haut 15 68 pixels 64 pixels Les crans de bienvenue la place des crans de bienvenue et de sortie il tait pr vu de faire au d part une animation en introduction Nous y tions presque mais devant le retard que prenait le reste du projet on a laiss de c t estimant que la partie graphique tait d j suffisamment au point Comment afficher un petit film avec X11 Voici comment on a proc d Avec un logiciel de pr sentation Keynote le PowerPoint d Apple on a fait une animation avec des titres qui entrent et qui sortent On l a export en mov disponible en PJ peut tre Avec QuickTime on a convertit ce film en une suite d images png Avec un logiciel de traitement d images Graphic Converter on a d abord r duit le poids des images descente 256 couleurs r duction du nombre de pixels puis on a cr e une t che pour automatiser la conversion en XPM Au final on se retrouve avec 43 images XPM on comptait afficher rapidement l aide de time
25. t de Programmation EPDP 1 Page 19 sur 23 e ee X Xmorpion Partie Graphique Quelques mots sur X11 Le syst me de fen trage X X Window System plus souvent appel X11 est quasiment le seul syst me de fen trage utilis par toutes les applications graphique sur tout syst me bas UNIX Mac OS X bas UNIX utilise cependant Quartz comme Window Manager mais il peut galement ex cuter simultan ment des programmes X11 gr ce aux librairies X11 et un serveur X bas sur le projet OpenSource XFree86 Nous le pr cisons car c est sur cette plateforme qu a t d velopp e l interface graphique de Xmorpion et ce beau PDF The D 412214 Project Inc Toute les fonctions d affichage des graphismes de Xmorpion utilisent les librairies X11 le rendant ainsi portable sur de nombreuses plateformes Mac OS X Linux SunOS Atlas et toutes plateforme UNIX impl mentant X11 Malgr tout cela ne fait que 5 des ordinateurs Xmorpion c et Xmorpion h Le module xmorpion est le code principal c est lui qui contient la fonction main qui est appel e au lancement du programme Il permet deux joueurs de jouer l un contre l autre Il contient aussi deux autres fonction Drawit et KeyPressed qui sont appel es par les events handlers et qui elles m mes appellent respectivement draxXGame et setActiveXxGame Main traitement des arguments pass es en ligne de commande cr at
26. tte variable en param tre de CreatePixmapFromData pour g n rer la pixmap appropri e Voir Xmorpion c pour un exemple d une telle manipulation LICENCE INFORMATIQUE P Module Environnement de Programmation EPDP 1 Page 9 sur 23 Ea 09O X Xmorpion 2 3 Travail r aliser Dans cette partie vous aurez compl ter xmorpion c de mani re permettre le jeu entre deux joueurs Pour ce faire vous utiliserez une variable globale de type XGame Les nombres de lignes colonnes nombre de cases aligner premier joueur seront pass s en arguments du programme xXmorpion e La fonction Drawlt sera modifi e de mani re ne faire appel qu la fonction drawXGame Les diff rents case de la fonction KeyPressed seront modifi s de mani re faire appel aux fonctions setActiveXGame touches de fl ches et updatexGame touche de retour chariot e La fonction main sera modifi e de mani re traiter les arguments du programme allouer la variable globale de type XGame et cr er la fen tre de jeu e La fonction drawXGame dessinera dans la fen tre pass e en argument une pixmap dans laquelle auront t dessin es des lignes pour d limiter les lignes et colonnes puis affichera pour chaque case coch e la croix ou le rond en fonction du joueur Vous proposerez un mode d affichage pour montrer quelle est la case active celle que le joueur s lectionnera s il tape sur retour chariot Pour cela vous pourrez par exemple d finir de no
27. u sens fichier h entre les deux parties Je vous laisse le soin de d finir votre structure xGame et les fonctions associ es Je veux au minimum avoir les fonctions suivantes XGame newXGame int nlines int ncolumns int nalign Player p qui alloue une structure xGame pour un tableau de jeu de nlines lignes et ncolumns colonnes que l on gagne en alignant nalign cases Le type Player sera d finir par vos soins et devra permettre d indiquer quel joueur joue en premier XGame deleteXGame XGame xg qui lib re la place m moire allou e pour une structure XGame voir la fonction pr c dente et renvoie un pointeur vers NULL int setActiveXGame XGame xg int line int column qui rend active la case situ e sur la ligne line et la colonne column c est dire que cette case sera coch e sur le joueur appuie sur la touche de retour chariot e int updateXGame XGame xg qui met jour le jeu en cochant la case active Le fait de savoir quel est le joueur courant sera g r de mani re interne e int drawXGame XGame xg Widget draw int x int y qui dessine le tableau du jeu dans la fen tre X draw le coin sup rieur gauche du tableau de jeu ayant pour coordonn es x y dans la fen tre draw Cette derni re fonction est la seule qui m rite quelques explications car elle fera appel aux fonctions du module xresource que je vous fournis Il me faut commencer par d finir ce qu est une pixmap 2 2 Les pixmaps Une pi
28. usr lib usr local lib usr local X11R6 lib Rajoute le r pertoire usr local dp gnu gettext lib dans la variable d environnement LD_LIBRARY_PATH e Pour compiler sous Linux faire une copie de Makefile linux en Makefile Cela vite d avoir taper gmake f Makefile linux chaque fois que vous voulez recompiler par d faut gmake prend le fichier Makefile Anorpion LICENCE INFORMATIQUE P Module Environnement de Programmation EPDP 1 Page 23 sur 23
29. uvelles pixmaps case active vide case active croix case active rond Les fonctions indiqu es ci dessus ne suffisent pas pour faire le jeu vous de d finir et crire les fonctions qui manquent et n oubliez pas de les documenter dans votre rapport final LICENCE INFORMATIQUE P Module Environnement de Programmation EPDP 1 Page 10 sur 23 F eee X Xmorpion 3 Partie algorithmique L objectif de cette partie est dans un premier temps d crire un programme qui permet de jouer au morpion contre l ordinateur L affichage et l indication des cases cocher se fera e uniquement sous forme d entr e sortie au format texte affichage dans une fen tre de commande par des printf et lecture par des scanf Le but plus profond est de d finir une structure Game permettant de stocker et g rer le jeu d crire l algorithme d IA permettant de d terminer le prochain coup de l ordinateur et d crire des petits modules associ s n cessaires au bon fonctionnement de tout a Le programme morpion vous offrira un cadre de validation de votre code Je commence par d crire l algorithme d IA MinMax que vous utiliserez puis je d crirai le squelette de base de la structure Game que vous devrez crire 3 1 L algorithme MinMax J ai d j bri vement d crit cet algorithme en cours La base du concept est que le jeu du morpion tout comme le jeu de puissance 4 ou encore le jeu d chec peut se d crire sous forme de gra
30. visualiser le contenu par une simple commande cat cross xpm Vous voyez que c est simplement un tableau de chaines de caract res comme argv La premi re chaine de caract res donne des informations sur l image largeur en pixels ici 64 hauteur en pixels ici 64 nombre de couleurs 2 nombre de plans 1 Les lignes suivantes font l association entre un code ASCII un caract re et une couleur nous avons donc un caract re suivie de c pour couleur suivie du codage couleur dans ses trois composantes R ed G reen et Blue chacune cod e en hexad cimal pr c d e d un entre 0 et 255 c est dire entre 00 et FF La premi re couleur est donc associ e au caract re espace et est la couleur transparente NONE La deuxi me couleur est associ e au caract re et est en gros un rouge R FF 255 G 00 B 01 Ensuite nous avons une chaine de caract res par ligne de l icone Chaque chaine de caract res contient donc autant de caract res qu il y a de colonnes chacun de ces caract res codant la couleur d un pixel La fonction CreatePixmapFromData disponible par Xxresource h permet de g n rer une pixmap partir d un tel fichier au format XPM il suffit d inclure ce fichier dans le programme C appelant CreatePixmapFromData une nouvelle variable globale au module et du nom de l image est alors d finie pour l icone ci dessus la variable est nomm e cross _xpm et il ny a qu passer ce
31. x parties bien distinctes dans ce projet Une premi re partie concerne l affichage graphique et l interaction Elle conviendra aux personnes qui aiment la programmation d interface et qui sauront s adapter au style de programmation de tierces personnes en l occurrence moi car il faudra utiliser la biblioth que d outils graphiques que je mets votre disposition Cette biblioth que ne comporte qu un ensemble limit de fonctions et il faudra savoir jongler avec ces capacit s limit es pour obtenir ce que vous d sirez Cette premi re partie concerne l criture du code principal Xmorpion c ainsi que du module xGame c Une deuxi me partie est plus algorithmique et concerne le jeu contre l ordinateur Elle conviendra aux personnes int ress es par la programmation d algorithmes d intelligence artificielle et d sireux de faire leur code de A Z aucune biblioth que ne sera mise votre disposition hormis la biblioth que standard et il vous faudra crire toutes les fonctions dont vous aurez besoin Cette partie concernera l criture d un programme principal de jeu de morpion en ASCII afin de tester les choses morpion c d un module Game c ainsi que d un module de gestion d une liste chain e LIFolist c LICENCE INFORMATIQUE P Module Environnement de Programmation EPDP 1 Page 5 sur 23 F eee X Xmorpion e 1 2 Outils mis votre disposition Vous baserez votre code sur l embryon de programme que j ai crit pour
32. xmap est tout simplement une image au sens de Xwindow La fonction CreatePixmap dans Xresource h permet de cr er une pixmap vide de largeur et LICENCE INFORMATIQUE P Module Environnement de Programmation EPDP 1 Page 8 sur 23 ee X Xmorpion hauteur donn es en pixels Nous allons utiliser une pixmap vide pour le fond du tableau de jeu Une pixmap a ceci d int ressant que c est un drawable c est dire un objet graphique X dans lequel on peut dessiner Un autre exemple de drawable est la fen tre de type widget et nomm e draw dans Xmorpion c que vous passerez en param tre de la fonction rawxGame Dessiner dans un drawable veut dire y dessiner des lignes fonction DrawLines de Xresource h pour un Widget et DrawLinesInPixmap pour dessiner dans une pixmap mais aussi y imprimer des pixmaps fonction PlacePixmapInWindow pour imprimer dans une fen tre widget ou PlacePixmapInPixmap pour imprimer dans une pixmap Il existe un format tr s sympathique pour les petites images icones le format XPM fichiers d extension xpm Il est sympathique parce qu il code l image en ASCII et qu il la code dans une structure C Une image peut donc tr s simplement s inclure au moyen de la directive de pr compilation include Vous en avez un exemple dans xmorpion c Le fichier cross xpm contient l icone codant une croix utilis e pour cocher une case par un des joueurs l autre fait un rond cod dans circle xpm Vous pouvez en
Download Pdf Manuals
Related Search