[MWS - Enquête] Le mélangeur de MWS truqué

Bon, c'est pas un scoop, tout le monde l'avait plus ou moins observé, mais j'en ai la preuve mathématique :

Je considère un jeu de 61 cartes comportant 21 terrains.
Dans toute la suite on appellera combin(m,n)=m!/(n!*(n-m)!)

Le nombre de possibilité pour piocher x terrains parmi les 21 cartes de terrains est : combin(21,x)
Le nombre de possibilité pour piocher 7-x cartes (on complète en fait la mains pour atteindre 7 cartes) parmi les 40 cartes non-terrains est combin (40,7-x)

Le nombre de mains ayant x terrains est finalement N(x) = combin(21,x)*combin(40,7-x)
Le nombre de mains possibles étant combin(61,7),

La probabilité pour avoir une main à x terrains est donc : combin(21,x)*combin(40,7-x)/combin(61,7)

On obtient : (th)

0 lands : 4.27%
1 lands : 18.47%
2 lands : 31.67%
3 lands : 27.86%
4 lands : 13.55%
5 lands : 3.63%
6 lands : 0.49%
7 lands :0.02%


J'ai effectué pour 100.000 mains différentes un test sur MWS, en utilisant le mélangeur 'parfait'. J'ai obtenu les valeurs suivantes : (obs)

0 lands : 2.42%
1 lands : 12.59%
2 lands : 26.67%
3 lands : 29.83%
4 lands : 19.39%
5 lands : 7.37%
6 lands : 1.53%
7 lands :0.2%

La variable S= somme[(obs_i-th_i)^2/th_i, i=0...7] suit une loi du khi² à 7 degrés de liberté.

S_observé = 13.8

L'hypothèse nulle "Le mélange est normal" est notée Ho.
Le test du khi² est unilatéral droit : au risque de 5% (de se tromper), la table donne S_max = 12.6

On a donc S_observé > S_max : L'hypothèse Ho est donc fausse au risque de 5%.


Finalement, avec 5% de chance de se tromper, on peut dire que le mélange de MWS est biaisé !



On voit d'ailleurs sur cette courbe (% de chance d'avoir une main de x terrains, en fonction de x (le nombre de terrains en main), que le biais est non négligeable : MWS privilégie les mana full, car on commence anormalement souvent avec des mains à 3, 4 et 5 terrains.

En contre partie, si vous testez vos jeux sur MWS, sachez qu'en réalité, il fera plus souvent des mana deaths qu'avec le programme.

_________________


[ Edité par chaudakh le 21 mar 2006 à 21h39 ]

chaudakh, ce n'est pas à toi qu'il faut apprendre qu'il ne s'agit que d'un générateur pseudo-aléatoire et donc qu'un biais et compréhensible.

ce n'est pas à toi qu'il faut apprendre qu'il ne s'agit que d'un générateur pseudo-aléatoire et donc qu'un biais et compréhensible.

Certes, mais j'en ai marre de devoir mulligan à chaque fois parce que j'ai des mains à 5 ou 6 lands, donc j'en ai cherché la raison. Le générateur pseudo-aléatoire est mauvais : le biais est franchement pas négligeable : A eux de modifier leur générateur de nombres aléatoires. Je fais pas le café non plus !

pourtant, ce n'est pas franchement dur de réaliser un shuffler non biaisé (ou si peu qu'on ne s'en rend pas compte)

_________________
Il faut mettre les liens

[ Edité par smc le 06 déc 2005 à 02h40 ]

pourtant, ce n'est pas franchement de réaliser un shuffler non biaisé (ou si peu qu'on ne s'en rend pas compte)

Rien compris. Il manque un mot non ? Dur peut-être...

Ce n'est pas parce que c'est du pseudo-aléatoire que le tirage doit être biaisé. Pour qu'il le soit à ce point, je pense que c'est forcément volontaire. Vous pouvez remarquer que la courbe est non seulement déplacée mais aussi aplatie (la variance doit être plus forte).

Je suis curieux de savoir Chaudâkh comment tu as fait pour faire ton expérience. Voici les points que j'aimerais éclaircir :
- comment as-tu fait pour automatiser les tirages et la capture des résultats ? Je serais intéressé pour faire mes propres expériences sur l'aléatoire de MWS.
- le deck utilisé pour les tests est-il le même pour les 100000 tirages ? Le biais n'est peut-être pas lié au type mais à l'ordre alphabétique des cartes. Si t'as fait le test avec 21 mountains, et si tu fais le test avec 4*chacun des basic land + 1 autre land, le résultat ne sera peut-être pas le même.
- as-tu essayé de voir les statistiques sur les autres types de cartes ?

