IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

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

Algorithmes et structures de données Discussion :

algorithme pour calcul de probabilité


Sujet :

Algorithmes et structures de données

  1. #1
    Membre à l'essai
    Inscrit en
    septembre 2005
    Messages
    48
    Détails du profil
    Informations forums :
    Inscription : septembre 2005
    Messages : 48
    Points : 18
    Points
    18
    Par défaut algorithme pour calcul de probabilité
    salut a tous
    voila j'ai un projet d'algo a rendre pour bientot, mais je bloque car c la premiere fois qu'on me demande de faire un algo pour calculer une proba(en general c juste des formule), donc ce que je cherche se n'est pas une reponse toute faite mais des pistes pour m'aider dans la realisation du projet...



    voici la question:

    Objet : Calculer la probabilité de gagner pour le premier joueur dans un jeu de dés (sur la supposition que chaque joueur utilise sa stratégie optimale).

    Les règles du jeu

    donc si vous aviez une piste pour demarrer parceque la je sais meme pas par ou commencer...
    merci

    * n joueurs, numérotés de 1 à n, jouent chacun à son tour. La partie ne comprend qu'un tour.

    * Chaque joueur, jette d'abord deux dés ; ensuite il peut choisir de valider zéro, un ou les deux dés et il relance une deuxième fois le ou les dés invalidés ; son score est la somme des valeurs des deux dés après le deuxième essai.

    * Le joueur qui a le meilleur score de la partie gagne ; mais si deux joueurs ou plus partagent le même meilleur score, celui qui était parmi eux le dernier à jouer gagne.

    * Bien sûr, chaque joueur voit les jets de ses prédécesseurs et choisit la stratégie qui lui donne la meilleure probabilité de gagner.


    Astuce : Quelle est la probabilité pour que le joueur qui a le meilleur score parmi les i premiers gagne, si son score est de s? Cette probabilité ne dépend pas de celui qui parmi ces i premiers a ce score.


    voila c asse coton comme probleme et je sais meme pas par ou commencer, si vous avez une idée pour fractionner le probleme ou quoi que se soit qui pourrai aider...
    merci d'avance

  2. #2
    Membre averti Avatar de xxiemeciel
    Inscrit en
    juin 2005
    Messages
    371
    Détails du profil
    Informations forums :
    Inscription : juin 2005
    Messages : 371
    Points : 352
    Points
    352
    Par défaut
    Salut,

    effectivement c'est un probleme assez complexe.

    Personnellement je commencerais par essayer de determiner quelle est la strategie optimale donc on te parle au debut.

    Un fois que tu auras trouver cette stratégie tu pourras peut etre deduire une regle.

    XXiemeciel
    XXiemeciel

  3. #3
    Membre à l'essai
    Inscrit en
    septembre 2005
    Messages
    48
    Détails du profil
    Informations forums :
    Inscription : septembre 2005
    Messages : 48
    Points : 18
    Points
    18
    Par défaut
    c'est exactement ce que j'etait entrain de chercher: par strategie optimale on veut simplement dire qu'en fonction du score qu'on a fait , du meilleur score et (je ne suis pas sur que ce facteur entre en ligne de compte..) de la position du joueur, s'il faut relancer 1, 2, ou aucun des....

    mais comme tu le constate meme le debut du probleme est asse cho

  4. #4
    Membre averti Avatar de xxiemeciel
    Inscrit en
    juin 2005
    Messages
    371
    Détails du profil
    Informations forums :
    Inscription : juin 2005
    Messages : 371
    Points : 352
    Points
    352
    Par défaut
    je pense la strategie optimale ne va pas etre la même pour le tout premier joueur puis pour les suivants.

    Prenons S(i) le resultat du joueur i.

    maintenant essaye de determiner les regles pour le joueur S(i+1)
    et pour le joueur S(0).

    je verrais quelquechose dans le genre suivant :
    - il y a deux des nommons les D1 et D2 et pour nous simplifier la vie on considere toujours que D1 est superieur ou egal a D2 (suffit de prendre la plus grande valeur des des pour D1)

    - Je suppose aussi que ce sont des des de 6

    - Si D1 == D2 == 1 on relance les deux

    - Si D1 + D2 superieur a S(i) on ne relance rien

    - Si S(i) - D1 superieur a 6 : on relance les deux (sinon c'est pas possible de gagner)

    - Si S(i) - D1 inferieur ou egal a 6 : la ca devient plus difficile de voir ce qui va etre optimale car plus la difference est proche de 6 plus on peut avoir envie de relancer les deux des. donc on va avoir (6 - S(i) + D1) chances sur 6 de battre le joueur i. reste a determiner la proba dans le cas ou te relance les deux des et de prendre la meilleur proba entre les deux (ce sera peut etre toujours de lancer un seul des d'ailleur j'ai pas fait le calcul)

    Pour S(0):

    - Si D1 == D2 == 1 relance les deux des

    - Si D1 != 0 et D2 == 1 on relance D2

    - On pourrais peut etre envisager si un Des a une valeur inferieur a 3 de le relancer car la proba de faire plus est meilleur que la proba de faire moins.

    juste un detail pour que ce que je viens de marquer fonctionne S(i) est le joueur precedent non éliminé, car si le joueur suivant a fais moins alors il a perdu et il ne sera pas considéré dans mes calculs.

    XXiemeciel
    XXiemeciel

  5. #5
    Membre habitué
    Profil pro
    Inscrit en
    janvier 2003
    Messages
    141
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : janvier 2003
    Messages : 141
    Points : 139
    Points
    139
    Par défaut
    personnellement, je suis assez d'accord mais je tiendrai compte des probas.
    - si D1 ou D2 = MAX (=6) on conserve
    - si p(D1+D2 >= Mi) >= 0.5 avec Mi lex max des i ers joueurs on relance. en effet on a plus de 50% de faire mieux. Je ne prends pas d'inégalité stricte car le dernier joueur pour un score égal l'emporte.
    - il faut pê moduler si un dé est "conservé": D1 conservé -> la règle devient p(D2 >= Mi-D1) >= 0.5

    voilà c'est ce que j'explorerais en plus

    ps: les proba sont simples à calculer. tu peux visualiser ça facilement en dessinant l'arbre à 2 niveaux pour le lancé de 2 dés. j'espère que tu vois ce dont je parle pcq c dur à dessiner là :s

  6. #6
    Membre averti Avatar de xxiemeciel
    Inscrit en
    juin 2005
    Messages
    371
    Détails du profil
    Informations forums :
    Inscription : juin 2005
    Messages : 371
    Points : 352
    Points
    352
    Par défaut
    je crois je vois ce que tu veux dire, mais comparer a 0.5 me parais limité

    tu dois comparer la proba de gagner avec un seul Des contre la proba de gagner avec deux des, car elles pourraient dans l'absolu etre toutes les deux plus grandes que 0.5 mais si tu veux etre optimal tu dois choisir la meilleur.

    imagine l'Exemple suivant (la somme représente D1+D2) :

    S(i) = 3+2 = 5

    le joueur i+1 lance les des et obtiens 3+1 = 4

    La proba de gagner en lancant juste D2 ou en relancant les deux des est plus grande que 0.5, mais c'est relancer juste le des D2 qui donne les plus grandes chances de gagner.


    XXiemeciel
    XXiemeciel

  7. #7
    Membre habitué
    Profil pro
    Inscrit en
    janvier 2003
    Messages
    141
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : janvier 2003
    Messages : 141
    Points : 139
    Points
    139
    Par défaut
    tu as raison j'ai répondu un peu vite pour les probas.
    mais tu peux adapter aux "3 cas":
    - H2 : 2 dés conservés -> pas de proba, on "connait" son état par rapport aux joueurs précédents
    - H1: 1 dé conservé -> ta proba se limite à 1 seul des 2 dés
    - H0: 0 dé conservé -> la proba se calcule sur les 2 dés

    tu pondères les probas à condition que l'hypothèse puisse au moins surpasser Mi (le maximum actuel).
    donc si en conservant les 2 dés on est sur de perdre mais pas si en on conserve 1, alors on garde H1 et H0 et on évalue: 0.5 * P(H1) + 0.5 P(H0)

    il faut pê aussi envisager quel dé est conserver mais je pense que la base du raisonnement est plus que décrite

  8. #8
    Membre averti Avatar de xxiemeciel
    Inscrit en
    juin 2005
    Messages
    371
    Détails du profil
    Informations forums :
    Inscription : juin 2005
    Messages : 371
    Points : 352
    Points
    352
    Par défaut
    je ne comprend pas ton raisonnement

    comment peux tu faire des cas de decision sur des probas que tu ne connais pas.

    Tu dois d'abord faire tes probas pour justement savoir si tu dois relancer 1 ou 2 dés.

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
     
    - Cas Premier : Tu depasse S(i), fini
    - Cas deuxieme : tu es inférieur a S(i)
         - sous cas 1 :  tu ne peux pas gagner en relancant 1 seul dé : donc il faut lancer les deux dés
         - sous cas 2 :  tu peux gagner en lancant 1 seul dé : calcul de proba.
    Pour moi c'est aussi simple que ça.

    XXiemeciel
    XXiemeciel

  9. #9
    Membre habitué
    Profil pro
    Inscrit en
    janvier 2003
    Messages
    141
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : janvier 2003
    Messages : 141
    Points : 139
    Points
    139
    Par défaut
    en fait ce sont des probas que je connais. Je ne parle pas de proba de gagner mais de proba d'avoir un score "gagnant" par rapport aux i premiers joueurs.
    Mes règles de décision sont basée sur Mi (le maximum actuel) et la valeur des dés. Et sur le fait que si j'ai plus d'1 chance sur 2 de l'emporter (plus grand ou égal à Mi) et bien c'est la meilleure décision "locale"

  10. #10
    Membre averti Avatar de xxiemeciel
    Inscrit en
    juin 2005
    Messages
    371
    Détails du profil
    Informations forums :
    Inscription : juin 2005
    Messages : 371
    Points : 352
    Points
    352
    Par défaut
    On en revient a ce que je disais au debut, pourqoi prendre une chance sur deux ? sur quoi se base ce fameux 50% ?

    La seule chose sur laquelle tu peux baser tes probas c'est sur la valeure de tes des et Mi, rien d'autre.

    A priori ta chance de gagner peux tres bien etre dans tout les cas tres faible si Mi est tres proche du maximum. Cela n'empeche pas de calculer la proba de gagner en relancant 2 des ou en relancant 1 des.

    Soit Mi la valeur a battre :

    Premier lancé de Des : D1 + D2 = R (avec D1 superieur ou egal a D2)

    - Si D1 + MAX(D2) inferieur a Mi : on relance les deux
    - Si D1 == 1 (donc D2 == 1 aussi) : on peut relancer les deux aussi
    - Maintenant si D1 + MAX(D2) superieur a Mi alors :
    proba de gagner en relancant juste D2 : p1 = (MAX(D2) - Mi + D1)/6
    proba de gagner en relancant les deux des : p2 = sommes(Qp) p plus grand que Mi. Avec Qp la proba de faire p avec les deux des.

    si p1 superieur a p2 : lance un seul des
    si p2 superieur a p1 : lance les deux des


    Maintenant un exemple : R = 2 + 1 = 3 avec Mi = 7
    Tu peux gagner en relancant 1 des si tu fais 6 avec D2 donc p1 = 1/6
    Tu peux gagner en relancant les deux des si tu lances 8,9,10,11 ou 12

    donc p2 = 5/36 + 4/36 + 3/36 + 2/36 + 1/36 = 15/36

    p2 superieur a p1 donc pour etre optimal tu relances les deux dés dans ce cas.

    dans l'exemple tu peux remarquer que p1 et p2 sont tout les deux inferieur a 50% en plus.

    un petit lien util pour les probas avec deux des :
    http://villemin.gerard.free.fr/Wwwgvmm/Probabil/DesProba.htm#paire

    XXiemeciel
    XXiemeciel

Discussions similaires

  1. Algorithme pour calcul en virgule flottante
    Par djbad dans le forum Algorithmes et structures de données
    Réponses: 13
    Dernier message: 06/02/2011, 23h19
  2. Algorithmes pour calculer la factorielle
    Par TrexXx dans le forum Mathématiques
    Réponses: 14
    Dernier message: 22/01/2009, 23h32
  3. Algorithmes pour calculer la racine carrée
    Par TrexXx dans le forum Mathématiques
    Réponses: 17
    Dernier message: 20/01/2009, 16h28
  4. algorithme pour calculer les fonctions trigo ?
    Par thomas0302 dans le forum Mathématiques
    Réponses: 3
    Dernier message: 24/12/2007, 22h44
  5. Recherche d'un algorithme pour calculer un Checksum
    Par noune40 dans le forum VB 6 et antérieur
    Réponses: 2
    Dernier message: 23/11/2006, 10h46

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo