Available nodes

 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, comme par exemple sur un pavage hexagonal.

 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.

Un algorithme procède à partir d'une configuration donnée, à savoir un graphe étiqueté avec diverses informations : les sommets déjà révélés, le nombre de mines adjacentes à chacun, les sommets marqués comme minés, etc.... A partir de cette configuration, il choisit une case à révéler et (s'il survit à cette case) produit une nouvelle configuration.

On propose ainsi de réaliser le projet en deux temps : d'abord en créant un programme permettant d'aider le joueur humain bloqué dans une certaine configuration en lui proposant le meilleur choix, puis en laissant le programme jouer des parties tout seul.

Un découpage des objectifs pour ce projet serait donc :
  1. Lecture d'un graphe en entrée représentant le plateau de jeu

    Le format suivant pour les graphes peut facilement être utilisé et partagé entre les équipes, et utilisé avec une fonction du style file->value :
    (4 (0 (1 2)) (1 (0 3)) (2 (0 3)) (3 (1 2)))
    
    Le premier chiffre représente le nombre de sommets, le reste de la liste étant une liste d'associations qui à chaque numéro de sommet associe la liste de ses voisins.
  2. Création d'un type abstrait de données graph.

    Le style d'écriture de ce TAD reprennent les formes de description vues en PG116. Le choix des fonctions à implémenter est laissé libre. Le sujet laisse la possibilité d'utiliser Typed Racket.
  3. Placer aléatoirement des mines sur le graphe.

    Il sera certainement nécessaire de calculer pour chaque sommet le nombre de mines sur ses voisins.
  4. Révéler un sommet du graphe.

    Cette transformation devra gérer les différentes terminaisons possibles (explosion et fin de jeu, révélation récursive des voisins si pas de mine alentour).
  5. Déterminer l'ensemble des coups sûrs.

  6. Choisir un coup de manière non déterministe.

    Dans le cas où on ne dispose pas de coups sûrs, il est demandé de programmer 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 ...).
Au delà de cette base de code, les évolutions possibles pour le programme sont multiples.
  • Ainsi, il est envisageable de proposer une visualisation des différents algorithmes sous la forme d'une interface graphique. Il est possible de s'inspirer de l'implémentation du Chat Noir pour voir comment réaliser une telle interface directement avec les bibliothèques du langage. Le code (en literate programming) est accessible depuis le github de racket, mais aussi ici.
  • Ensuite, une autre option consiste à jouer sur différentes familles de pavages, comme les pavages archimédiens, en se limitant dans un premier temps aux pavages uniformes (carrés, hexagones, triangles). Alternativement, une extension propose de jouer sur certaines familles de graphes (arbres, grilles 3xN, 4xN, ...) où des contraintes différentes peuvent apparaître, le choix de ces familles devant être motivées.
  • Enfin, il est envisageable de développer un programme pouvant jouer des parties automatiquement afin de récupérer différentes statistiques : nombre de victoires, nombre de défaites, temps de calcul, ... ceci afin de pouvoir comparer différentes stratégies empiriquement.

 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 :
  • Une stratégie efficace (qui gère beaucoup de configurations différentes) devrait pouvoir l'être sur ces différents types de graphes. Notons que la stratégie à adopter peut être évidente dans certains cas (dans celui des cliques ou des arbres 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.