Démineur : Tactiques Avancées

Une position de démineur désagréable

Dans cette position, je connais un tas de mines sur tous les fronts restants, mais je n’arrive pas à déterminer exactement où elles se trouvent.
Il y a quelques mines qui pourraient être dans l’une des deux positions (rouge ou bleu), un groupe de mines qui pourrait être dans l’une des deux dispositions (vert) et une situation plus complexe en haut à gauche que je n’ai pas marquée explicitement, impliquant le « 5 » et le « 6 ».

le mien exclut

Démineur : Logique ou Probabilité

Le démineur peut être joué de deux manières : comme un jeu de logique ou comme un jeu de probabilité.

Techniquement, la probabilité subsume la logique. Si vous pouvez prouver logiquement qu’une mine doit être à un endroit, sa probabilité doit être de 100 % ;
si vous pouvez prouver qu’elle ne peut pas l’être, sa probabilité doit être de 0 %. La probabilité est donc tout ce dont vous avez besoin, dans un certain sens.
Néanmoins, vous utilisez la déduction logique pour détecter ces situations à 100 % ; Parfois, surtout à des niveaux de difficulté plus faciles, c’est tout ce dont vous avez besoin pour terminer une partie de démineur ; aucun recours aux probabilités n’est nécessaire.

Mais il existe certainement des situations où toute la logique du monde ne vous sauvera pas. La situation « T » qui apparaît en bas au centre du plateau de jeu ci-dessus en est un exemple simple, légèrement compliqué par les mines supplémentaires à proximité.
(Le scénario le plus simple remplace le « 2 » par un « 1 » et le « 5 » par un « 3 », de sorte qu’il soit symétrique.)

Il n’y a aucun moyen d’obtenir d’autres informations sur l’emplacement probable de la seule mine qui reste dans ces deux espaces.
C’est une chance sur deux, comme un tirage au sort. Lorsque vous trouvez quelque chose comme cela, vous feriez probablement mieux de deviner tout de suite, plutôt que de le garder pour plus tard.
Ainsi, si vous vous trompez, vous n’aurez pas perdu beaucoup de temps supplémentaire à résoudre le reste du plateau.
(Je suis un perfectionniste, donc je le garde pour la fin, et je ne me reproche pas d’avoir mal deviné.
Et, attention, c’est une mauvaise conception de jeu que de mettre la victoire ou la défaite de la partie sur un tirage au sort.)

Une Tactique de Fin de Partie

Une tactique de fin de partie très simple que vous pouvez utiliser consiste à compter le nombre de mines restantes.
Supposons que j’ai résolu tout sauf la section inférieure droite du plateau. Voici les deux seules configurations de mines qui correspondent aux données :

le mien en bas a droite

Si vous atteignez cette position et que le compteur indique qu’il ne reste que deux mines, vous avez terminé ; ce doit être la position B.

Si le compteur indique qu’il en reste trois, ce n’est pas nécessairement la position A, cependant.
Il pourrait s’agir de la position B avec la mine restante dans l’un des groupes de 3×3 cases en bas à droite.

En fait, les probabilités sont en faveur de la réponse B.

Probabilités Locales

Si vous examinez uniquement les probabilités « localement », vous pouvez voir que chacune des cases des groupes mutuellement exclusifs marqués a 50 % de chances d’être une mine.
Par « localement », je veux dire que si vous avez un « 1 » à côté de deux cases inconnues, chacune a 50 % de chances d’être une mine.

L’état des lieux en bas au centre est exactement comme celle-ci : chacune des cases adjacentes à la paire inconnue a exactement une mine non comptabilisée, donc chaque élément de données adjacent suggère une chance de 50 %.
La situation en haut à gauche est similaire :

le mien sept

La situation en bas à droite est également un peu comme celle-ci ; chacun des nombres sur le « devant » a une mine non comptabilisée et deux cases où elle pourrait se trouver.

Si une case avait une mine non comptabilisée à côté de lui, mais trois cases inexplorées, chaque case aurait une probabilité de 33 % ;
quatre cases inexplorées donneraient chacune une chance de 25 % d’avoir une mine. S’il y avait deux mines non comptabilisées et trois cases inexplorées, chacune aurait une probabilité de 66 %.

