Discussion :

[KORTA]

si on n'a pas d'indication sur le nombre de mines, tu ne peux pas calculer la proba. Sinon, il faut en plus avoir une proba sur le nombre de mines potentielles dans la zone (proba que tu peux calculer à partir du nombre de cases restantes sur le plateau)

Ben supposons que le nombre de mines est nb_mines, et le nombre de cases est nb_cases et le nombre de cases restantes est nb_cases_restantes.

Bien que je ne pense pas que ce soit nécessaire d'avoir ces informations dans les exemples que j'ai montrés mais je peux me tromper ..

[PINGOUIN_GEANT]

j'ai essayé de formaliser avec l'aide d'événements, de variable aléatoire...
et en fait cela ne se fait pas du tout simplement :
car tu as d'une part : l'évènement case est une mine
mais surtout l'évènement du style case-nombre te donne une probabilité sur les cases voisines, qui se révèle "n'être pas vraiment un évènement".
donc, il faut une formulation extrêment poussée du problème pour utiliser tout ce qui probabilité conditionnelle.
plus prosaïquement, en fait tu as tes 1 de ton 3° exemple qui donnent des indications sur les configurations que tu peux obtenir et celles à exclure.
il s'agit plus d'un problème de dénombrement
et la vraie probabilité pour une case A grâce aux infos que tu as est :
nombre de configurations compatibles avec les données dont la case A est mine /
nombre de configurations compatibles avec les données.
après je ne sais pas s'il existe des méthodes rapides pour tout dénombrer ou si ce que les autres t'ont déjà proposé peut marcher

PS: en tout cas, ce que j'avais déjà proposé ne marche pas car cela ne respecte pas la formule indiquée plus haut

[Wavyx]

j'ai aussi essayé de formuler ca avec un systeme d'equations mais c'est foireux. En plus je pense qu'on devrait encore tenir compte du nombre de mines restantes pour evaluer correctement la proba d'une formulation :s

sinon je pense que tu devrais pê te tourner vers les CSP pour trouver les configurations compatibles. Pas forcément la résolution d'un csp mais au moins la propagation des contraintes.

c tout pour le moment...

[PINGOUIN_GEANT]

j'ai aussi essayé de formuler ca avec un systeme d'equations mais c'est foireux. En plus je pense qu'on devrait encore tenir compte du nombre de mines restantes pour evaluer correctement la proba d'une formulation :s

sinon je pense que tu devrais pê te tourner vers les CSP pour trouver les configurations compatibles. Pas forcément la résolution d'un csp mais au moins la propagation des contraintes.

c tout pour le moment...

avant d'essayer d'implémenter une méthode, il faudrait voir mathématiquement si elle marche. en fait qu'elle donne le résultat de la formule que j'ai indiquée plus haut, qui est, j'en suis sûr, bonne. (il faut donner un sens à ces probabilités (Que représente-elle ?) et seul le dénombrement le permet.)

[ceugniet]

il s'agit plus d'un problème de dénombrement
et la vraie probabilité pour une case A grâce aux infos que tu as est :
nombre de configurations compatibles avec les données dont la case A est mine /
nombre de configurations compatibles avec les données.

Très juste, et le dénombrement, ce n'est pas de la tarte. Je m'y suis collé pour le cas le plus simple, pour voir.

Il s'agit du cas nommé "carrément plus dur", c'est-à-dire le plus facile des trois. Il ne semble pas inconcevable de traiter chaque cas à la main, quoique cela risque de devenir extrêmement compliqué dans les cas suivants, mais par contre je ne vois pas comment automatiser ce traitement - le programmer pour laisser à l'ordinateur le plaisir de débrouiller les fils. En outre, les simplifications ci-dessous sont probablement assez difficiles à programmer ; les abandonner signifierait alors calculer réellement ces nombres de combinaisons et on tombe nécessairement hors du champ du format IEEE des réels, puisque si C=480 et M=99, alors C(C,M)=5,6.10**104, et l'on serait alors obligé de définir des routines spéciales pour grands nombres.

