Le programme principal se trouve dans la classe «Mastermind»
télécharger 88.56 Kb.
|
| Rapport de projet Informatique de Base Création d’un Master-Mind à six couleurs et quatre possibilités. Projet à réaliser en Java. La seconde partie intégrera une intelligence artificielle capable de résoudre sans intervention humaine le plus rapidement possible la combinaison entrée par un humain. Loïc Ehre Olivier Versanne 1ère année groupe 3  2007 – 2008 IntroductionLe projet est divisé en deux parties qui forment à terme un seul programme. La première partie consiste à la création de l’interface du jeu de Master-Mind pour que l’utilisateur puisse saisir des combinaisons de couleurs dans le but de trouver la combinaison proposée aléatoirement par l’ordinateur. La seconde partie complète le jeu en ajoutant une intelligence artificielle qui doit trouver la combinaison choisie par un utilisateur en un minimum de coups.  Cas d’utilisation Structuration du projetJava étant un langage de programmation objet, nous avons décidé de tirer partie des avantages de cette méthode de programmation et avons découpé notre projet en différentes classes, comme vous pouvez le voir sur le schéma UML suivant.  Diagramme UML MastermindLe programme principal se trouve dans la classe « Mastermind ». Celle-ci va définir deux instances de la classe abstraite Joueur qui seront de type ordinateur contre humain (à noter qu’avec notre modèle de conception, il est possible de faire jouer deux humains ensemble ou deux ordinateurs ensemble). if(choix == 1){ // L'utilisateur recherche la combinaison this.cacheur = new Ordinateur(); this.chercheur = new Humain(); } else if(choix == 2) { // L'utilisateur crée la combinaison this.cacheur = new Humain(); this.chercheur = new Ordinateur(); } Grâce à la généralisation, il est très simple de définir les cas de jeu JoueurLa classe Joueur généralise la conception et permet donc de programmer simplement la différence entre un Ordinateur et un Humain ce qui rend facile l’alternance d’un joueur humain avec un joueur informatique. abstract public class Joueur { /*Classe abstraite de généralisation utilisée dans Mastermind.java pour * définir un joueur (humain ou informatique) */ protected Combinaison combinaison; // Uniquement utilisé dans le cas où le joueur est celui qui cache public Combinaison get_combinaison() { return this.combinaison; } // Création de la combinaison abstract public void creer_combinaison(); // Recherche de la combinaison abstract public void chercher_combinaison(Combinaison c); } Classe Joueur CombinaisonLa classe Combinaison représente les associations des quatre billes du Master-Mind. La classe gère les combinaisons avec un tableau d’entier de longueur quatre. La classe est composée de plusieurs méthodes. La méthode bienPlace qui retourne le nombre de billes bien placée, ou le nombre de témoins noirs, et la méthode malPlace qui retourne le nombre de billes en mauvaise positions (témoins blancs). Nous avons dissocié ces méthodes afin de pouvoir utiliser leurs résultats directement dans des tests en optimisant ainsi le nombre de calculs effectués. ConstanteLa classe Constante regroupe toutes les constantes utilisées dans le programme ; du nom du jeu au nombre de pion en passant par la valeur entière correspondante aux couleurs. Cette classe est aussi munie d’une fonction indiquant si un entier correspond à une couleur. ConsoleNous avons créé une classe Console et n’avons pas utilisé celle qui était disponible car celle-ci n’avait ni les méthodes que nous attendions ni la gestion de l’affichage souhaité. Cette classe est dotée de « fonctions raccourcies » comme println ou print qui permettent d’éviter de saisir à chaque fois System.out.println(), de la fonction read qui récupère les caractères saisis, readInt qui recueille un entier saisi en vérifiant qu’il se trouve dans le bon intervalle et enfin readCouleur qui gère la saisie d’une combinaison de couleur et retourne une combinaison. Deuxième phase : « l’Intelligence Artificielle »FonctionnementL’algorithme que nous avons choisi commence par créer l’ensemble des combinaisons possibles (  ). ArrayList ((int)(Math.pow(Constante.NB_PION, Constante.NB_COULEUR))); for(int i = 1; i <= Constante.NB_COULEUR; i++) for(int j = 1; j <= Constante.NB_COULEUR; j++) for(int k = 1; k <= Constante.NB_COULEUR; k++) for(int l = 1; l <= Constante.NB_COULEUR; l++) combin_dispo.add(new Combinaison(i, j, k, l)); Création du tableau initial contenant toutes les combinaisons possibles Il élimine les combinaisons incohérentes avec les résultats des témoins récupérés, jusqu’à obtenir un ensemble très petit dans lequel se trouvera la combinaison. L’algorithme n’a donc pas besoin de se rappeler les résultats et combinaisons précédentes puisque les combinaisons impossibles sont déjà supprimées de l’ensemble. La suppression d’une combinaison de l’ensemble s’effectue en analysant chaque combinaison de l’ensemble par rapport à celle qui a été saisie et nous ne gardons que les combinaisons qui rendent exactement les mêmes témoins. for(int j = 0; j < combin_dispo.size(); j++){ if(combin_dispo.get(j).bienPlace(saisie) != good || saisie.malPlace(combin_dispo.get(j)) != bad){ // On supprime toutes celles qui n'ont pas le même nombre de billes bien placées // ou qui n'ont pas le même nombre de billes mal placées combin_dispo.remove(j); j--; // On reste sur la même combinaison : ArrayList effectue une compression des // indices après une suppression } } Boucle de suppression RobustesseNous avons mis en place plusieurs systèmes de gestion d’erreur. La classe Console gère toutes les mauvaises saisies de la part de l’utilisateur : caractères spéciaux, lettres, espaces, chiffres incorrects… Du côté de l’ordinateur, pour vérifier son bon fonctionnement, nous avons testé toutes les combinaisons possibles plusieurs fois à l’aide de la méthode « brute force », une grosse boucle qui passe d’une combinaison à la suivante, de la première à la dernière. Cela nous a permis de corriger quelques problèmes et de vérifier la stabilité du programme. Statistiques et optimisationsNous avons ensuite profité de l’état « test » du programme pour pouvoir réaliser des statistiques sur l’intelligence de l’algorithme quant aux résultats obtenus et l’optimisation de ceux-ci. La première méthode que nous avons testée nous donnait un ensemble résultat unique. L’algorithme en prenant le premier élément de l’ensemble systématiquement, trouve la combinaison en un intervalle de 1 à 9 essais. L’algorithme n’était pas très performant, même s’il était toujours plus rapide qu’un algorithme aléatoire ou une méthode « Brutus ». Nous avons émis l’hypothèse en décortiquant les résultats que la lenteur venait du fait que l’ordinateur testait toujours la première combinaison. Nous avons donc légèrement modifié notre algorithme afin de prendre une combinaison aléatoire dans l’ensemble trié des combinaisons restantes.
Statistiques obtenus lors de différents tests Les résultats ont été grandement améliorés puisque nous n’avions pas eu de cas où l’ordinateur trouvait en 8 et 9 essais, la moyenne était plus faible d’un essai et l’écart type était aussi plus proche de 0. A la vue de ces résultats, nous avons donc gardé la méthode de choix aléatoire. Jeux de testsVoici deux exemples pour montrer le bon fonctionnement des deux parties. Bienvenue sur Mastermind Sublime IA ''''''''''''''''''''''''''''''''''' Choisissez une option dans le menu suivant : 1 - Trouver la combinaison de Sublime IA (Partie 1) 2 - Laisser Sublime IA chercher votre combinaison (Partie 2) 3 - Sublime IA vs Sublime IA (Ajouts) 4 - Humain vs Humain (Ajouts) 0 - Quitter ---------------------------------------------------------- > 1 ---------------------------------------------------------- Accueil du programme Première partieL’ordinateur a choisi aléatoirement la combinaison [ Rouge, Blanc, Jaune, Jaune ]. Suivons la méthode de « prendre la première combinaison valide de l’ensemble ». Tentative n° 1 Saisissez votre combinaison parmi la liste des couleurs suivantes : 1 = Blanc, 2 = Noir, 3 = Rouge, 4 = Vert, 5 = Bleu, 6 = Jaune (exemple : pour Noir / Vert / Rouge / Bleu, tapez 2435) > 1111 Témoin(s) noir(s) : 1, Témoin(s) blanc(s) : 0 ---------------------------------------------------------- Tentative n° 2 Saisissez votre combinaison parmi la liste des couleurs suivantes : 1 = Blanc, 2 = Noir, 3 = Rouge, 4 = Vert, 5 = Bleu, 6 = Jaune (exemple : pour Noir / Vert / Rouge / Bleu, tapez 2435) > 1222 Témoin(s) noir(s) : 0, Témoin(s) blanc(s) : 1 ---------------------------------------------------------- Tentative n° 3 Saisissez votre combinaison parmi la liste des couleurs suivantes : 1 = Blanc, 2 = Noir, 3 = Rouge, 4 = Vert, 5 = Bleu, 6 = Jaune (exemple : pour Noir / Vert / Rouge / Bleu, tapez 2435) > 3133 Témoin(s) noir(s) : 2, Témoin(s) blanc(s) : 0 ---------------------------------------------------------- Tentative n° 4 Saisissez votre combinaison parmi la liste des couleurs suivantes : 1 = Blanc, 2 = Noir, 3 = Rouge, 4 = Vert, 5 = Bleu, 6 = Jaune (exemple : pour Noir / Vert / Rouge / Bleu, tapez 2435) > 3144 Témoin(s) noir(s) : 2, Témoin(s) blanc(s) : 0 ---------------------------------------------------------- Tentative n° 5 Saisissez votre combinaison parmi la liste des couleurs suivantes : 1 = Blanc, 2 = Noir, 3 = Rouge, 4 = Vert, 5 = Bleu, 6 = Jaune (exemple : pour Noir / Vert / Rouge / Bleu, tapez 2435) > 3155 Témoin(s) noir(s) : 2, Témoin(s) blanc(s) : 0 ---------------------------------------------------------- Tentative n° 6 Saisissez votre combinaison parmi la liste des couleurs suivantes : 1 = Blanc, 2 = Noir, 3 = Rouge, 4 = Vert, 5 = Bleu, 6 = Jaune (exemple : pour Noir / Vert / Rouge / Bleu, tapez 2435) > 3166 Témoin(s) noir(s) : 4, Témoin(s) blanc(s) : 0 Félicitation, vous avez gagné ---------------------------------------------------------- Résolution humaine d’une combinaison Nous trouvons la bonne combinaison en 6 essais. Deuxième partieNous allons choisir une combinaison pour l’ordinateur, prenons la même que celui qu’il nous avait donné et voyons s’il fait mieux. Saisissez votre combinaison parmi la liste des couleurs suivantes : 1 = Blanc, 2 = Noir, 3 = Rouge, 4 = Vert, 5 = Bleu, 6 = Jaune (exemple : pour Noir / Vert / Rouge / Bleu, tapez 2435) > 3166 ---------------------------------------------------------- Tentative n° 1 1296 combinaison(s) possible(s) Combinaison : [ Vert Bleu Blanc Blanc ] Témoin(s) noir(s) : 0, Témoin(s) blanc(s) : 1 1020 combinaison(s) supprimée(s) Appuyez sur la touche Entrée pour continuer > ---------------------------------------------------------- Tentative n° 2 276 combinaison(s) possible(s) Combinaison : [ Noir Noir Rouge Vert ] Témoin(s) noir(s) : 0, Témoin(s) blanc(s) : 1 236 combinaison(s) supprimée(s) Appuyez sur la touche Entrée pour continuer > ---------------------------------------------------------- Tentative n° 3 40 combinaison(s) possible(s) Combinaison : [ Rouge Blanc Jaune Rouge ] Témoin(s) noir(s) : 3, Témoin(s) blanc(s) : 0 38 combinaison(s) supprimée(s) Appuyez sur la touche Entrée pour continuer > ---------------------------------------------------------- Tentative n° 4 2 combinaison(s) possible(s) Combinaison : [ Jaune Blanc Jaune Rouge ] Témoin(s) noir(s) : 2, Témoin(s) blanc(s) : 2 1 combinaison(s) supprimée(s) Appuyez sur la touche Entrée pour continuer > ---------------------------------------------------------- Tentative n° 5 1 combinaison(s) possible(s) Combinaison : [ Rouge Blanc Jaune Jaune ] Témoin(s) noir(s) : 4, Témoin(s) blanc(s) : 0 Sublime IA a trouvé la combinaison : [ Rouge Blanc Jaune Jaune ] ---------------------------------------------------------- Résolution d’une combinaison par l’ordinateur Nous nous apercevons que l’ordinateur trouve en un essai de moins et aurait pu trouver en quatre coups s’il avait eut plus de chance lors du quatrième essai (1 chance sur 2). Quoiqu’il en soit, l’ordinateur a trouvé notre combinaison avec succès. ExtensionsNous avons apporté quelques améliorations à notre programme afin d’augmenter ses fonctionnalités. Tout d’abord, nous avons ajouté une limite au nombre de tours à jouer maximum. Comme dans les vrais Master-Minds, les joueurs doivent trouver en moins d’un certains nombre de essais. Nous avons fixé la limite à 8. Celle-ci peut être modifiée en changeant la valeur dans la classe Constante. Grâce à la généralisation et à la conception par héritage, nous avons la possibilité de faire jouer un ordinateur contre un autre ou bien un humain contre un autre humain. ConclusionLe projet était intéressant grâce au fait d’être totalement libre de concevoir du début à la fin l’architecture complète du programme. Cela nous a ainsi incités à réfléchir sur les différentes manières de concevoir le problème afin d’élaborer au mieux l’organisation des classes, packages et méthodes à utiliser. Nous avons utilisé des méthodes qui n’ont pas encore été vu en cours comme l’héritage ou la conception via un diagramme UML. Cela nous a facilités grandement la tâche pour la suite du développement. Le plus difficile pour nous a été de réaliser la seconde partie avec la résolution du système algorithmiquement. Le duo mathématicien (Loïc) et informaticien (Olivier) que nous formions nous as permis de surmonter ce problème et aussi de partager nos connaissances dans nos différentes spécialités. Comme amélioration complémentaire nous avions pensé mettre une interface graphique en utilisant un MVC, mais les consignes au sujet des extensions n’étaient pas très claires et par conséquent nous avons limité les développements supplémentaires afin de coller au mieux au cahier des charges fournis. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
similaire:
 | «description d’évènements». Mais la thématique de la ville et de l’architecture s’inscrirait également dans le programme culturel... | | «histoire des arts» de leur programme disciplinaire. Toujours connecté aux autres disciplines, l’enseignement de l’histoire des arts... |
| | «L’assesseur de collège Godnieff, principal du collège d’E est admis à faire valoir ses droits à la retraite.» Plus loin, on lisait... | |
| «travail considéré comme féminin», qui modifie simultanément les rapports sociaux de sexe, de “race” et de classe |  | |
| | «Va-pas-trop-vite» : 80 ans déjà ! Construit au chantier Bouché de Pornic au milieu des années trente, ce crevettier traditionnel... | |
| «inclusion» Dans l’ash du 6 septembre dernier, on trouve un article intitulé «La France à la recherche d’un modèle de désinstitutionalisation»... | | «Pourrez~vous former un plan de travail ?» Un large extrait de cette lettre d'Alain est cité dans la «Note de l'éditeur» qui se trouve... |