Voici la situation de « probabilité locale » pour le plateau complet :

le mien local

Comme vous pouvez le voir, plusieurs cases dans la zone supérieure gauche ont plus d’une probabilité ; la case inexplorée adjacente au « 2 » et au « 6 » et celle adjacente au « 3 » et au « 5 ». (Celle à côté du « 5 » et du « 6 » a toujours 66 % en raison des deux, il n’y a donc pas d’incompatibilité apparente.)

Résoudre les conflits de probabilité locaux dans le jeu Démineur

Vous devriez vous demander à ce stade ce que signifie avoir des probabilités locales contradictoires. Une intuition est que la probabilité la plus élevée devrait l’emporter. Par exemple, le carré entre le 6 et le 2 doit en réalité être de 66 %. Cela signifierait que le carré le plus à gauche auquel est attribué un 50 % n’est en réalité que de 33 %. Ou vous pourriez penser que vous combinez les priorités d’une manière ou d’une autre ; peut-être que la probabilité devrait être de 5/6, ou la moyenne.

Mais aucune de ces hypothèses n’est vraiment correcte. Les données à partir desquelles les probabilités sont dérivées ne sont pas indépendantes les unes des autres, donc aucune mathématique directe sur les probabilités n’est valable. La raison pour laquelle une estimation locale de 50 % est correcte en bas au centre est qu’elle est réellement indépendante de tout le reste. Si vous construisiez au hasard des plateaux correspondant à toutes les données collectées jusqu’à présent, exactement la moitié d’entre eux auraient la mine à chacun des deux emplacements possibles.

(La probabilité déroute parfois les gens, qui ont du mal à savoir quelles règles de probabilité s’appliquent dans quelle situation. Cette approche est essentiellement une méthode garantie de validité, car elle sous-tend la définition de la probabilité en tant que statistique prédictive : mesure de tous les arrangements possibles qui auraient pu conduire à la situation actuelle, en supposant que chacun était également probable.)

Ainsi, la mesure correcte pour la situation en haut à gauche consiste à examiner tous les arrangements possibles de mines qui correspondent aux données actuellement collectées, et à mesurer quel pourcentage d’entre eux a une mine dans la bonne position.

Cela prendrait beaucoup de temps si nous le faisions directement. Heureusement, il existe de meilleures méthodes.

Compter les arrangements

La manière abstraite de calculer les probabilités consiste à parcourir tous les arrangements possibles de mines, à éliminer ceux qui ne correspondent pas aux données que nous avons collectées et à compter les statistiques pour chaque emplacement possible.

Une approche plus pratique consiste à ne considérer que ceux qui ne seraient pas éliminés du tout. Pour ce faire, vous devez appliquer la logique et générer toutes les situations possibles qui pourraient correspondre aux données actuelles. J’ai déjà montré les deux scénarios pour le coin inférieur droit ; voici les possibilités pour le haut à gauche :

mine en haut gauche

(Comme précédemment, l’ovale à double hauteur indique qu’une mine pourrait être dans l’une ou l’autre position avec une probabilité égale.)

J’aurais pu lister chacun de ces deux cas séparément, il y aurait donc 10 arrangements, mais cela ne s’avérerait pas utile.

Quant à l’organisation : les deux lignes (numérotées « 1 » et « 2 ») se distinguent par la position de la mine dans la quatrième ligne. Les trois colonnes sont caractérisées par la position des mines dans la deuxième ligne.

Attention aux subtilités des probabilités locales et globales

Maintenant, vous pourriez être tenté de simplement dire « aha, il y a cinq cas, nous pouvons donc compter le nombre de cas pour chaque emplacement possible de mine ». Par exemple, la mine de la quatrième ligne (par le « 1 » en bas à gauche) est à gauche dans les deux cas de la ligne 1, et à droite dans les trois cas de la ligne 2. Vous pourriez donc tenter d’argumenter qu’elle a 60 % de chances d’être à droite, adjacente au « 6 ». (Il s’agit d’une position qui présente des probabilités locales contradictoires de 50 % et 66 %.)

