COM
MTGA
 Win
Rencontre de hasard  
1 sur le champ de bataille
Vis de mana  
1 sur le champ de bataille
Combo proposée le 31/03/2007, commentaire de :

NdZeSword: Les probabilités sont de notre côté : Mana Screw va nous rendre %C%C (donc nous faire gagner un mana) une fois sur deux, et ne rien donner (donc nous faire perdre %1) une fois sur deux. Ainsi, le tour après avoir joué Chance Encounter, on a 4 manas minimum, puisqu'on vient de jouer Chance Encounter. L'idée est qu'on a très peu de chance de faire beaucoup de mana (la probabilité d'arriver à N manas en partant de 4 avec N>=4 est de 4/N) mais on se fiche pas mal de faire beaucoup de manas, on veut juste "faire durer" suffisamment le nombre de pile ou face (on veut juste gagner 10 fois).

Parce que la capacité de Chance Encounter est une capacité déclenchée conditionnelle, il faut que la condition soit remplie *avant* le début de l'entretien pour qu'elle se déclenche. D'où l'idée qu'il faut essayer de charger l'Encounter tout de suite, pour gagner à l'entretien prochain.

En fait, sans poser de 5e terrain, on a environ 59,5% de chances de gagner au prochain entretien. Et si on a posé un 5e terrain, alors on a environ 69,3% de chances de gagner au prochain entretien. Bien sûr, si on n'est pas pressés et qu'on peut attendre un tour de plus, alors la victoire est quasi-assurée.

Notons M le nombre de mana qu'on a à disposition, et L le nombre de marqueurs "luck" qu'on a sur la Chance Encounter. Notons alors P(M, L) la probabilité de réussir à mettre 10 marqueurs "luck" sur la Chance Encounter à l'aide de Mana Screw dans le tour. On souhaite donc calculer P(4, 0).