Voici mon exemple :

Dans le jeu complet, il reste M mines à placer dans C cases vides. On suppose, et c'est déjà faux, que l'on n'a aucune autre information sur la partie du jeu que l'on ne voit pas et par conséquent que toutes les configurations hors de cette zone sont équiprobables. (Ben oui, c'est faux car on sait qu'il y a une mine par ci, deux mines par là hors de la zone en question et que par conséquent toutes les configurations hors de cette zone ne sont pas équiprobables ! Mais que faire d'autre ?)

Dans cette zone de 3*5 soit 15 cases, il faut placer soit 1 mine, dans la colonne centrale (3 positions possibles) soit 1 mine dans les 5 cases de gauche et 1 dans les cinq de droite.

Il faut donc compter
toutes les configurations possibles a priori : il y a C(C,M) (nombre de combinaisons de C éléments pris M à M) façons de placer M mines dans C cases :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
    T = C(C,M) = C! / [(M!)*[(C-M)!]]

... toutes les configurations où il y a 1 mine dans l'une des trois cases centrales :

soit C(3,1) façons de choisir la case * C(C-15,M-1) façons de placer les M-1 mines restantes ailleurs que dans cette zone

... et toutes les configurations où il y a 1 mine dans les 5 cases de gauche et 1 dans les cinq de droite :

soit C(5,1) façons de choisir la case de la mine de gauche * C(5,1) façons de choisir la case de la mine de droite * C(C-15,M-2) façons de placer les M-2 mines restantes ailleurs que dans cette zone

La probabilité qu'il y ait une mine dans l'une des trois cases centrales (événement E1) est donc :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

P1 = 3 * [(C-15)!]/[(M-1)!]/[(C-M-14)!]  / T

La probabilité qu'il y ait une mine dans les 5 cases de gauche et une dans les 5 cases de droite (événement E2) est donc :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

P2 = 5*5 * [(C-15)!]/[(M-2)!]/[(C-M-13)!]  / T

Mais, on sait qu'on se trouve dans le cas de l'événement E1 ou dans celui de l'événement E2. Il nous suffit donc de calculer la probabilité conditionnelle "probabilité de E1 si (E1 ou E2)" et "probabilité de E2 si (E1 ou E2)"

La probabilité qu'une mine se trouve dans l'une des trois cases centrale est donc :

P'1 = P1 / (P1+P2)

La probabilité qu'une mine se trouve dans les 5 cases de gauche et une dans les 5 cases de droite est donc :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

P'2 = P2 / (P1+P2) = 1 - P'1

Il n'est donc pas nécessaire de calculer toutes ces factorielles car elles disparaissent dans les simplifications :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
P'1 = P1 / (P1+P2) = {3 * [(C-15)!]/[(M-1)!]/[(C-M-14)!]  / T}
 
                      / {
                           {3 * [(C-15)!]/[(M-1)!]/[(C-M-14)!]  / T}
                          +
                           {5*5 * [(C-15)!]/[(M-2)!]/[(C-M-13)!]  / T}
                        }
                   = {3 * [(C-15)!]/[(M-1)!]/[(C-M-14)!]}
 
                      / {
                           {3 * [(C-15)!]/[(M-1)!]/[(C-M-14)!]}
                          +
                           {5*5 * [(C-15)!]/[(M-2)!]/[(C-M-13)!]}
                        }
                   = {3 /[(M-1)!]/[(C-M-14)!]}
 
                      / {
                           {3 /[(M-1)!]/[(C-M-14)!]}
                          +
                           {5*5 /[(M-2)!]/[(C-M-13)!]}
                        }
                   = {3 /[(M-1)]/[(C-M-14)!]}
 
                      / {
                           {3 /[(M-1)]/[(C-M-14)!]}
                          +
                           {5*5 /[(C-M-13)!]}
                        }
                   = {3 /[(M-1)]}
 
                      / {
                           {3 /[(M-1)]}
                          +
                           {5*5 /[(C-M-13)]}
                        }
                   = {3*(C-M-13) /[(M-1)]}
 
                      / {
                           {3*(C-M-13) /[(M-1)]}
                          +
                           {5*5 }
                        }
                   = {3*(C-M-13) }
 
                      / {
                           {3*(C-M-13) }
                          +
                           {5*5*(M-1) }
                        }
P'1 =              = {3*(C-M-13) }/ {{3*(C-M-13) }+{5*5*(M-1) }}

Par exemple, si C = 100, M=20,

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

P'1 = 3*67 /(3*67+25*19) = 201/(201+475)=201/676

et

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

P'2=  25*19 /(3*67+25*19)= 475/(201+475)=475/676

P'1 est la probabilité qu'une mine se trouve dans l'une des trois cases centrales, mais chacune de ces trois cases joue le même rôle : la probabilité de présence dans chacune des cases centrales est donc P'1 /3 soit 67/676.
De même, P'2 est la probabilité qu'une mine se trouve dans l'une des cinq cases de gauche, mais chacune de ces cinq cases joue le même rôle : la probabilité de présence dans chacune des cases de gauche est donc P'2 /5 soit 95/676. De même pour les cases de droite, bien sûr.

J'espère que je ne me suis pas trompé, mais même si j'ai fait une erreur de calcul, cela donne une idée du genre de chose à faire. Reste à automatiser !!!

Euh, bon courage pour les cas suivants...

[Wavyx]

hum ! le developpement ! pas bcp de temps à consacrer à ce probleme cette semaine :s mais bravo pour l'effort !

sinon désolé d'insister sur le csp, mais je pense que en trouvant toutes les solutions admissibles selon les contraintes connues ( nb mines totales, indications, cases vides,...) on peut plus facilement (et pê plus justement) estimer la vraie probabilité de trouver une mine en un point. Car meme si il ya une probabilité estimée par une méthode "correcte", on utilise sans doute des configurations qui sont incompatibles pour une solution complète du problème.
J'espère que vous me suivez
en résumé: lister toutes les configurations de solutions possibles, puis dénombrer ou calculer la proba d'avoir une mine en un point (par exemple: nb de fois que la case X a une mine par rapport a toutes les configurations acceptables)

bon courage pour la suite

[ceugniet]

en résumé: lister toutes les configurations de solutions possibles, puis dénombrer ou calculer la proba d'avoir une mine en un point (par exemple: nb de fois que la case X a une mine par rapport a toutes les configurations acceptables)

Wavyx, tu as raison. C'est cela qu'il faut faire. Ce n'est pas très difficile mais il faut savoir combien cela prendra de temps en calcul. Je propose, de faire la liste des cases "renseignées" (celles qui portent un numéro); supposons qu'il y en ait 8. Pour chacune d'elles on liste les cases qui l'entourent à l'exception de celles qui sont déjà numérotées (et où l'on sait donc qu'il n'y a pas de mine). Par exemple, autour d'une case où se trouve un numéro 2, on liste huit cases. Les configurations dans ces huit cases sont au nombre de C(8,2). Ensuite on va faire 8 boucles imbriquées ; comme c'est ingérable (d'ailleurs ce ne sera pas à chaque fois 8 boucles; ça peut être 6, 7, 3, selon la complexité du problème), il faudra bien sûr faire une boucle de boucles, mais sur le principe c'est équivalent à huit boucles imbriquées les unes dans les autres. La boucle la plus externe concernera la case renseignée 0 et la boucle en question va passer en revue les configurations relatives à cette case. La boucle suivante (à l'intérieur de la première) concernera la case renseignée 1 et balayera les configurations autour de cette case, etc...Comme ceci ne tient pas compte des conflits, on verifiera à chaque niveau s'il y a conflit entre une configuration de ce niveau et les configurations des niveaux précédents et si oui on sautera à l'index suivant.

Finalement, on fait ce qu'a dit Wavyx : compter pour chaque case le nombre de CAS où elle s'est retrouvée avec une mine. Pour le comptage, il faudra pondérer avec les probabilités relatives de n-k mines au dehors, si la configuration en question comporte au total k mines, car k est variable selon les configurations.

Pour le cas "alors là bravo si vous y arrivez", par exemple, j'ai évalué le nombre de configurations : sans tenir compte des contraintes croisées, on dénombre environ 400 000 000 configurations, mais tenant compte du fait que la case comportant le chiffre 4 est proche d'autres cases comportant 1, on divise par 2 les possibilités autour de 4. De même pour les cases 2, etc. Je pense que l'on devrait balayer entre 10 000 000 et 20 000 000 configurations, ce qui permettrait peut-être d'avoir un temps d'exécution raisonnable.

C'est difficile d'évaluer le temps de calcul de ce passage en revue. Même si le gros cas que tu as proposé est effectivement trop lourd, je pense que tu peux résoudre comme cela les cas plus petits.

[Wavyx]

de manière générale, je pense qu'avec un CSP et une bonne méthode de propagation ya sans doute moyen d'avoir une complexité "effective" réduite.
mais il est vrai qu'il faut générer les contraintes et ça va vite. ya pas juste les contraintes vis à vis des cases avec indications. par exemple ya déjà la contrainte globale. Et puis aussi on trouve des configurations admissibles mais seulement pour les cases "trouvables" par la résolution d'un CSP. mais après il reste toutes les cases non fixées et non fixables :s

bref beaucoup de courage

sinon je pense (mais pas sûr) qu'il existe des versions de recherche locale pour les csp mais alors on perd l'estimation exacte.

voilà, j'ai plus trop d'idée pour creuser le problème. Faudrait tester et avoir pas mal de temps devant soi pcq ça va pas être direct.

bonne chance

ps: il existe des libraires pour les CSP en plus il s'agit d'une formulation entière donc des algos "efficaces".

[coco]

Voici ce que je propose pour passer d'un état N à un état N+1 (i-e découverte d'une case) :

1) P[] = tableau de probabilité qu'une case soit une mine initialisé à -1