Cependant, cela oublie une subtilité importante : le nombre de mines est différent dans certains cas ; il y a 6 mines dans A1, 4 mines dans B2 et 5 dans les autres cas.

Compter les mines non touchées

Liets renvoie ensuite le script plus simple en bas à droite, puis explore ces sous-locations en détail.

le mien en bas a droite

Supposons que j’aie terminé tout le reste du plateau et que je sache qu’il reste exactement trois mines.

On pourrait être tenté de supposer que la configuration A, avec exactement trois mines, est plus probable. C’est faux.

On pourrait aussi être tenté de considérer combien il y avait de mines au total et combien de cases du plateau, et de dire « quelles sont les chances que la région 3×3 du bas soit vide ». C’est faux. La raison exacte pour laquelle cela est faux est complexe à expliquer et pourrait peut-être être comparée au « paradoxe de la conclusion d’un accord ». Il suffit de dire, cependant, que les probabilités réelles pour cette situation sont indépendantes du nombre total de mines et de la taille totale du plateau.

La réponse

La vraie réponse est la suivante : combien de configurations possibles de trois mines y a-t-il qui correspondent à ma connaissance du plateau ? L’image en montre deux : la configuration A et la configuration B. Mais la configuration B ne comporte que deux mines. La troisième mine pourrait se trouver dans n’importe laquelle des régions 3×3 inférieures de cases pour lesquelles je n’ai pas collecté de données. Il existe donc neuf configurations variantes de B ; je n’ai simplement pas pris la peine de les dessiner.

Il y a donc dix configurations possibles. Chacune de ces dix configurations a la même probabilité de se produire. (Comme mentionné précédemment, c’est la notion cruciale pour comprendre les probabilités. Les chances que l’ordinateur ait généré l’un de ces cas en premier lieu étaient faibles, mais elles étaient tout aussi faibles, car l’ordinateur [pour autant que nous le sachions] donnait à chaque arrangement une chance égale. Vous avez autant de chances d’obtenir dix faces d’affilée que de lancer le motif deux faces, une pile, une face, trois piles, une face, une pile, une face. Vous avez plus de chances d’obtenir un total de cinq faces et cinq piles que dix faces, mais pas un motif particulier de pile et de face. Dans Démineur, nous nous intéressons aux arrangements de mines, qui sont comme des motifs de lancer de pièces de monnaie.)

Analyse des probabilités des configurations

Étant donné que chacun des dix arrangements (neuf pour B, un pour A) a la même probabilité de se produire, la configuration B a 90 % de chances dans ce scénario particulier !

S’il restait quatre mines à ce stade, alors la configuration A aurait neuf variantes. La configuration B aurait une variante pour chaque arrangement de deux mines dans le coin inférieur gauche ; il s’agit de C(9,2), qui est 9!/((9-2)! * 2!), ou 9*8/2, qui est 36. Dans ce cas, la configuration B n’a que 75 % de probabilité.

Avec cinq mines, la configuration A a 36 variantes, et la configuration B a 9*8*7/6 = 84 variantes ; donc les chances pour B sont d’un peu plus de 66 %.

Avec six mines, la probabilité que B soit atteint est d’environ 60 %. S’il y a sept mines, la probabilité que B soit trouvée n’est que de 50 %. Dans le cas où il y a huit minutes, l’option B est moins probable que A ;

À l’heure actuelle, il y a tellement de mines supplémentaires à placer dans les emplacements restants qu’il y a moins d’installations.

Considérons le pire des cas, où il reste 11 mines. (Cela est extrêmement improbable, mais si cela se produisait, ces probabilités s’appliqueraient.) Avec la configuration B, tous les carrés non rencontrés doivent avoir une mine ; avec la configuration A, tous sauf un en ont une – et donc il y a 9 variantes pour A, et une seule pour B.

Une solution finale

