Les mathématiques cachées derrière le démineur
Le démineur a l'air d'un jeu simple. Et pourtant, il cache des problèmes mathématiques fascinants qui occupent les chercheurs depuis des décennies. De la théorie de la complexité au calcul de probabilités, plongez dans les mathématiques qui se cachent derrière chaque clic.
Le démineur est NP-complet
En 2000, le mathématicien Richard Kaye a démontré que le problème de la consistance du démineur est NP-complet. Qu'est-ce que cela signifie concrètement ?
Un problème NP-complet est un problème pour lequel :
- Vérifier une solution proposée est facile (temps polynomial)
- Trouver la solution depuis zéro est potentiellement extrêmement long (temps exponentiel)
Appliqué au démineur : si quelqu'un vous montre où sont toutes les mines, vous pouvez vérifier facilement que cette configuration est compatible avec les chiffres affichés. Mais déterminer si une configuration existe (si la grille est résoluble) est un problème fondamentalement difficile.
Le démineur appartient à la même famille de difficulté que le problème du voyageur de commerce ou la satisfaisabilité booléenne. Un simple jeu Windows qui cache un des problèmes les plus profonds de l'informatique théorique !
Le calcul de probabilités au démineur
Quand la logique pure ne suffit plus (le fameux 50/50), les mathématiques prennent le relais. Calculer la probabilité qu'une case donnée contienne une mine est essentiel pour prendre la meilleure décision possible.
Probabilité naïve vs probabilité réelle
L'approche naïve consisterait à dire : s'il reste 20 mines pour 80 cases inconnues, chaque case a 25% de chances d'être une mine. Mais c'est faux dès qu'on tient compte des contraintes locales.
En réalité, chaque chiffre affiché sur la grille impose une contrainte sur ses voisines. Ces contraintes créent des probabilités très inégales : certaines cases à 5%, d'autres à 80%, même si la moyenne globale est à 25%. On retrouve ce même type de raisonnement probabiliste dans d'autres jeux, comme la bataille navale et son analyse probabiliste des tirs. C'est pourquoi les bons joueurs ne devinent pas « au hasard » - ils évaluent intuitivement ces probabilités. Cela fait partie des techniques avancées du jeu.
Le calcul exact
Pour calculer la probabilité exacte qu'une case soit minée, il faut :
- Énumérer toutes les configurations valides de mines le long de la frontière
- Pour chaque configuration, calculer le nombre de manières de placer les mines restantes dans les cases intérieures (non adjacentes à la frontière)
- Compter dans combien de ces configurations la case considérée est minée
Ce calcul fait intervenir des coefficients binomiaux (combinaisons) et peut devenir très lourd. Les solveurs informatiques le font en quelques millisecondes, mais un humain ne peut qu'en faire une approximation intuitive.
La théorie des contraintes appliquée
Chaque case numérotée du démineur définit une contrainte : la somme des mines dans son voisinage égale son chiffre. L'ensemble de ces contraintes forme un système que les mathématiciens appellent un problème de satisfaction de contraintes (CSP).
Les techniques utilisées pour résoudre les CSP se retrouvent dans de nombreux domaines : planification d'emplois du temps, allocation de fréquences radio, coloration de graphes, compilation de code... Jouer au démineur, c'est résoudre un CSP à la main.
Propagation de contraintes
La technique de base pour résoudre un CSP est la propagation : quand vous déduisez qu'une case est une mine, cette information modifie les contraintes de toutes les cases numérotées voisines. Ces nouvelles contraintes peuvent à leur tour révéler d'autres mines ou cases sûres, en cascade.
C'est exactement ce que vous faites quand vous jouez : saturation → complétion → réduction → nouvelle saturation... Cette cascade de déductions est de la propagation de contraintes en action.
Les solveurs de démineur
Plusieurs algorithmes ont été développés pour résoudre automatiquement le démineur :
- Solveur par règles simples : applique saturation et complétion. Résout ~30% des situations en Expert
- Solveur par soustraction : ajoute la réduction entre contraintes voisines. Résout ~60% des situations
- Solveur par énumération : teste toutes les configurations possibles de la frontière. Résout ~90% des situations déterministes
- Solveur probabiliste : quand la logique ne suffit pas, calcule les probabilités exactes et choisit la case la plus sûre. Maximise le taux de victoire (~35% en Expert)
Un humain expert se situe généralement entre le solveur par soustraction et le solveur par énumération - avec en plus une bonne intuition probabiliste.
Les nombres de la grille : quelques statistiques
Voici des chiffres intéressants sur les grilles du démineur, calculés par simulation :
- En Expert (99 mines, 480 cases), une case aléatoire a 20,6% de chances d'être minée
- Le chiffre le plus fréquent est « 1 » (~35% des cases révélées), suivi de « 2 » (~25%)
- Les « 5 », « 6 », « 7 » et « 8 » sont extrêmement rares. Un « 8 » (toutes les voisines sont minées) est quasi impossible en mode standard
- Le premier clic révèle en moyenne 15 à 25 cases au centre d'une grille Expert
- Environ 10 à 15% des grilles Expert sont résolubles uniquement par la logique (sans aucun guess) - une question de solubilité qu'on retrouve aussi dans l'analyse probabiliste du solitaire
Le lien avec l'intelligence artificielle
Le démineur est un terrain de jeu pour les chercheurs en IA. Il combine information partielle (vous ne voyez pas toutes les mines), raisonnement logique et prise de décision sous incertitude - trois défis majeurs de l'IA.
Des approches variées ont été testées : réseaux de neurones, apprentissage par renforcement, algorithmes génétiques... Mais à ce jour, les meilleurs solveurs restent les algorithmes de satisfaction de contraintes classiques, combinés au calcul probabiliste. L'IA n'a pas encore surpassé la bonne vieille logique mathématique pour ce problème.
Pourquoi tout cela compte pour vous
Comprendre les mathématiques derrière le démineur ne vous rendra pas forcément meilleur du jour au lendemain. Mais cela vous aidera à :
- Accepter que certaines parties sont mathématiquement impossibles à gagner sans chance
- Faire de meilleurs choix quand vous devez deviner (choisir la case la moins probable d'être minée)
- Apprécier la profondeur insoupçonnée de ce jeu que vous pensiez connaître
Pour en savoir plus sur l'histoire fascinante du démineur, découvrez notre article dédié.