Jeu de dames

Projet d’Algorithmique et Programmation

Revue Finale

Trystan CHARTON – Maxence MOHR – Julien OLLAGNON

Introduction

• Jeu de plateau à deux joueurs : Noirs VS Blancs• Appelé aussi checkers ou jeu de dames

internationales.• Règles imposées : Celles de la FFJDObjectifs :• Appliquer nos connaissances en C et

Algorithmique• Mode humain VS humain et humain VS IA

Trystan CHARTON – Maxence MOHR – Julien OLLAGNON

Plan de cet exposé

1. Analyse du sujet et boucles– Structures de données– Boucle « recherche coup »– Boucle « joue rafle »– Joueur IA

2. Réalisation et Bilan– Difficultés rencontrées– Bilan

Trystan CHARTON – Maxence MOHR – Julien OLLAGNON

Partie 1 : Analyse et boucles

Trystan CHARTON – Maxence MOHR – Julien OLLAGNON

Partie 1 - Analyse du sujet

• Boucle principale : gère le jeu de façon générale

• Boucle affichage : affiche le damier• Boucle recherche coup : chercher les coups

possibles• Boucle joue rafle : joue la rafle et déplace le

pion.• Mode IA : Plusieurs niveaux de difficultés

Trystan CHARTON – Maxence MOHR – Julien OLLAGNON

Partie 1 – Structures de données

Trystan CHARTON – Maxence MOHR – Julien OLLAGNON

Partie 1 - Principe de la fonction « recherche coup »

Trystan CHARTON – Maxence MOHR – Julien OLLAGNON

Partie 1 - Principe de la fonction « joue rafle »

Trystan CHARTON – Maxence MOHR – Julien OLLAGNON

Partie 1 - Le mode IA

• 3 difficultés liées à la profondeur du MiniMax :– Difficulté 1 Profondeur = 3– Difficulté 2 Profondeur = 5– Difficulté 3 Profondeur = 7

• MiniMax :-> Voit plusieurs coups en avance, en prenant en compte le joueur adverse.

Principe ici pour trois rafles à l’avance: 1. l’ordinateur essaye de maximiser ses gains2. Le joueur humain minimise les gains de l’IA3. L’ordinateur maximise à nouveau ses gains

Trystan CHARTON – Maxence MOHR – Julien OLLAGNON

Partie 1 - Le mode IA : le MiniMaxint minimax (damier, joueur, profondeur, Nœud N, coordonnées coord_sauvées) Val1=INT_MINSi profondeur > 0

Si(nœud = MAX)Cherche des coups possibles de l’IAPour chaque coup possible

Copie du tableau de jeu (copie_damier)L’IA joue dans la case possible (rafle entière) val = minimax(copie_damier, joueur, profondeur -1, MIN)Si val > val1Val1=val Coor_sauvées = Coord_actuelles

Si(nœud = MIN)Cherche des coups possibles de l’humainPour chaque coup possible

Copie du tableau de jeu (copie_damier)L’IA joue pour l’humain dans la case possible (rafle entière))val = minimax(copie_damier, joueur, profondeur -1, MAX)Si val < val1Val1=valCoor_sauvées = Coord_actuelles

ElseReturn eval(damier)

Trystan CHARTON – Maxence MOHR – Julien OLLAGNON

Partie 1 - Le mode IA : évaluation pions

Trystan CHARTON – Maxence MOHR – Julien OLLAGNON

Partie 1 - Le mode IA : évaluation dames

Trystan CHARTON – Maxence MOHR – Julien OLLAGNON

Partie 1 - Le mode IA : évaluation nombre dames

Pour tout le damierSi l’IA a une dame

score += 250Si l’humain a une dame

score -=300

Ceci permet d’éviter d’offrir la possibilité à l’humain d’avoir des dames, tout en valorisant un plateau si l’IA a des dames

Trystan CHARTON – Maxence MOHR – Julien OLLAGNON

Partie 2 : La réalisation et bilan

Trystan CHARTON – Maxence MOHR – Julien OLLAGNON

Partie 2 - Difficultés rencontrées

1. Listes & structures de données2. Débogage3. Activités extérieures (temps de « coupure »)4. MiniMax5. Cas d’égalité6. Dames7. Niveau de programmation de chacun :

groupe hétérogène

Trystan CHARTON – Maxence MOHR – Julien OLLAGNON

Partie 2 - Bilan du projet

• Analyse : OK• Boucle Principale : OK• Boucle Affichage : OK• Boucle Recherche Coup : OK, mais a du être

débuggée• Boucle Joue rafle : OK, mais a du être débuggée• Boucle MiniMax : En cours de tests

Trystan CHARTON – Maxence MOHR – Julien OLLAGNON

Conclusion

• Applications de nos connaissances sur un cas complet et intéressant

• Jeu agréable et facile à comprendre que nous apprécions

• Non terminé : Le MiniMax reste à tester correctement

• Le travail à plusieurs est très intéressant, nous avons appris à travailler (points de vue différents)

• Beaucoup de plaisir à le coder, et à y jouer !!

Trystan CHARTON – Maxence MOHR – Julien OLLAGNON

Références et logiciels utilisés

• Références :Fédération Française d’Othello

http://www.ffjd.fr

• Logiciels utilisés :Codeblocks/Notepad++ pour la programmationGCC via Cygwin/MinGW pour la compilationMicrosoft Word 2013 pour le rapportMicrosoft Powerpoint 2013 pour cette présentationMicrosoft Visio Pro 2013 pour les schémasThe GIMP et MS Paint pour les images

Trystan CHARTON – Maxence MOHR – Julien OLLAGNON

Merci de votre écoute

Trystan CHARTON – Maxence MOHR – Julien OLLAGNON

Démonstration

Ouvrir le dossier source du jeuInvite de commande

Rapport Final (PDF)

Démonstration :

Rapports :

Trystan CHARTON – Maxence MOHR – Julien OLLAGNON