Dans le plateau actuel, il reste 9 mines. L’une d’entre elles se trouve en bas au centre, ce qui permet un choix totalement indépendant que nous pouvons ignorer. Par conséquent, nous considérons le plateau complet à l’exception de ce cas ; il ne reste que huit mines non comptabilisées. (Je continuerai à compter explicitement l’ovale en haut à gauche puisqu’il est sur l’image en haut à gauche, juste pour être clair.)

Toute combinaison d’une configuration en haut à gauche et d’une configuration en bas à droite pourrait se produire, sauf l’une d’entre elles (A1 + A) qui nécessiterait neuf mines. Par conséquent, nous devons énumérer chacune de ces configurations possibles et compter les mines restantes et les cases non rencontrées.

En fait, le nombre de cases non rencontrées est indépendant : il y en a neuf en bas à droite et trois en haut à gauche, donc il y en a 12 au total.

En haut à gauche En bas à droite Nombre de mines Mines laissées Variantes inconnues
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

Il y a donc au total 118 combinaisons possibles. À partir de là, vous pouvez compter le nombre de combinaisons pour chacune des configurations en haut à gauche et en bas à droite indépendamment :

Configuration Variantes Pourcentage
A1 1 1
B1 13 11
A2 13 11
B2 78 66
C2 13 11
A 15 13
B 103 87

Calcul des probabilités pour chaque case

Ensuite, j’ai parcouru chaque case du tableau et calculé sa probabilité, en additionnant le nombre de variantes dans lesquelles elle apparaissait, en divisant par 118. (En fait, en additionnant simplement les pourcentages ci-dessus.) De plus, en moyenne, chaque case non rencontrée avait une mine dans 15 des 118 variantes (après tout, les chances qu’au moins une case non rencontrée ait une mine sont très élevées). [Ceci peut être calculé en multipliant le nombre de mines restantes par les variantes non rencontrées, ce qui vous indique le nombre moyen de mines sur les cases non rencontrées.]

mine chances

(Notez que cela ne montre pas toutes les informations disponibles. Par exemple, nous savons que la probabilité que les deux carrés vert foncé « 87 » soient liés : si l’un est vrai, l’autre doit l’être. De même, les trois « 13 » bleu pâle qui sont des mines pour la configuration A sont également liés. Les « 13 » bleu pâle restants ne sont pas liés : au contraire, si l’un d’eux devait être une mine, les chances que l’un des autres soit une mine diminuent.)

Jouer au jeu Démineur

Il y a de fortes chances que vous n’ayez pas envie de vous asseoir et de régler tous ces calculs lorsque vous jouez à un jeu de démineur.

Moi non plus.

J’ai énuméré les configurations possibles en haut à gauche et en bas à droite. J’ai remarqué qu’une configuration (B2-B) utilisait une mine de moins que toutes les autres. Cette règle empirique a été appliquée : « moins de mines signifie plus de variantes non rencontrées » (ce qui s’applique à peu près jusqu’à ce que le nombre de cases non rencontrées soit inférieur à deux fois le nombre de mines non rencontrées), ce qui signifie que les configurations qui utilisent moins de mines sont beaucoup plus probables.

Comme il y avait beaucoup de configurations en haut à gauche, déterminer les probabilités pour une case est quelque peu compliqué. Par conséquent, j’ai simplement pensé que la configuration B en bas à droite était beaucoup plus probable et j’ai deviné l’une des cases appropriées. (J’espérais que cela me permettrait de terminer le coin inférieur droit, puis, armé de plus de connaissances sur le nombre de mines restantes, je pourrais terminer le coin supérieur gauche, et il ne me resterait plus qu’à lancer la pièce en bas au centre. Bien sûr, idéalement, je choisirais une case qui maximiserait la probabilité d’obtenir des informations utiles, mais n’importe laquelle de ces suppositions m’aurait permis d'”entrer” dans le coin inférieur droit pour une collecte de données supplémentaire.) Les probabilités étaient en faveur de la configuration B, j’ai donc choisi une case qui avait une mine pour la configuration A.

mine perds

Huit fois sur neuf, j’aurais eu raison.

Source: https://nothings.org/games/minesweeper/

Explorez d’autres articles utiles :

Démineur : Guide étape par étape

Démineur : Trucs et Astuces