Ce serait intéressant d'envoyer un mail à MWS leur expliquant les limites de leur logiciel sur ce point et en leur faisant comprendre que c'est très important (après tout, peut-être ne savent-il pas jouer à magic).

Je suis curieux de savoir Chaudâkh comment tu as fait pour faire ton expérience. Voici les points que j'aimerais éclaircir :
- comment as-tu fait pour automatiser les tirages et la capture des résultats ? Je serais intéressé pour faire mes propres expériences sur l'aléatoire de MWS.

Tu peux le faire en allant dans Statistiques >> Statistiques avancées, et là tu choisis l'onglet qui constitue les mains de départ. Tu peux ensuite générer le nombre que tu veux de main, en gérant aussi la méthode de tri, et MWS fait lui même les calculs de proba (il te donne aussi la proba de jouer un sort tour 1 et tour 2) ....
J'ai fait plusieurs fois l'expérience avec 100.000 mains (ce qui est déjà suffisamment grand pour établir une statistique), et la conclusion est à chaque fois la même : le khi² observé calculé est toujours supérieur au khi² maxi de tolérance à 5%. => conclusion : le mélange ne suit pas la loi théorique, à 5% près : le mélange est donc biaisé.

J'ai essayé avec 21 montagnes, d'autres terrains basiques et rien n'y fait, le biais est là.

Je n'ai par contre pas essayé avec un jeu de 60 cartes jouant 17 terrains (comme gob) ou une jeu de 63 cartes jouant 35 terrains (turboland) .... Peut être le biais est moindre au encore pire, à tester.

Pourtant, je me suis renseigné sur le site de MWS et ceux ci donne même le code du mélangeur de MWS : Les cartes semblent effectivement rangées dans le deck suivant une loi uniforme : peut être ai-je mal lu le code. Il y a un biais certain (sur la moyenne, moins sur l'écart type) introduit quelque part dans l'algorithme : il n'est pas normal que les terrains soient si souvent regroupés et que les cartes du même nom si souvent à côté.

En tout cas, MWS est un mauvais outil pour tester les decks, car à part piocher des terrains et commencer avec des mains à 5 lands, le programme ne sait pas faire grand chose d'autre malheureusement : il donnera de mauvaises indications sur la valeur réelle de la base de mana d'un jeu (ce qui est primordial pour un bicolore et surtout tricolore, comme zoo, trini-casse-terran, etc.)

Je compte à ce titre rédiger un article dans le bazar sur "Comment construire sa base de mana" en abordant l'aspect statistique de la chose, extrêment intéressante pour des jeux tricolores jouant des fetch, biland, et wasteland, ou pour des jeux requérant bcp de mana rapidement.

Moi je jouais un deck avec 40 lands sur 60 et j'ai réussi à avoir des mains sans aucun terrain qui donne du mana (j'avais 4 maze et 3 tabernacle).

Ok et merci pour les infos.

Si t'as besoin d'aide pour les calculs de proba, je peux t'aider (j'ai ce qu'il faut en bagage scientifique ). Mais apparemment tu te débrouilles aussi.

Hé bien !!!

je n'aurais jamais pensé que je verrai un jour ce cher khi2 faire son apparition sur un topic de magiccorp.

En tout cas les observation faites son très intéressantes et permettent peut-être d'en rassurer quelques uns ( moi par exemple) ...

Bravo pour l'étude, je pense que peu de gens se rendent compte de l'impact qu'un programme biaisé peu engendrer, surtout si celui-ci est utilisé afin de tester ses decks en vue d'un tournoi...

Oui mais c'est tellement étonnant...

Je m'en demande vraiment la raison. Il faut absolument faire un report à MWS. C'est peut-être une faiblesse cruciale de leur soft qu'ils n'avaient pas identifiée.

De mon côté, je vais essayer de voir si la difficulté de faire un mélange correct est si grande...

Je vais énumérer les raisons que j'entre-aperçois :
- involontaire :
............ils n'ont pas identifié leur bug
............ils ne connaissent rien à magic et pensent que ce fix n'est pas prioritaire
............c'est difficile de faire un algo de mélange de 60 cartes (ça m'étonnerait mais bon)
- volontaire :
............ils font un mélange proche de IRL qui n'est pas un mélange qui suit khi² de toute façon (quand on vient de faire une partie, c'est normal que les terrains/créatures/rituel&éphémères se retrouvent agglutinés si on ne fait pas gaffe
............ils ont une pression pour que la version gratuite sur ordi ne vienne pas supplanter la version payante IRL

Le problème, c'est qu'aucune des explications que je donne ne me parait plausible. Qu'en pensez-vous ? Avez-vous d'autres idées ?

Je vais t'apporter un élément de réponse Maverick.

