Projet Démineur (ou Minesweeper)
Jeu du démineur
Le jeu de démineur est un jeu de réflexion dont la version la plus connue est celle distribuée par Microsoft sur le système Windows. Dans sa forme classique, le jeu se compose d'une grille contenant des cellules cachées. Ces cellules sont de deux types : minées ou non. Le nombre total de cellules minées est connu. Le joueur perd si il découvre une cellule minée. Les cellules non-minées, une fois découvertes par le joueur, indiquent le nombre de cellules minées dans leur voisinage. Le voisinage d'une cellule correspond aux cellules qui lui sont adjacentes. Noter que la grille du démineur est un graphe dont les sommets, correspondent aux cellules. Dans le cas de la grille, ces sommets sont de degré 8, 5 ou 3 selon leur position, mais on peut jouer au démineur sur un graphe arbitraire qui n'est pas forcément une grille.
Description du projet
_Le but de ce projet est de proposer différentes stratégies permettant à une machine de jouer au démineur sur un graphe donné en entrée, comportant un sous-ensemble de cellules cachées. Une stratégie peut se définir comme une collection d'algorithmes déterministes ou non-déterministes permettant d'augmenter le nombre de cellules découvertes du graphe, en évitant de révéler des cellules minées. Voici un exemple pour chacune de ces catégories :
- Déterministe : Révéler récursivement les sommets adjacents à un sommet donné indiquant 0.
- Non-déterministe : Si aucun sommet n'est révélé, en révéler un aléatoirement.
- La lecture d'un graphe en entrée représentant le plateau de jeu. On pourra utiliser un fichier texte où chaque ligne correspond à une arête définie par ces extrémités (id1 id2), ou encore une version simplifiée du langage DOT utilisé par la commande dot.
- Le placement aléatoire de k mines sur le graphe.
- La gestion de l'action "révéler un sommet", avec les différentes terminaisons possibles.
- Un (ou plusieurs) algorithme(s) permettant de déterminer l'ensemble des coups sûrs.
- Dans le cas où on ne dispose pas de coups sûrs, un (ou plusieurs) algorithme(s) permettant de déterminer l'ensemble des coups les moins risqués, pour une notion de risque bien définie (aléatoire, espérance de gain ...)
- Développer un programme pouvant jouer plusieurs parties automatiquement et récupérer différentes statistiques : nombre de victoires, nombre de défaites, temps de calcul etc. Afin de pouvoir comparer différentes stratégies empiriquement.
- L'étude de certaines familles de graphes (arbres, grilles 3xN, 4xN, ...) où des contraintes différentes peuvent apparaître.
Recommandations
_Pour l'ensemble du projet, il est recommandé de systématiquement :
- Définir formellement les éléments nécessaires pour représenter le jeu, et les relier à leur implémentation.
- Définir formellement les algorithmes proposés, et étudier leur complexité (temps/mémoire). Il est aussi possible de définir une méthode empirique permettant de comparer les différentes algorithmes sur un ensemble de graphes tests.
Remarques :
- Le fichier suivant contient une liste de recommandations explicites pour la réalisation de la partie algorithmique du projet. En particulier, vos propos seront illustrés d'exemples dessinés et commentés. Le rapport sera rédigé à l'aide de Latex. Les dessins pourront être réalisés à l'aide de bibliothèques pour LaTeX (comme pstricks ou tikz), ou de logiciels de dessin (comme xfig).
- Le fichier suivant contient une liste de standards de codage sur le langage Lisp, une lecture saine avant de commencer à coder dans ce langage.
- Une stratégie efficace (qui gère beaucoup de configurations différentes) devrait pouvoir l'être sur ces différents types de graphe. Notons que la stratégie à adopter peut être évidente dans certains cas (dans celui des cliques par exemple).
- Si l'on restreint ses algorithmes (à une famille de graphes donnée, à des configurations possibles ...), il est impératif d'expliquer en quoi les restrictions sont intéressantes à étudier. Par exemple, si on se restreint à une famille de graphes que sont les cycles, la restriction peut être considérée comme trop forte.