2) T[] = tableau d'adjacence avec une case découverte initialisé à 0

3) C[] = tableau avec les valeurs d'adjacence et les mines

4) V[] = tableau temporaire des cases voisines

5) M = nombre total de mines

On parcourt C[] une première fois. On recherche les cases découvertes et pour chacune d'elle on met sa probabilité à 0 et on calcul la probabilité des ses voisines :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
//Remplissage des proba des cases découvertes + leurs voisines
Pour tous les i
_Pour tous les j
__Si C[i,j] est découverte Alors
___P[i,j]=0
___V[]=GetCasesVoisinesNonDejaDecouvertes(i,j)
___Pour tous les V[k,l]
____T[k,l]=T[k,l]+1 
____Si P[k,l]=-1 Alors
_____P[k,l]=0
____FinSi
____P[k,l]=(P[k,l] + C[i,j]/Len(V[])) / T[k,l]
___FinPour
__FinSi
_FinPour
FinPour

A ce stade, on a des probabilités approximatives pour les cases découvertes et leurs voisines (=cases traitées). Reste à remplir les autres cases :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
//Nombre de mines potentiellement présentes par les cases traitées :
NbMines=0
NbCasesNonTraitees=0
Pour tous les i
_Pour tous les j
__Si P[i,j]>-1 Alors
___NbMines=NbMines+P[i,j]
__Sinon
___NbCasesNonTraitees=NbCasesNonTraitees+1
__FinSi
_FinPour
FinPour
 
//Remplissage des proba des cases non traitées :
Pour tous les i
_Pour tous les j
__Si P[i,j]=-1 Alors
___P[i,j]=(M-NbMines) / NbCasesNonTraitees
__FinSi
_FinPour
FinPour

cet algo ne prend pas en compte le fait de marquer une case comme minée... mais c'est un début