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

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

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

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 :D

- 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

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

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

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 ;)

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:

---

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

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"

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