Démineur (jeu)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Démineur.

Le démineur est un jeu de réflexion dont le but est de localiser des mines cachées dans un champ virtuel avec pour seule indication le nombre de mines dans les zones adjacentes.

De nombreuses versions gratuites existent, mais la plus connue est celle fournie avec Microsoft Windows. Cette version particulière, à défaut d'inventer le concept, l'a popularisé, et la désignation Démineur identifie souvent cette version précise et non le principe général du jeu.

Les graphismes du jeu sous Windows n'ont guère évolué entre la version sur Windows 3.0 et celle sur Windows XP ; néanmoins on constate que sous Windows Vista et sous Windows 7 les graphismes ont été améliorés. À partir de Windows 8, le démineur n'est plus fourni avec Microsoft Windows. Il passe sous la forme d'une application Xbox appelée Microsoft Minesweeper à télécharger sur le Windows Store. Il acquiert dès lors de nouveaux graphismes (un mode moderne et un autre mode jardin), un mode aventure et des récompenses à gagner avec un compte Xbox Live.

Par défaut le jeu se joue avec la souris, mais il peut également aujourd'hui se jouer sur un écran tactile.

Système de jeu[modifier | modifier le code]

Le champ de mines est représenté par une grille, qui peut avoir différentes formes : deux ou trois dimensions, pavage rectangulaire ou non, etc.

Chaque case de la grille peut soit cacher une mine, soit être vide. Le but du jeu est de découvrir toutes les cases libres sans faire exploser les mines, c'est-à-dire sans cliquer sur les cases qui les dissimulent.

Lorsque le joueur clique sur une case libre comportant au moins une mine dans l'une de ses cases avoisinantes, un chiffre apparaît, indiquant ce nombre de mines. Si en revanche toutes les cases adjacentes sont vides, une case vide est affichée et la même opération est répétée sur ces cases, et ce jusqu'à ce que la zone vide soit entièrement délimitée par des chiffres. En comparant les différentes informations récoltées, le joueur peut ainsi progresser dans le déminage du terrain. S'il se trompe et clique sur une mine, il a perdu.

On peut signaler les cases contenant des mines présumées par un drapeau en cliquant sur le bouton droit de la souris — mais ce n'est aucunement obligatoire. Il faut faire attention à ne pas signaler une case saine par un drapeau, car cela peut induire en erreur ; ce n'est toutefois pas aussi pénalisant que de découvrir une mine.

Dans le démineur de Windows, il est possible de cliquer simultanément avec les boutons gauche et droit de la souris sur une case. Cette manipulation est à faire sur une case ayant un numéro (donc avec une ou plusieurs mines à proximité) et lorsque le joueur a préalablement déminé le nombre requis de mines alentour. Dans ce cas là, toutes les autres cases adjacentes dépourvues de drapeau seront découvertes. Pratique pour gagner du temps.

Le jeu est chronométré, ce qui permet de conserver les meilleurs scores.

Jusqu'à Windows XP, le démineur de Windows contenait également un smiley prenant différentes humeurs selon la situation : souriant en temps normal, triste lorsque le joueur a perdu, portant des lunettes de soleil lorsqu'il a gagné et nerveux lorsque le bouton de la souris est enfoncé. Un clic sur ce smiley permettait de commencer une nouvelle partie[1].

Logique ou hasard ?[modifier | modifier le code]

Le jeu du démineur est un problème NP-complet[2], il invite cependant le joueur à combiner plusieurs tactiques, selon le degré de probabilité. On peut avoir des certitudes absolues selon le nombre d'informations qui s'entrecoupent ; mais on peut aussi n'en avoir absolument aucune, notamment lors des premiers coups où l'on est obligé de procéder à l'aveuglette ; enfin, on peut, sans avoir de certitude absolue, calculer de fortes probabilités. Il s'agit donc alternativement d'un jeu de hasard et d'un casse-tête.

Certaines variantes cherchent à diminuer la part du hasard. Les plus simples offrent une option dans laquelle certaines cases connues du joueur, typiquement les coins, sont toujours sûres. Les plus sophistiquées jouent elles-mêmes en cas de situation où l'on ne peut pas trancher. Une variante particulière a poussé ce dernier procédé dans ses limites : en demandant au joueur de jouer une case ou bien de déclarer explicitement qu'il croit ne pas pouvoir décider, elle rend chaque coup possible dans un espace mathématique étendu.

Mesure de difficulté[modifier | modifier le code]

La difficulté d'une grille de démineur peut être mesurée avec un indice : le 3BV (abréviation de Bechtel's Board Benchmark Value).

Variantes[modifier | modifier le code]

Le démineur existait avant Windows, et a été exploité une fois bien connu du grand public sur de nombreuses plateformes (Macintosh, Linux...). Il existe également comme extension des navigateurs de la famille Mozilla. Dans la version Mozilla, il existe également un pavage hexagonal.

