Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter
Démineur, probabilité d'avoir une mine ?
J'AI RAJOUTE DES SCHEMAS SUR CE QUI ME POSE PROBLEME, CONSULTEZ LES ICI :
http://www.developpez.net/forums/vie...12981&start=15
J'aimerais connaitre la probabilité qu'il y ait une mine sous une case.
J'ai déja un peu réfléchi au problème, et voila ou j'en suis.
La probabilité est de nb_mines_restantes / nb_cases_restantes si les cases voisines ne nous donnent aucune information.
Autrement la probabilité dépend des cases voisines, mais je n'arrive pas à le modéliser, quelqu'un a une idée ?
Re: Démineur, probabilité d'avoir une mine ?
Ce n'est pas plutot:Envoyé par KORTA
nb_mines_restantes / nb_cases_restantes
La probabilité est la même, c'est la probabilité que tu choississe cette case qui va varier suivant les informations que tu possède sur celle ci (donnée par les cases avoisinantes)
Re: Démineur, probabilité d'avoir une mine ?
Si si tu as raison. je corrige.Ce n'est pas plutot:
nb_mines_restantes / nb_cases_restantes
euh je pense pas. prenons un exemple pour m'expliquer :La probabilité est la même, c'est la probabilité que tu choississe cette case qui va varier suivant les informations que tu possède sur celle ci (donnée par les cases avoisinantes)
La probabilité pour qu'il y ait une mine sous une case X, dont une des cases voisines appelé Y est à "1" (cad qu'il y a une mine dans les 8 cases adjacentes) et dont les cases voisines de Y excepté X sont reconnues comme étant vides, est de 1 . En effet la mine est forcément sous X dans ce cas.
J'aimerais pouvoir généraliser ce raisonnement afin de le coder.
Re: Démineur, probabilité d'avoir une mine ?
La probabilité est la même, c'est la probabilité que tu choississe cette case qui va varier suivant les informations que tu possède sur celle ci (donnée par les cases avoisinantes)[/quote]
euh je pense pas. prenons un exemple pour m'expliquer :
La probabilité pour qu'il y ait une mine sous une case X, dont une des cases voisines appelé Y est à "1" (cad qu'il y a une mine dans les 8 cases adjacentes) et dont les cases voisines de Y excepté X sont reconnues comme étant vides, est de 1 . En effet la mine est forcément sous X dans ce cas.
J'aimerais pouvoir généraliser ce raisonnement afin de le coder.[/quote]
Après mure reflexion (10 secondes tout au plus) j'ai effectivement raconté n'importe quoi, désolé.
Il faut utiliser les probabilités conditionnelles.
La probabilité de l'évènement A sachant l'évènement B et noté : P(A/B).
Elle est determinée par P (A/B) = p(A ^ B) / p(B) où ^ est l'intersection.
oui ca a l'air d'etre une bonne idée, mais comment faire concrètement ?
P(X ) = p(X^Y) / p(X|Y)
comment calculer ca ?
je vais faire un peu de qualitatif.
le fait que tu connaisses une information sur les cases voisines grâce à une case écrase l'information globale nb de mines/nb de cases restantes.
c'est presque comme en physique quantique la probabilité de présence avant et après la mesure.
pour t'en convaincre imagine une grille où il n'y qu'une mine. tu tombe sur une case avec 1 marqué dessus.
donc tu n'as plus le choix qu'entre 7 cases. et pour le reste la probabilité devient exactement 0.
reste alors 2 types de possibilités pour calculer tes probas :
soit case à côté : prob. évidente
si tu as plusieurs choix pour une même case : la plus forte des deux.
si complexe, est-ce que cela marce tout le temps ? je ne sais pas.
soit éloigné: tu dois pouvoir trouver quelquechose pour estimer un minimun de mines qui collent aux choses déjà découvertes. (un espèce de balayage)
cela m'a l'air cohérent mais je ne porte pas garant
c'est pas mal mais en meme temps je vois pas comment tenir compte "exactement" de l'information...
imagine 2 cases indicatrices voisines: utiliser la proba max pour les cases inconnues à chaque fois, c'est négliger que tu as déjà "favoriser" une case inconnue en tenant compte de la 1ere indication. c'est pas hyper clair :s
sinon un autre "bricolage" qui me vient à l'esprit:
p = nb mines rest / nb cases rest
q = proba d'avoir une mine dans une case voisine d'une indication = nb indication / nb cases voisines
on parcourt toutes les cases restantes et on fait p_est = p + q
et on "renormalise" en trouvant un facteur r tel que r * (somme p_est) = 1
et on redistribue le r sur tout les p_est: p_final = r * p_est
bon voilà c'est sans doute incorrect mais ça peut donner un assez bon estimateur (j'espère)
sur le temps d'ecrire la reponse j'ai eu une autre idée en fait...
on fait 2 ensembles: ens avec indication et ens sans indication
nb_mines_indic = on calcule le nombres de mines qui sont sur des cases voisines à une ou plusieurs indications
nb_mines_norm = nb_mines_rest - nb_mines_indic
on separe le comptage des cases restantes de manière similair => nb_cases_indic et nb_cases_norm
et puis on calcule 2 probas:
pour les cases sans indic, on garde nb_mines_norm/ nb_cases_norm
pour les cases avec indic, 3 possibilités:
a) on approxime brutalement nb_mines_indic/nb_cases_indic
b) on utilise la formule de bayes complete. vu que le nombre d'indications autour d'une meme case est limitée à .... euh... 3 (si les indications >= 1) ça reste raisonnable à évaluer non?
c) un naive bayes: on suppose l'independance entre les differentes indications. c'est comme avant sauf que dans ce cas on a mieux evaluer les frequences je pense
ps: la limite à 3 si les indications >= 1 c'est "intuitif". mais je vois pas comment le prouver et j'ai pas de contre-exemple sous la main donc c'est peut-etre faux
wait wait, ton idée a l'air tres bonne mais je la suis pas ??!!,:
euh.. oui mais quelle idée? la deuxième je suppose?
et quelle partie te semble plus "nébuleuse" que le reste ...
oui c'est ca la deuxieme idée, et plus particulierement le calcul des probas des cases avec indications ...
bon je vais tenter d'eclaircir:
tu fais un ensemble avec toutes les cases qui sont voisines à une case avec indication: ensemble "A"
pour chaque indication "i" avec "m" mines, on prends les cases adjacentes "C_i". Si C_i contient déja >= m cases marquées, tu fais rien. Sinon tu marques les cases dans C_i jusqu'à ce qu'il y en ai m.
Tu parcoures toutes les indications comme ça. A la fin tu as donc obtenu le nombre de mines sur les cases voisines à des indications = nb de case marquées dans A.
c bon jusque là ??
et après bayes, tu connais je suppose...
en fait il faudrait pe exclure des cases quand on fait le marquage. Par exemple si les suppositions qu'on a faites sont telles que la configuration locale est determinée. càd si on ne peut logiquement plus marquer de cases (même si on a pu se tromper dans les cases minées)
Non, peux-tu réexpliquer STP ?
hé bien je pense qu'en prenant le max de proba pour chaque case qu'on rencontre on exagère l'estimation de la probilité réelle. En fait je cherchais un moyen pour calculer l'apport exact d'une indication ou plusieurs selon les cas de figures. En principe avec les probas conditionnelles, ça devrait etre possible SAUF que à partit d'une mine supposée on fait varier les probas des cases inconnues voisines mais aussi celle plus éloignée. Car si on tient compte de la proba induite par l'indication, on doit "pondérer" les estimations qu'on fait sur les cases suivantes. C'est pas evident sans dessin :s
sinon maintenant que j'y repense encore... peut-être que ce serait plus intelligent encore de modéliser ça comme un CSP (constraint satisfaction problem). on prendrait un calcul simple pour evaluer les probas des points inconnus voisins d'indications. Puis on prend la case inconnue avec la proba la plus grande. On fixe sa valeur, on propage et puis on regarde si une solution est encore possible. Enfin qqch comme ça et en iterant. Sinon on pourrait aussi resoudre le probleme avec les contraintes...
j'ai commencé a coder ceci en java
et le probleme que je rencontre est le meme que celui que tu exposes, car une case situé a l'intersection du voisinage de deux cases indicatrices supposent que la probabilité est supérieure, mais la calculer revient a avoir mal a la tete...
Autrement j'ai calculé simplement la probabilité de chaque case en consultant les états des cases voisines des voisines. c'est compliqué mais pour ceux qui ont suivi ca devrait pas etre trop dur a comprendre.
et essayer ma "première" idée
supposez l'indépendance et sommer les probabilités, puis normaliser le tout pour avoir une somme = 1 ?
c pas top mais c tjs ça non? ou alors juste prendre les 3 case les plus proches c pe un meilleur approximateur
euh j'ai oublié les cours de proba depuis longtemps, donc pour normaliser comment tu t'y prends ???
Ca a l'air d'etre une bonne idée ce que tu proposes.
Pour ceux qui n'ont pas compris, car il faut le dire c'est difficile a expliquer , voici quelques schémas :
Si vous arrivez a determniez les probas pour chaque case , vous êtes alors tres forts (les schémas sont de plus en plus complexes...)
facile.
carrément plus dur ..
euh impossible ?
alors la bravo si vous y arrivez
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)
mouais c vrai que le dernier post n'est pas hyper rigoureux mais on en a déjà parlé avant. En fait le nb de mines restantes ça donnerait une sorte de "prior" pour les cases restantes. Reste le plus dur: evaluer la proba en tenant compte des indications.
je pense de plus en plus qu'il s'agit d'un CSP (et accessoirement d'un probleme de proba) mais evaluer les probas conditionnelles de plusieurs indications
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Répondre avec citation
Partager