%10 Il est évident que pour tout M, P(M, 10) = 1 (s'il y a 10 marqueurs "luck", alors on a réussi à les y mettre).

Pour les calculs suivants, on utilise le fait que :
* pour tout i < 10, P(0, i) = 0
=> si on n'a plus de mana dispo, on n'arrivera pas à mettre de marqueur supplémentaire.
* pour tout k > 0 et tout i < 10, P(k, i) = 1/2 * P(k-1, i) + 1/2 * P(k+1, i+1)
=> si on a k mana en pool et qu'on en utilise 1 pour la Screw, soit on perd le lancer (on a k-1 manas en pool et toujours autant de marqueurs) soit on gagne le lancer (on a k+1 manas en pool et un marqueur de plus).

%9 Calculons les P(M, 9).
* P(0, 9) = 0
* P(1, 9) = 1/2 * P(0, 9) + 1/2 * P(2, 10) = 1/2 * 0 + 1/2 * 1 = 1/2
* P(2, 9) = 1/2 * P(1, 9) + 1/2 * P(3, 10) = 1/2 * 1/2 + 1/2 * 1 = 1/4 + 2/4 = 3/4
* P(3, 9) = 1/2 * P(2, 9) + 1/2 * P(4, 10) = 1/2 * 3/4 + 1/2 * 1 = 3/8 + 4/8 = 7/8
* P(4, 9) = 1/2 * P(3, 9) + 1/2 * P(5, 10) = 1/2 * 7/8 + 1/2 * 1 = 7/16 + 8/16 = 15/16
* etc.
* Par récurrence, P(M, 9) = (2^M - 1) / 2^M

%8 Calculons les P(M, 8)
* P(0, 8) = 0
* P(1, 8) = 1/2 * P(0, 8) + 1/2 * P(2, 9) = 1/2 * 0 + 1/2 * 3/4 = 3/8
* P(2, 8) = 1/2 * P(1, 8) + 1/2 * P(3, 9) = 1/2 * 3/8 + 1/2 * 7/8 = 10/16
* P(3, 8) = 1/2 * P(2, 8) + 1/2 * P(4, 9) = 1/2 * 10/16 + 1/2 * 15/16 = 25/32
* P(4, 8) = 1/2 * P(3, 8) + 1/2 * P(5, 9) = 1/2 * 25/32 + 1/2 * 31/32 = 56/64
* P(5, 8) = 1/2 * P(4, 8) + 1/2 * P(6, 9) = 1/2 * 56/64 + 1/2 * 63/64 = 119/128
* etc.
* Par récurrence, P(M, 8) = (2^(M+2) - (M+2) - 2) / 2^(M+2) (https://oeis.org/A000247 pour les numérateurs soit 0, 3, 10, 25, 56, 119, 246, 501, 1012, 2035, 4082, 8177, 16368, 32751, 65518, 131053, 262124, 524267, 1048554, 2097129, 4194280, 8388583, 16777190, 33554405, 67108836, 134217699, 268435426, 536870881, 1073741792, 2147483615)

%7 Calculons les P(M, 7)
* P(0, 7) = 0
* P(1, 7) = 1/2 * P(0, 7) + 1/2 * P(2, 8) = 1/2 * 0 + 1/2 * 10/16 = 10/32
* P(2, 7) = 1/2 * P(1, 7) + 1/2 * P(3, 8) = 1/2 * 10/32 + 1/2 * 25/32 = 35/64
* P(3, 7) = 1/2 * P(2, 7) + 1/2 * P(4, 8) = 1/2 * 35/64 + 1/2 * 56/64 = 91/128
* P(4, 7) = 1/2 * P(3, 7) + 1/2 * P(5, 8) = 1/2 * 91/128 + 1/2 * 119/128 = 210/256
* etc.
* Par récurrence, P(M, 7) = (2^(M+4) - ((M+5)(M+6)/2 + 1)) / 2^(M+4) (pour les numérateurs, 2^(M+4) - https://oeis.org/A000124 décalé de 5 soit 0, 10, 35, 91, 210, 456, 957, 1969, 4004)

%6 Calculons les P(M, 6)
* P(0, 6) = 0
* P(1, 6) = 1/2 * P(0, 6) + 1/2 * P(2, 7) = 1/2 * 0 + 1/2 * 35/64 = 35/128
* P(2, 6) = 1/2 * P(1, 6) + 1/2 * P(3, 7) = 1/2 * 35/128 + 1/2 * 91/128 = 126/256
* P(3, 6) = 1/2 * P(2, 6) + 1/2 * P(4, 7) = 1/2 * 126/256 + 1/2 * 210/256 = 336/512
* P(4, 6) = 1/2 * P(3, 6) + 1/2 * P(5, 7) = 1/2 * 336/512 + 1/2 * 456/512 = 792/1024
* etc.
* Par récurrence, P(M, 6) = (2^(M+6) - XXX) / 2^(M+6) (pour les numérateurs, 2^(M+6) - https://oeis.org/A000125 décalé de 7 soit 0, 35, 126, 336, 792, 1749, 3718, 7722)

%5 Calculons les P(M, 5)
* P(0, 5) = 0
* P(1, 5) = 1/2 * P(0, 5) + 1/2 * P(2, 6) = 1/2 * 0 + 1/2 * 126/256 = 126/512
* P(2, 5) = 1/2 * P(1, 5) + 1/2 * P(3, 6) = 1/2 * 126/512 + 1/2 * 336/512 = 462/1024
* P(3, 5) = 1/2 * P(2, 5) + 1/2 * P(4, 6) = 1/2 * 462/1024 + 1/2 * 792/1024 = 1254/2048
* P(4, 5) = 1/2 * P(3, 5) + 1/2 * P(5, 6) = 1/2 * 1254/2048 + 1/2 * 1749/2048 = 3003/4096
* etc.
* Par récurrence, P(M, 5) = (2^(M+8) - XXX) / 2^(M+8) (pour les numérateurs, 2^(M+8) - https://oeis.org/A000127 décalé de 9 soit 0, 126, 462, 1254, 3003, 6721, 14443, 30251)

%4 Calculons les P(M, 4)
* P(0, 4) = 0
* P(1, 4) = 1/2 * P(0, 4) + 1/2 * P(2, 5) = 1/2 * 0 + 1/2 * 462/1024 = 462/2048
* P(2, 4) = 1/2 * P(1, 4) + 1/2 * P(3, 5) = 1/2 * 462/2048 + 1/2 * 1254/2048 = 1716/4096
* P(3, 4) = 1/2 * P(2, 4) + 1/2 * P(4, 5) = 1/2 * 1716/4096 + 1/2 * 3003/4096 = 4719/8192
* P(4, 4) = 1/2 * P(3, 4) + 1/2 * P(5, 5) = 1/2 * 4719/8192 + 1/2 * 6721/8192 = 11440/16384
* etc.
* Par récurrence, P(M, 4) = (2^(M+10) - XXX) / 2^(M+10) (pour les numérateurs, 2^(M+10) - https://oeis.org/A006261 décalé de 11 soit 0, 462, 1716, 4719, 11440, 25883, 56134)

%3 Calculons les P(M, 3)
* P(0, 3) = 0
* P(1, 3) = 1/2 * P(0, 3) + 1/2 * P(2, 4) = 1/2 * 0 + 1/2 * 1716/4096 = 1716/8192
* P(2, 3) = 1/2 * P(1, 3) + 1/2 * P(3, 4) = 1/2 * 1716/8192 + 1/2 * 4719/8192 = 6435/16384
* P(3, 3) = 1/2 * P(2, 3) + 1/2 * P(4, 4) = 1/2 * 6435/16384 + 1/2 * 11440/16384 = 17875/32768
* P(4, 3) = 1/2 * P(3, 3) + 1/2 * P(5, 4) = 1/2 * 17875/32768 + 1/2 * 25883/32768 = 43758/65536
* etc.
* Par récurrence, P(M, 3) = (2^(M+12) - XXX) / 2^(M+12) (pour les numérateurs, 2^(M+12) - https://oeis.org/A008859 décalé de 13 soit 0, 1716, 6435, 17875, 43758, 99892, 218348)

%2 Calculons les P(M, 2)
* P(0, 2) = 0
* P(1, 2) = 1/2 * P(0, 2) + 1/2 * P(2, 3) = 1/2 * 0 + 1/2 * 6435/16384 = 6435/32768
* P(2, 2) = 1/2 * P(1, 2) + 1/2 * P(3, 3) = 1/2 * 6435/32768 + 1/2 * 17875/32768 = 24310/65536
* P(3, 2) = 1/2 * P(2, 2) + 1/2 * P(4, 3) = 1/2 * 24310/65536 + 1/2 * 43758/65536 = 68068/131072
* P(4, 2) = 1/2 * P(3, 2) + 1/2 * P(5, 3) = 1/2 * 68068/131072 + 1/2 * 99892/131072 = 167960/262144
* etc.
* Par récurrence, P(M, 2) = (2^(M+14) - XXX) / 2^(M+14) (pour les numérateurs, 2^(M+14) - https://oeis.org/A008860 décalé de 15 soit 0, 6435, 24310, 68068, 167960, 386308, 850136)

%1 Calculons les P(M, 1)
* P(0, 1) = 0
* P(1, 1) = 1/2 * P(0, 1) + 1/2 * P(2, 2) = 1/2 * 0 + 1/2 * 24310/65536 = 24310/131072
* P(2, 1) = 1/2 * P(1, 1) + 1/2 * P(3, 2) = 1/2 * 24310/131072 + 1/2 * 68068/131072 = 92378/262144
* P(3, 1) = 1/2 * P(2, 1) + 1/2 * P(4, 2) = 1/2 * 92378/262144 + 1/2 * 167960/262144 = 260338/524288
* P(4, 1) = 1/2 * P(3, 1) + 1/2 * P(5, 2) = 1/2 * 260338/524288 + 1/2 * 386308/524288 = 646646/1048576
* etc.
* Par récurrence, P(M, 1) = (2^(M+16) - XXX) / 2^(M+16) (pour les numérateurs, 2^(M+16) - https://oeis.org/A008861 décalé de 17 soit 0, 24310, 92378, 260338, 646646, 1496782, 3313334)

%0 Calculons les P(M, 0)
* P(0, 0) = 0
* P(1, 0) = 1/2 * P(0, 0) + 1/2 * P(2, 1) = 1/2 * 0 + 1/2 * 92378/262144 = 92378/524288
* P(2, 0) = 1/2 * P(1, 0) + 1/2 * P(3, 1) = 1/2 * 92378/524288 + 1/2 * 260338/524288 = 352716/1048576
* P(3, 0) = 1/2 * P(2, 0) + 1/2 * P(4, 1) = 1/2 * 352716/1048576 + 1/2 * 646646/1048576 = 999362/2097152
* P(4, 0) = 1/2 * P(3, 0) + 1/2 * P(5, 1) = 1/2 * 999362/2097152 + 1/2 * 1496782/2097152 = 2496144/4194304

Ainsi, on a une probabilité de 2496144/4194304 soit environ 59,5% de chances de gagner. Et si on avait posé un 5e terrain, alors :

* P(5, 0) = 1/2 * P(4, 0) + 1/2 * P(6, 1) = 1/2 * 2496144/4194304 + 1/2 * 3313334/4194304 = 5809478/8388608

Ainsi, on a une probabilité de 5809478/8388608 soit environ 69,3% de chances de gagner.

Ndniarfounet: En raison des règles sur le slow play, cette combo ne sera pas autorisée en tournoi compétitif.

haut de page - Discussion : page 1

ZeSword
Bruxelles, Belgique

 Légende
le 30/11/2017 11:55
Une démonstration plus simple:
Coro, dans ce post a écrit :
La formule que tu cherches est la suivante. Pour 0=<k=<n des entiers, je note C(n, k) le coefficient binomial (k parmi n). La probabilité P(n, m) d'arriver à mettre au moins n marqueurs en ayant m manas au départ est donné par :
P(n, m) = 1 - 2^(2-2n-m) x sum(i = 0,...,n-1; C(2n+m-1, i))

Démonstration : On trouve la relation de récurrence vérifiée par les P(n, m), et on vérifie aisément que l'expression proposée vérifie la même relation de récurrence tout en remplissant les mêmes conditions initiales.

Démonstration 2 : Nan, en fait, c'est une blague, je ne suis pas du tout assez fort pour résoudre la relation de récurrence à 2 paramètres que tu as calculée brute force style. J'ai résolu le problème autrement. L'idée, c'est que le nombre de manas que tu as après les pile ou face suit ce qu'on appelle une marche aléatoire. Un peu de littérature à ce sujet ici.

Donc j'appelle S_k le nombre de manas que tu as après k lancers de pièce, en particulier S_0 = m. J'appelle X_k = 1 ou -1 le résultat du k-ième lancer, de sorte que :
S_k = m + sum(i=1,...,k; X_k)

Si un lancer X_k donne 1, j'appelle ça une montée, sinon c'est une descente. Je cherche donc à calculer la probabilité d'avoir au moins n montées avant que ma marche aléatoire S_k ne s'annule.

Je fixe maintenant le nombre de lancers de pièce à 2n + m - 1. Il est possible que mon jeu se termine avant, mais ce n'est pas grave, je lance les pièces jusqu'à la fin quitte à ce que mon nombre virtuel de mana S_k soit négatif si jamais il s'annule avant, ce sera commode pour calculer la formule. Pourquoi ce nombre? Il est suffisament grand pour que si je n'ai pas obtenu au moins mes n montées, alors forcément S_(2n + m - 1) est négatif. Il est suffisamment petit pour que si j'ai obtenu mes n montées avant que S_k ne s'annule, alors S_k ne s'est jamais annulé lors de mes 2n + m - 1 lancers, puisqu'il n'y a pas la place pour redescendre à 0 après n montées.

On obtient donc que les suites de lancers qui ne me permettent pas d'avoir n montées avant de perdre tout mon mana (c'est-à-dire annuler S_k) sont exactement celles qui annulent S_k quelque part dans mes 2n + m - 1 tirages. Je vais donc compter le nombre de ces suites ce qui me permettra de calculer la probabilité de l'événement complémentaire à celui qui m'intéresse. Parmi elles, il y a d'un côté celles qui finissent à un total S_(2n + m - 1) négatif et de l'autre celles qui finissent à un total positif mais s'annulent entre-temps.

D'après le petit papier que j'ai mis en lien plus haut, le nombre de suites qui aboutissent à un total S_(2n + m - 1) égal à S entier pair est nul. Le nombre qui aboutissent à un total égal à S entier impair négatif S = -(2j + 1) est donné par un nombre binomial C(2n+m-1, i) en notant i = (2n + m - 1 + S - m) / 2 le nombre de montées correspondant. D'après le principe de réflexion, c'est le théorème 1.2 du petit papier, le nombre de suites qui aboutissent à un total positif impair S = 2j + 1 mais annulent S_k entre-temps est exactement le nombre de suite qui aboutissent au total -S que je viens de calculer.

On introduit la probabilité 2^(1-2n-m) que chacune des suites individuellement a de se produire, on somme et on obtient la zolie formule que j'ai exhibée en haut de mon post, aux erreurs bêtes d'inattention près bien sûr.
Ant1
le 13/02/2023 10:53
Citation :
Ndniarfounet: En raison des règles sur le slow play, cette combo ne sera pas autorisée en tournoi compétitif.


en raison de Vis de mana surtout
haut de page - Discussion : page 1