Des variantes plus exotiques existent qui proposent des variations de la structure du jeu avec par exemple des plateaux de jeu non plans, plusieurs mines par case, l'intégration d'une levée des indécidables, ou bien du déroulement du jeu avec par exemple des parties en temps limité. Certains programmes offrent aussi des facilités pour le jeu à plusieurs joueurs, comme la certification des résultats en vue de l'établissement de classements, et des statistiques sur de nombreux aspects du jeu, comme sa difficulté théorique compte tenu de la distribution des mines.

Cliquez sur une vignette pour l’agrandir

Algorithmes[modifier | modifier le code]

Dans cette section, nous allons considérer un tableau de démineur de largeur m, de hauteur n, et comportant x mines.

Placement des mines[modifier | modifier le code]

Pour pouvoir placer des mines aléatoirement, il faut avoir accès à un générateur de hasard. Puis on lui demande un nombre compris entre 1 et n, ce sera le numéro de la ligne, et un second nombre compris entre 1 et m, ce sera le numéro de colonne. Ensuite on regarde si la case ainsi choisie comporte déjà une mine, auquel cas on ne fait rien et sinon on y place une mine. On effectue ce schéma jusqu'à ce qu'on ait placé x mines.

L'algorithme mentionné ci-dessus peut poser des problèmes de temps de calcul si on a une grille assez pleine voire très pleine. Si par exemple on décide de jouer sur une grille de dimension 20X20 et qu'on veut y mettre 361 bombes. Quand on aura déjà placé 360 bombes et qu'on débutera l'algorithme pour placer la dernière, il y a de fortes chances (90 %) que la case tirée au hasard soit déjà occupée par une bombe et qu'on doive refaire le tirage au sort de nombreuses fois. Pour corriger ce problème on peut modifier un peu l'algorithme de placement de bombes pour les cas où il y a plus de bombes que de cases vides : on peut placer une bombe partout et ensuite tirer au hasard les emplacements des cases vides.

On peut également procéder comme au loto : numéroter les cases de 1 à 400 (pour le cas d'une grille 20X20) tirer au hasard une case et ensuite sortir cette case des possibilités pour ensuite tirer la case suivante parmi les 399 cases restantes. Cet algorithme nécessite une structure de données plus complexe mais la complexité algorithmique O(n) de chaque tirage au sort est indépendant du nombre de bombes déjà posées et vaut O(1).

Calcul du nombre de mines de chaque case[modifier | modifier le code]

Il existe deux grands algorithmes (au sens où ce sont les plus utilisés) permettant le calcul des nombres des différentes cases du démineur.

Par case[modifier | modifier le code]

Le premier algorithme est dit naïf : c'est la méthode la plus évidente à comprendre et à mettre en place, mais ce n'est pas la plus optimisée.

Après le placement des mines, l'algorithme parcourt le tableau en entier, case par case. Pour chacune d'entre elles, il compte le nombre de mines dans le voisinage direct, et lui assigne ce nombre. Voici une implémentation simplifiée en pseudo-code :

explorer tableau par case
    si case est vide
        nombre := compter_mines( case.voisinage )
        case.valeur = nombre

Nous aurons donc une complexité algorithmique de O( m \times n ).

Par mine[modifier | modifier le code]

Alors que le premier algorithme s'effectue dans un deuxième temps, celui s'applique au moment-même du placement des mines sur le tableau.

L'algorithme fonctionne en considérant les mines et leur voisinage comme des ensembles. Lorsqu'une case est incluse dans un de ses ensembles, le nombre qui lui est associé est incrémenté de un. Ainsi, en pseudo-code :

// Placement de la mine

explorer mine.voisinage par case
    si case est vide
        incrémenter case.valeur

Cette approche du problème permet de réunir deux étapes en une seule. En termes de complexité, algorithmique, cet algorithme est plus performant : O( x ), sachant que x < (m \times n)- 1, car le tableau ne peut ni être recouvert de mines, ni contenir plus de mines que de cases (exception faite des variantes avec plusieurs mines par case).

Astuce[modifier | modifier le code]

Dans la version Windows du démineur, en tapant, durant le jeu "xyzzy", puis "entrée" et enfin "majuscule", le pixel du coin supérieur gauche de l'écran (écran windows, et non pas la fenêtre de jeu) devient noir lorsque le curseur passe sur une mine, et blanc lorsqu'il passe sur une case libre.

Parodies[modifier | modifier le code]

Le jeu est parodié par l'équipe de CollegeHumor dans un sketch prenant la forme d'une fausse bande-annonce pour un film intitulé Minesweeper: The Movie[3].

Références[modifier | modifier le code]

Sur les autres projets Wikimedia :

  1. (en) Lissa Wiebers, « Navigating Minesweeper », SmartComputing, vol. 4, no 3,‎ mars 1996.
  2. (en) http://www.cs.toronto.edu/~cvs/minesweeper/minesweeper.pdf
  3. (en) Minesweeper: The Movie, sur CollegeHumor, 6 août 2007.