Article écrit par Manu (1-12-53), le 3 août 2003
Introduction
On se demande souvent si il y a un endroit particulièrement favorable pour effectuer le premier clic d'une partie. Pour essayer de dégager le champ de mines sans laisser de zones non déminées ici ou là sur lesquelles il faut revenir ensuite, certains ont l'habitude de commencer dans un coin et d'essayer d'évoluer en diagonale vers le coin opposé. Ils prétendent en plus avoir un trou plus fréquemment en commençant par une extrémité… Pourquoi pas ?
Les petits calculs qui suivent visent à expliquer pourquoi on observe effectivement plus d'ouvertures sur les coins que sur les bords, et plus sur les bords qu'en plein milieu.
Probabilités
Les calculs sont basés sur les hypothèses suivantes :
1. la répartition des mines dans le champ est aléatoire. C'est-à-dire que toutes les grilles possibles pour un certain niveau ont une probabilité égale de sortir. En réalité, on sait depuis longtemps que c'est complètement faux, cela fera peut-être l'objet d'un autre article… Cependant c'est un modèle qui permet de faire des calculs simples et qui donne des résultats très réalistes quand on les compare aux résultats obtenus en commençant plusieurs centaines de parties. De plus ce modèle de « démineur parfaitement aléatoire » correspond à ce qu'on est en droit d'attendre d'une version du jeu. D'ailleurs, beaucoup de joueurs ignorent que le démineur de Microsoft n'est pas aléatoire…
2. le premier clic n'est jamais une mine. Cela par contre est une vérité non discutable, étant donné que c'est la manière dont a été fait le programme de Microsoft.
En partant sur la base de ces hypothèses, voilà
les résultats obtenus :
|
DEBUTANT WIN 98 (10 mines sur 8 × 8 = 64 cases)
|
| |
1er clic… |
2ème clic si le 1er clic n'a rien ouvert… |
| Pas de mine sous la case que vous avez choisi. Restent 10 mines sur les 63 autres cases, donc 53 chances sur 63 qu'il n'y ait pas de mine sous chaque case entourant la case choisie
|
Après le premier clic, il reste 10 mines sous 63 cases (donc 53 cases vides). Pour avoir un trou en cliquant au milieu, il faut 9 cases vides (disposées en 3*3). Pas juste 8 comme c'était le cas au premier clic
|
| Milieu |
 |
 |
| Bord |
 |
 |
| Coin |
 |
 |
On peut faire la même chose pour l'intermédiaire et l'expert :
|
INTERMEDIAIRE (40 mines sur 16 × 16 = 256 cases)
|
| |
1er clic… |
2ème clic si le 1er clic n'a rien ouvert… |
| Milieu |
 |
 |
| Bord |
 |
 |
| Coin |
 |
 |
Signification
Je précise la manière dont il faut comprendre les résultats obtenus en prenant un exemple…
A l'expert, on a 24.93 % de chance d'avoir une ouverture en effectuant son deuxième clic sur un bord... :
-> ...quel que soit l'emplacement du premier clic : que ce premier clic soit en coin, sur le bord ou au milieu, le second clic a 24.93 % de chances d'ouverture s'il est fait au bord.
-> ...si le premier clic n'a rien ouvert. En effet, si le premier clic a fait un trou de 45 cases par exemple, il ne reste plus que 480-45 = 435 cases non encore découvertes dont seulement 435-99 = 336 sont vides. Cela donne une probabilité de seulement  = 21.24 % d'avoir une deuxième ouverture, ce qui est nettement inférieur aux 24.93 % annoncés. Cela se comprend facilement en se disant que si le premier clic a fait un trou, la densité de mines sur l'espace restant a augmenté, ce qui diminue les chances d'ouverture. D'ailleurs, qui aurait envie de tenter de faire un deuxième trou s'il dispose au premier clic d'une grande ouverture facile
à exploiter ?
-> ... et si le 2ème clic est indépendant du premier. En effet, si le deuxième clic est fait sur une case touchant la case découverte au premier clic, il faut alors tenir compte de l'indication donnée par la case découverte comme dans l'exemple ci-dessous :
|
Dans cette situation d'expert, le premier clic a donné un 1. Si le deuxième clic est fait sur le ?, la probabilité d'ouverture n'est pas de 24.93 % comme calculé précédemment. En effet, pour avoir une ouverture dans cette situation précise, il faut que les deux conditions suivantes soient respectées :
1. la mine du 1 est sous une des 2 croix ; probabilité correspondante : 2/5 = 0.40 = 40%.
2. les deux cases sous les points sont vides ; probabilité correspondante :  = 62.94%
|
 |
