Les meilleurs développeurs C++ freelances sont sur Codeur.com

Developpement C++ sur codeblocks

 Fermé·Moins de 500 €·1 offre·1037 vues·3 interactions


Jeu de base
Implémenter le jeu de base en suivant les instructions suivantes :
• L’Othellier est une matrice de 8x8 cases
• Possibilité de sauvegarder une partie et de la charger
• Les coups doivent être légitime (blindage obligatoire de tous les cas possibles)
• Score en fin de partie
• Plateau représenté en console avec des couleurs obligatoires !
• Pas de saisie des coups, on se déplace à l’aide du clavier (utilisez les touches z, q, s, d) sur le
damier (blinder les bords !) et on joue son coup en appuyant sur la touche Entrée.
A noter que dans cette partie, il n’y a pas de Théorie des Graphes ! Il s’agit simplement de la mise en
place du jeu de base et de ses règles.
N'oubliez pas de tester votre jeu entre deux joueurs humains.
Ne passer pas trop de temps sur cette partie (qui n'a rien à voir avec la Théorie des Graphes !). Une
classe ou 2 suffisent par exemple pour gérer le jeu en entier. Inutile aussi de faire de l'héritage et du
polymorphisme sauf si vous savez ce que vous faites :)
Niveau 1 – Débutant (8 points)
Voici le premier niveau de difficulté proposé. Ce niveau est accessible pour tout le monde.
Un peu de vocabulaire qui sera valable pour l'ensemble du projet :
• Noeud : Correspond à un état donné du jeu à un instant t. Dans le cas de l’Othello, il s'agit de
la position des pions
• Transition : Action permettant de passer d'un état à un autre. Dans le cas de l’Othello, il
s'agit d’un coup (Noir ou Blanc)
• Graphe : Ensemble de noeuds reliés par des arcs. Un arc représente une transition d'un état
à un autre. Un graphe peut posséder des cycles.
• Graphe d’état : Arbre montrant les différents nœuds à un instant donné. Un exemple est
fourni sur le site de M Fercoq : [URL visible pour les membres Pro]
Projet Théorie des graphes - ING2 2017
Florent DIEDLER - CodeAnalysis SASU Page 8
Dans le cas de l’Othello, le graphe d’état montre les différentes positions des pions sur le
plateau de jeu. Chaque coup joué créé une nouvelle position et donc un nouvel état.
• Arbre de recherche : Ensemble des états accessibles en partant de l’état actuel. Dans le jeu
de l’Othello, la création d’un nouvel état se fait lorsque l’on pose un pion.
Travail à réaliser :
1. Implémenter un premier algorithme naïf permettant à un joueur de jouer contre l’ordinateur.
L’ordinateur jouera aléatoirement tout en respectant les règles du jeu.
2. Modéliser les possibilités de coup de l’ordinateur par un arbre (un arbre est un graphe sans
cycle) qui sera affiché en temps réel dans la console. A vous de trouver comment représenter
le plus lisiblement possible cet arbre.
Projet Théorie des graphes - ING2 2017
Florent DIEDLER - CodeAnalysis SASU Page 9
Niveau 2 – Intermédiaire (8 points)
Vous verrez que l’algorithme précédent est loin d’être satisfaisant. En effet, l’IA n’a aucune stratégie
et n’a aucun moyen d’évaluer une position donnée pour savoir si elle est entrain de gagner ou de
perdre. Le fait de dire que telle ou telle position est « mieux qu’un autre » peut être évalué par une
heuristique. Une heuristique est une fonction mathématiques qui calcul un coût pour un nœud
donné.
Plus l’heuristique sera précise et plus l’IA sera forte car évaluera mieux une position donnée.
1. Proposer une heuristique dans le cas de l’Othello pour évaluer une position donnée. Justifiez
votre choix dans le rapport.
2. Implémenter une IA niveau intermédiaire utilisant l’heuristique choisie à la question
précédente. Pour cela, implémenter l’algorithme Min-Max très bien expliqué sur Internet… et
fixer la profondeur de recherche à 5 coups.
3. Proposer une solution élégante permettant de visualiser sur la console l’arbre de recherche
(ou arbre des possibilités) ainsi que les coûts de chaque nœud.
4. Fixer maintenant une profondeur de recherche à 30 coups. Qu’observez-vous ? Quelle est la
profondeur de recherche maximale possible pour le cas de l’Othello ? Justifiez dans le rapport.
Projet Théorie des graphes - ING2 2017
Florent DIEDLER - CodeAnalysis SASU Page 10
Niveau 3 – Avancé (2 points)
Ce niveau doit être abordés uniquement pour les meilleurs et ceux qui veulent prétendre au 19 ou
20. Vous devez au préalable avoir fait les niveaux 1 et 2 avant de vous attaquer au niveau 3.
Vous verrez que l’algorithme précédent n’est toujours pas suffisant. Le problème principal de
l’algorithme Min-Max est son temps de calcul qui peut être très long surtout si la profondeur de
recherche est élevée.
1. Implémenter l’algorithme Alpha-Beta permettant d’améliorer le Min-Max. Fixer la
profondeur de recherche à 5 coups et comparer vos résultats avec l’algorithme Min-Max.
2. Implémenter l’algorithme NegaMax permettant d’améliorer Alpha-Beta. Fixer la profondeur
de recherche à 5 coups et comparer vos résultats avec l’algorithme Alpha-Beta.
3. Pour ceux qui s’ennuient, optimisez vos algorithmes afin de permettre de fixer la profondeur
de recherche à 20 coups ou plus…
Vous pouvez aussi modifier votre heuristique de la partie précédente afin d'en trouver une plus
puissante...
Arriverez-vous à créer une IA imbattable pour ce jeu ? Le jeu en vaut la chandelle... Bon courage !

Projet_Théorie_des_graphes_v2_2.pdf

Budget indicatif : Moins de 500 €

Publication : 21 avril 2017 à 14h54

Profils recherchés : Développeur C++ freelance

Le profil du client est reservé aux prestataires abonnés

Créer un compte

Chaque jour, des centaines de clients utilisent Codeur.com pour trouver un prestataire. Créez votre compte dès maintenant, remplissez votre profil et trouvez de nouveaux clients.

Trouver des nouveaux clients

Votre navigateur Web n’est plus à jour. Il ne permet pas d’afficher correctement le site Codeur.com.
Nous vous invitons à mettre à jour votre navigateur ou à utiliser un autre navigateur plus récent.