Sommaire :

Une situation délicate
Démineur : question de logique ou de probabilités ?
Une tactique pour finir
Probabilités
Résoudre les probabilités discordantes
Compter les dispositions possibles
Compter les mines manquantes
Solution du problème
Et on joue !

Une situation délicate

Dans cette situation, on connaît un certain nombre de mines sur les 3 champs restants, mais on ne peut pas savoir où elles sont. Il y a peu de mines qui sont dans des positions 50%-50% (rouge ou bleu), un groupe de mines qui peuvent être selon 2 arrangements différents avec 2 ou 3 mines (vert), et un schéma plus compliqué en haut à gauche que je n'ai pas marqué, et qui comprend le et le .

 

Démineur : question de logique ou de probabilités ?

On peut jouer au Démineur de deux façons : comme un jeu de logique ou comme un jeu de probabilités.

En fait, la logique est incluse dans les probabilités... Si on peut prouver qu'une mine est à tel endroit, cela signifie que la probabilité qu'elle soit là est de 100% ; inversement lorsqu'on sait qu'une case est sans mine, la probabilité est de 0%. Les probabilités, c'est la seule chose nécessaire pour déminer, en quelque sorte. En pratique, surtout dans les grilles faciles de l'expert, on ne fait que des déductions pour résoudre les situations ou il y a ces 100% de probabilité. Cela suffit pour terminer une telle grille ; pas besoin de faire appel aux probabilités..

Mais il y a tant de situations où toutes les déductions du monde ne sont d'aucune aide. Le célèbre 'T', situation qui apparaît a au milieu en bas de la grille ci-dessus, en est un exemple tout simple - légèrement plus complexe en raison des mines supplémentaires juste à côté. (le vrai 'T' étant le même schéma mais en remplacant le par un , et le par un ).