Au total, la probabilité d'ouverture en cliquant sur le ? est de 0.4×0.6294 = 0.25.17 = 25.17%. On remarque que la présence du 1 fait varier cette probabilité d'ouverture de 24.93 % à 25.17%. L'écart aurait été nettement plus significatif (et en sens inverse) si ce 1 avait été un 2. Si ça avait été un 3 ou un 4 , le ? aurait été entouré d'au moins une mine et la probabilité d'ouverture aurait alors été 0%. Il y aurait même eu une importante probabilité de trouver une de ces mines sous le ? et donc de perdre la partie. Si le 1 avait été un 5 , la partie était obligatoirement perdue en cliquant sur le ?.
On comprend donc que les probabilités données au début de cet article concernant les 2ème
clics ne sont valables que si ce 2ème clic n'est pas fait à côté du 1er. Dans le cas
contraire, les calculs sont différents et souvent plus complexes.
Commentaires
• Il est amusant de constater que les probabilités d'ouverture sont légèrement plus grande à l'intermédiaire qu'au débutant, malgré le fait que la densité de mines soit la même pour ces deux niveaux : 10/64 = 40/256 = 0,15625. Cela est dû au fait que le premier clic n'est jamais une mine et que les densités réelles à prendre en compte sont donc 10/63 = 0.15873 pour le débutant et 40/255 = 0.15686 pour l'intermédiaire.
• Il est très important de comprendre une chose : il est plus facile d'obtenir une ouverture en coin qu'au milieu car on « demande » à moins de cases d'être vide. Cependant, les ouvertures obtenues au milieu sont en moyenne plus grandes étant donné qu'elles s'effectuent dans les 8 directions, contre seulement 5 pour une ouverture de bord et 3 pour une ouverture de coin. En résumé, cliquer au milieu ouvre moins souvent mais ça ouvre plus grand ! Tout est donc question de choix : soit on clique en coin pour avoir fréquemment des trous dès le début, quitte à avoir des trous difficiles à exploiter (voire impossible, ce qui arrive parfois aussi), soit on clique au milieu et on préfère avoir à commencer de nombreuses parties en attendant un trou présentant de nombreuses zones de travail facile. Pour trancher définitivement le débat, il pourrait être utile de calculer la taille moyenne (en nombre de cases) d'une ouverture de coin, d'une ouverture de bord et d'une ouverture de milieu. Avis aux matheux…
• J'ai comparé ces résultats théoriques avec les résultats obtenus par Paul Kerry (USA, 2-14-54) de manière expérimentale. Voici les résultats :
| Emplacement du premier clic |
Milieu |
Bord |
Coin |
| Pourcentage théorique d'ouverture en considérant une distribution parfaitement aléatoire des mines |
15.69 |
31.42 |
49.93 |
| Pourcentage d'ouverture constaté par Paul Kerry, sur un échantillon d'essai de 424 clics au milieu, 196 au bord et 135 en coin |
14 |
31 |
44 |
La comparaison nous amène à constater que même si on sait que la distribution des mines n'est pas parfaitement aléatoire, les résultats sont en général proches du modèle théorique. J'en appelle aux volontaires pour faire l'expérience sur plus de grilles (1000 clics de chaque cas serait bien) afin de préciser un peu ces premiers résultats.
• La dernière version de Windows XP propose une grille de 9*9 cases au lieu de 8*8 cases pour le niveau débutant. Voici l'influence de ce changement quant aux probabilités d'ouverture aux deux premiers clics :
| Probabilité d'ouverture au premier clic |
| |
DEBUTANT WIN 98 |
DEBUTANT WIN XP |
| Milieu |
 |
 |
| Bord |
 |
 |
| Coin |
 |
 |
Ces résultats sur les 2ème clics sont valables avec les mêmes conditions que précédemment.
Les écarts énormes observés sont dus au fait que dans cette nouvelle version, la densité de mines a été ramenée de 0.15625 à 0.125, soit une chute de 20% ! Dans ces conditions, il est évident que Windows XP favorise énormément les temps records. D'ailleurs un joueur comme Damien Moore (excellent joueur Canadien : 1-11-46 et n°3 mondial) a réussi à faire trois fois 2 sec et une fois 1 sec sur cette grille 9*9 dans ses 20 premières minutes d'essai ! C'est dire que cette grille doit à mon humble avis être maintenue comme non officielle en ce qui concerne l'homologation de records. Il existe avec la grille 8*8 des possibilités déjà trop importantes à mon goût de faire des temps inférieurs à 3 sec.
Voilà. J'espère avoir été clair et informatif. N'hésitez pas à me faire connaître vos réactions, remarques et corrections d'éventuelles erreurs sur le forum.
Bon déminage à vous tous,
Manu
|