Pour réaliser un mélange, et ce quel que soit le langage que tu utilises, tu peux identifier 3 grandes façons de faire (je ne rentrerai pas dans les détails). Chacune d'entre elles a plusieurs variantes bien sûr donc ça porte le total à plusieurs dizaines.
Elles ont toutes leurs avantages et leurs défauts mais aucune d'entre elles ne garantit le "100 % aléatoire".
MWS utilise l'une de ces 3 manières de faire (et pas la meilleure), ce qui explique les résultats démontrés par Chaudakh ci-dessus.

Si tu veux un autre exemple de biais de mélange, tu ouvres Winamp, tu fous un millier de chansons dedans et tu utilises la fonction "random" et "shuffle" et tu me dis ce que tu observes.

tu ouvres Winamp, tu fous un millier de chansons dedans et tu utilises la fonction "random" et "shuffle" et tu me dis ce que tu observes.

J'observe qu'une même chanson peut être rejouée à une chanson d'intervalle. C'est pourtant pas difficile de mettre un test après le choix du numéro de la chanson : "Si la chanson a déjà été jouée depuis l'ouverture du programme, je choisis un nouveau numéro, sinon, j'exécute la chanson" ...

MWS utilise l'une de ces 3 manières de faire (et pas la meilleure)

Certes, alors qu'ils apportent artificiellement un biais dans leur algorithme pour retomber à 5% près sur la loi théorique en IP(x) = combin(Nl,x)*combin(N - Nl,7-x)/combin(N,7)
où :
N = nombre de cartes du deck
Nl = nombre de cartes de terrains du deck
x = nombre de cartes de terrains en main

Je comprends tout à fait qu'on ait des problèmes de mélange, mais pas des problèmes de ce type :
- Je viens de monter un deck avec 29 terrains sur 63 cartes. Et bien avec MWS, j'ai deux fois plus de chances d'avoir 7 terrains en première main que 0 (0,54% contre 1,19%). J'ai obtenu ce résultat, quel que soit le mode de mélange utilisé (ils proposent un vrai aléatoire et une pseudo-simulation de mélange).

Et pourtant, j'utilise une grosse diversité de terrains, plus même que des autres cartes qui constituent mon deck.

Le mauvais mélange peut s'expliquer en disant qu'avant mélange il trie les cartes par type, et qu'ensuite il essaie de mélanger. C'est crétin. J'imagine comme cela, bêtement un moyen de s'assurer qu'il n'y ait pas de biais aussi visible :
- trier par nom de la carte et si une seconde occurence de la même carte arrive, lui rajouter cinq à la première carte. Par exemple, pour montagne ça donnerait :
1ère occurence : mountain
2ème occurence : rountain
3ème occurence : wountain
4ème occurence : bountain
5ème occurence : gountain
6ème occurence : lountain
7ème occurence : qountain
8ème occurence : vountain
...

En conclusion, même s'il y a ensuite un biais, il est invisible par l'utilisateur.

J'ai fait quelques tirages de main hier toujours avec le même deck, simplement pour voir si mon jeu sortait bien. Je suis tombé (au bout du 5ème tirage peut-être) sur une main avec 3 exploration. Je me dis : ok, ça peut arriver, regardons la biblio : 3 trini collées et 3 standstill dans 4 cartes. Difficile de mesurer l'improbabilité d'un tel évènement, mais intuitivement, c'est du gros foutage de gueule.

Ps : ce n'est pas la même chose de mélanger 1000 chansons et 60 cartes pour 2 raisons au moins :
- ce n'est pas le même ordre de grandeur d'éléments à mélanger
- un bon mélange n'est pas critique pour winamp alors que ça l'est pour MWS.

Qqun saurait s'il y a moyen de reprogrammer le module de mélangeage sur MWS ?
Parce qu'en y regardant de près (code source accessible partiellement sur le site officiel), le programme mélange les terrains, les enchantements, les artefacts, les creatures, les ephémères et les rituels séparément, puis fait du mélange par bloc... c'est pour ça que c'est biaisé (enfin je pense ...)

c'est assez surprenant en effet comme mélange.
sinon chaudakh, tu seras "jugé" au jury jeudi?

[Edit : Je censure sec ! pour le "jugment", J'en sais rien... je suis en exams en ce moment à l'ECL donc ça m'étonnerait qu'ils me valident mes cours du 2e trimestre aux Mines... Par contre j'ai enfin mon quitus langues, je suis monté à Nancy lundi dernier pour une soutenance avec Massemin)
_________________

mercenaire smc, à votre service

[ Edité par chaudakh le 22 mar 2006 à 13h49 ]

je ne savais pas qu'ils avaient mis une partie du code source...
faudrait que j'aille voir sur leur site...ca fait longtemps...