Il n'y a aucun moyen d'obtenir plus de renseignements pour trouver la mine qui laisse ces 2 cases non découvertes... C'est du 50-50 - un pile ou face. Quand on tombe sur ce genre de situation, il vaut mieux faire un choix tout de suite, plutôt que de se garder ce truc pour la fin - si votre choix était le mauvais, vous n'aurez pas perdu le temps que vous auriez passé à déminer le reste de la grille. (Pour ma part, je suis un finisseur, c'est à dire que je garde pour la fin les situations comme ça, et du coup je ne m'en veux pas si je fais le mauvais choix. Et souvenez-vous que c'est une mauvaise conception du jeu qui vous fait jouer votre victoire sur un pile ou face...)

 

Une tactique pour finir

L'une des tactiques les plus faciles est de compter le nombre de mines restantes. Supposons que j'aie déminé toute la grille sauf ce coin en bas à droite. Les deux seules possibilités de configuration des mines sont celles-ci :

A	B

Dispositions de mines possibles

Si on arrive dans cette situation et que le compteur dit qu'il reste 2 mines, c'est gagné : ca ne peut être que le schéma B.

Si le compteur dit trois mines restantes, ce n'est pas forcément le schéma A. Ce pourrait être le schéma B avec la dernière mine dans le groupe de 3*3 cases dans le coin.

En fait, les probabilités sont en faveur du schéma B.

 

Probabilités locales

Si on étudie les probabilités "localement" (c'est à dire en excluant le reste de la grille), on peut voir que chacune des cases marquées en rose a 50% de chance d'être une mine. Si on a un a côté de deux cases non découvertes, chacune a 50% de chance d'être une mine.

En bas au milieu, c'est exactement le cas : chacune des cases a une probabilité de 50% d'être une mine.

Chaque ellipse rose couvre 1 mine... Il reste donc 7 mines

Le coin en bas à droite est une situation grosso modo du même type : chaque chiffre est face à une mine et une case sans mine.

Si il ne manquait qu'une mine à un chiffre qui avait 3 cases non découvertes autour de lui, chaque case aurait une probabilité de 33% d'être une mine ; pour 4 cases non découvertes autour de lui, ce serait 25%. S'il manquait 2 mines à un chiffre et 3 cases non-découvertes, chacune aurait une chance de 66% d'être une mine.

Voici les probabilités particulières pour la totalité de la grille :

Comme vous pouvez le voir, il y a certaines cases en haut à gauche qui ont plus d'une probabilité : la case non-découverte qui touche le et le , et celle entre le et le . (Celle qui touche le et le a quand même 66% de chance due aux 2 cases ; il n'y a donc pas d'incompatibilité apparente).

 

Résoudre les probabilités discordantes

A cet endroit, vous devriez vous demander ce que veut dire "probabilités discordantes". Ce qui doit vous éclairer, c'est que c'est la plus grande probabilité qui l'emporte. Par exemple, la case entre le et le est certainement de 66%. Ce qui signifie que la case à gauche du qu'on a calculée à 50%, est en fait à 33%. Ou bien on pourrait croire qu'on combine les probabilités, et atteindre 5/6, ou la moyenne...

Aucune de ces probabilités ne sont correctes... Les données desquelles les probabilités sont extraites ne sont pas indépendantes, donc les calculs sont faux. Le 50% du bas au centre est, quant à lui, correct, parce que c'est indépendant d'autre chose. Si on construisait de manière aléatoire des grilles qui remplissaient les conditions de probabilité indiquées ci-dessus, on obtiendrait exactement la moitié de grilles comportant une mine dans chacune des 2 possibilités. Les probabilités sont parfois sources de confusion chez les gens qui ont du mal à savoir quelle règle appliquer dans quelle situation. Cette méthode est valable, car elle est basée sur la définition de la probabilité en tant que statistique prédictive : mesure des différents arrangements qui auraient pu aboutir à la situation actuelle, considérant que ces possibilités sont équiprobables.

Ainsi, pour calculer correctement le schéma en haut à gauche, il faut envisager l'ensemble des dispositions de mines qui puissent correspondre aux données dont on dispose, ce qui permet de mesurer la probabilité de chacune des dispositions de comporter une mine dans la bonne position.

Cela prendrait trop de temps de tout faire de cette manière. Fort heureusement, il existe des méthodes plus performantes.

 

Compter les dispositions possibles

Une manière abstraite de calculer les probabilités est de faire le tour de toutes les dispositions de mines possibles, d'éliminer celles qui ne collent pas avec les données collectées, et de compter les statistiques pour chaque endroit.

Une méthode plus pratique est de ne considérer que celles qui ne seraient pas éliminées du tout. Pour cela, vous raisonnez logiquement, et vous reproduisez toutes les situations possibles qui pourraient correspondre aux données. J'ai déjà montré les deux possibilités pour le schéma en bas à droite ; voici les possibilités pour le coin en haut à gauche :

	A	B	C
1
2

Dispositions de mines possibles

(Comme précédemment, l'ovale rose indique que la mine peut être dans l'une ou l'autre position avec une probabilité équivalente. J'aurais dû représenter ces 2 cases séparément ; il y aurait eu du coup 10 possibilités, mais ça n'aurait pas eu un grand intérêt. Les deux lignes (1 et 2) sont individualisées par la mine de la 4e ligne. Les trois colonnes sont caractérisées par la position de la mine de la 2e ligne)

Maintenant, on pourrait dire "bah il y a que 5 cas possibles, donc on peut compter la probabilité, pour chaque position de mine". Par exemple, la mine de la 4e ligne (qui touche le ), est sur la gauche des deux cases dans la ligne 1 (du tableau), et sur la droite dans les trois cas de la ligne 2 (du tableau). On peut donc dire que cette mine a 60% de chance d'être sur la droite (3/5), à côté du . (C'est une case qui a des probabilités discordantes de 50% et 66%)

Cependant, c'est raisonner en oubliant un détail : le nombre de mines est différent dans chaque cas... Il y a 6 mines dans le A1, 4 dans le B2 et 5 dans les autres cas.

 

Compter les mines manquantes

Mais retournons au schéma plus simple, pour le décortiquer un peu plus...

A	B

Dispositions de mines possibles

Supposons que j'aie déminé tout le reste de la grille, et que je sais qu'il reste exactement 3 mines.

La tentation serait de penser que le cas A, avec exactement 3 mines est le plus probable. Cela est faux.

On pourrait aussi considérer le nombre total de mines, et le nombre de cases non découvertes, pour dire "quelles sont les chances pour que la zone de 3x3 cases dans le coin n'ait pas de mines". C'est incorrect. La raison pour laquelle c'est incorrect est difficile à comprendre, et pourrait être comparée au paradoxe "faisons un choix". Je dirai simplement que ça ne dépend pas du nombre total de mines et de la taille de la grille.

La réponse est celle-ci : combien de dispositions de mines existe-t-il qui correspondent à ce que j'ai déjà découvert de la grille ? L'image en montre 2 : la configuration A et la B. Mais la B n'a que deux mines. La 3e peut être à n'importe quel endroit de la zone de 3x3 cases dasn le coin, dont on ne connaît aucune information. Il y a ainsi 9 configurations de B différentes ; j'ai pas pris le temps de les dessiner toutes.

Du coup, il y a 10 dispositions possibles, chacune ayant une chance équivalente. (Comme dit précédemment, c'est un point crucial dans la compréhension des probabilités. Les probabilités que l'ordinateur ait généré chacune de ces situations sont faibles, mais elles sont égales, d'après ce que nous savons du Démineur. C'est exactement comme faire un pile ou face et tomber 2 fois sur pile puis 1 face, puis 1 pile, puis 3 fois sur face, puis 1 pile, puis 1 face, puis 1 pile. On obtient 5 pile et 5 face, mais dans un certain ordre. Dans le Démineur, cela concerne des arrangements de mines, qui equivalent au pile ou face.)

Puisque chacun des 10 possibilités (9 pour B, 1 pour A) est équiprobable, la disposition B a 90% de chances d'être correcte dans ce scénario particulier !

S'il ne restait que 4 mines à ce moment du jeu, alors la disposition A aurait 9 variantes. La disposition B aurait une variante pour chaque arrangement de 2 mines dans la zone de 3*3 cases dans le coin ; c'est C(9,2), égal à 9!/((9-2)! * 2!), soit 9*8/2, soit 36. Dans ce cas, la disposition B a 75% de chances d'être correcte.

Avec 5 mines restantes, la disposition A aurait 36 variantes, et la B 9*9*7/6 = 84 variantes ; le % pour B ne serait que de 66% environ.

Avec 6 mines restantes, la B est à 60%. Avec 7 mines, B n'est plus qu'à 50%. Pour 8 mines restantes, B devient moins probable que A ; à ce moment-là il y a tellement de mines restantes dans les cases non découvertes qu'il y a moins de dispositions différentes. Considérons le pire des cas, c'est à dire lorsqu'il reste 11 mines - chose qui a extrêmement peu de chances d'arriver, mais si elle arrive, ces probabilités s'appliquent. Avec la disposition B, toutes les cases non découvertes sont des mines ; avec la configuration A, toutes sauf une sont des mines - et du coup il y a 9 variantes de A, et une seule de B.

 

Solution du problème

Dans la grille dont je parle depuis le début, il reste 9 mines. Une de ces mines va dans le coin en bas aà droite, et est totalement indépendante des autres zones, donc on peut oublier cette mine. Du coup, considérons la grille entière sauf cette mine : il ne reste plus que 8 mines. (Je continuerai à compter volontairement l'ovale dans la zone en haut à gauche, simplement pour ne pas créer d'ambiguité)

Toutes les combinaisons entre les différentes dispositions en haut à gauche et en bas à droite sont possibles, sauf l'une d'entre elles (A1 + A), qui nécessiterait 9 mines. Il faut alors énumérer chacune des dispositions possibles, et compter pour chacune le nombre de mines restantes, et le nombre cases non découvertes.

En fait, le nombre de cases non découvertes non liées au problème ne change rien à celui-ci : il y en a 9 dans le coin en bas à droite, et 3 en haut à gauche soit 12 au total.

Haut à gauche	Bas à droite	Nombre de mines	Mines restantes	Nombre de variantes de la disposition
A1	B	8	0	1
B1	A	8	0	1
B1	B	7	1	12
A2	A	8	0	1
A2	B	7	1	12
B2	A	7	1	12
B2	B	6	2	66
C2	A	8	0	1
C2	B	7	1	12