L'art de bien mélanger un deck
écrit par zombie33


      Mélanger les cartes : une grande passion du joueur de Magic. Le joueur de Magic a tellement besoin de sa dose de shuffle que certains joueurs vont même jusqu'à déclarer un mulligan plutôt que de garder une main sans fetch. Vous l'aurez compris nous allons parler ici de battage de cartes et d’aléatoire.
L’idée d’écrire cet article est venu à force d’observer des joueurs se plaindre de la mauvaise distribution des cartes sur les plateformes de jeu online telles que Cockatrice ou MTGO et il me semble important de clarifier certains points à ce sujet. Le mélange de cartes, que ce soit dans la vie réelle ou lors de parties simulées par ordinateur est un sujet qui a fait l’objet de nombreuses études en mathématiques et en algorithmique. La plupart des articles de vulgarisations que l’on peut trouver sur le sujet sont souvent trop succints, mais surtout ne traitent dans leurs exemples que des jeux de 32 et 52 cartes alors que nous mélangeons en jouant à Magic des bibliothèques de toutes tailles.

Je vous propose donc ici un article spécifiquement destiné aux joueurs de Magic tenant compte des spécificités particulières de ce jeu. Bien que cet article comporte quelques notions de mathématiques avancées, pas de panique il se veut abordable par tous !


Comment sont effectués les mélanges de cartes sur les plateformes online ?

Mélanger un ensemble d’objets, comme des cartes magic, ce n’est pas compliqué en soit. Il suffit de numéroter les différents objets puis d’appliquer une permutation sur ces numéros. On obtient alors une notation assez intuitive comme on peut le voir dans l'exemple ci-dessous dans le cas où l'on a que 3 cartes :

• [1;2;3] : On ne change pas l’ordre des cartes.
• [1;3;2] : On échange la deuxième et la troisième carte.
• [2;1;3] : On échange la première et la deuxième carte.
• [2;3;1] : On coupe le paquet après une carte.
• [3;1;2] : On coupe le paquet après deux cartes.
• [3;2;1] : On échange la première et la troisième carte.

Au total, il n’y a que ces 6 permutations pour un ensemble de 3 cartes.

Un mélangeur parfait serait un mélangeur qui associerait à chacun de ces mélanges la même probabilité. Le problème, c’est que le nombre de permutations augmente très très rapidement en fonction du nombre de cartes que l’on considère. En effet pour un jeu de 60 cartes, le nombre de permutations possibles est supérieur au nombre d'atomes dans l’univers :
8320987112741390144276341183223364380754172606361245952449277696409600000000000000

Quand on mélange un paquet de cartes on aimerait avoir la même probabilité de se retrouver dans chacune de ces possibilités. Si on était capable d'avoir une méthode ou un ordinateur capable de faire cela, on l'appellerait : mélangeur parfait. Le problème, c'est qu'un tel mélangeur n'existe pas et que notre seul espoir va être de se rapprocher autant que possible de ce mélangeur.

Techniquement, un algorithme ne peut pas générer de phénomènes aléatoires car il est déterministe, il peut seulement générer des résultats très difficilement prévisibles et en apparence aléatoire et c'est bien sûr le cas des algorithmes utilisés sur les plateformes de jeux online comme MTGO ou Cockatrice. Ces algorithmes sont suffisamment performants pour être considérés comme "suffisamment aléatoires". Nous verrons plus loin qu'il existe un moyen de mesurer ce "suffisamment". Quoi qu'il en soit, toute forme d'injustice de la part des joueurs jouant sur ces plateformes et se plaignant de mana full ou mana death trop fréquents n'est rien de plus que le fruit d'un biais cognitif.



Le graphique ci-dessus décrit la probabilité d'avoir un certain nombre de terrains en main de départ avec un deck de 60 cartes contenant 24 terrains. Ce graphique a été obtenu avec un calcul de probabilité avec une loi hypergéométrique pour les valeurs bleues (c'est à dire pour un mélangeur parfait) et les valeurs rouges ont été obtenues avec 13000 premières mains obtenues sur MTGO.

J'aimerais rajouter à cela une remarque pour les joueurs de plateformes online. Quand j'affirme que le mélangeur utilisé est suffisamment performant, cela signifie entre autre qu'il est totalement inutile de mélanger plusieurs fois son deck à la suite... Pensez-y !


Comment bien mélanger son deck ?


La question que l’on se pose ici est double, car oui on veut certes obtenir un paquet bien mélangé de notre côté. Mais il est tout aussi important de connaître les techniques qui ne sont pas efficaces, car chacune d’entre elles, comme nous allons le voir, peut être détournée pour tricher par un joueur mal intentionné.

Le mélange Américain

Nous allons dans un premier temps nous intéresser au mélange le plus communément utilisé dans les jeux de cartes et ensuite nous interroger sur son efficacité.

Ce mélange consiste à séparer le tas de cartes en deux paquet approximativement égaux puis de former un troisième paquet de cartes en alternant approximativement les cartes de chaque paquet. Le fait que cette méthode soit approximative est justement un but recherché ici, car c’est de là que va naître l’aléatoire du mélange. Dans la pratique il y a plusieurs façon de faire un mélange américain et on a donné des noms différents à ces mélanges bien que le résultat obtenu soit à peu près du même type :

• Le mélange américain ou mélange en mitraillette (Riffle Shuffle) : Il s’agit de la technique la plus utilisée lorsque l’on mélange les cartes car il s’agit là de la plus rapide. C'est celle utilisé par les croupiers dans les casinos notamment.
• Le mélange par écrasement (Mashing Shuffle) : Il s’agit de la technique utilisée par les joueurs de cartes à collectionner tels que les joueurs de Magic car ces cartes ainsi que les protections supportent assez mal la courbure imposée par le mélange américain.


Il est communément admis que lorsqu’on effectue ce type de mélange plusieurs fois, notre paquet de cartes est bien mélangé. Tout réside dans le sens que l'on donne à “plusieurs”.

Avant d’aller plus loin dans cette analyse, je vais vous décrire un tour de magie imaginé au début du XXème siècle par deux magiciens Williams et Jordan. Il s’agit d’une application d’un résultat probabiliste. Le tour consiste à demander à une personne de prendre un jeu de cartes puis d'effectuer successivement : une coupe, un riffle shuffle, une coupe, un riffle shuffle et terminer par une coupe. Puis cette personne doit piocher une carte et la remettre au hasard dans le paquet. Le magicien se saisit alors du jeu et étale le paquet face visible devant lui et après un temps de réflexion fini par retrouver la carte choisie en moyenne 9 fois sur 10. Cela demande évidemment un entrainement particulier mais rien d'extraordinaire. Le magicien doit au préalable avoir appris l’ordre initial des cartes et savoir quoi regarder. Au final, le point important dans cet exemple est que si l’on n’apporte pas suffisamment de chaos à un système ordonné au préalable, il est toujours possible de tirer des informations du mélange obtenu avec une marge d’erreur qui peut être étonnement faible.

La question qui se pose est alors la suivante : Combien de fois donc doit on effectuer de mélange américain pour obtenir une répartition “suffisamment” aléatoire pour rendre toute triche impossible ?

La réponse à cette question délicate a été apporté assez récemment en 1992 par un mathématicien du nom de Persi Diaconis qui, et cela ne vous étonnera pas, fut auparavant un magicien professionnel. Pour répondre à cette question, Diaconis introduit un moyen de mesurer l’écart entre un mélangeur donné et le mélangeur parfait que l’on désire obtenir. Nous ne rentrerons pas dans les détails de ses travaux, mais ce qu’il faut savoir c’est que cet indicateur est un nombre entre 0 et 1 et plus il est proche de 0, plus notre mélange est efficace. Sachant cela, voici les courbes que fournit cet indicateur lorsque varie le nombre de mélanges américains.


Ce graphique est obtenu à l’aide des probabilités exactes et théorique et non d’un générateur aléatoire.
On observe donc sur ce graphique que les premiers mélanges effectués n’ont quasiment aucun effet sur notre indicateur. On estime que pour qu’un deck soit bien mélanger cet indicateur doit être au plus égal à 0,5 et cela correspond à mélanger au moins 6, 7 ou 8 fois pour des jeux ayant respectivement 40, 60 et 99 cartes.

Cela peut paraitre beaucoup et fastidieux mais comme on a naturellement tendance à sous-estimer toujours l'importance de mélanger suffisamment un deck, je vais vous donner un exemple concret de tricherie difficilement repérable, réalisable lorsqu’on ne mélange pas suffisamment un jeu et qui ne demande ni une adresse ni une mémoire excessive.

Vous êtes au milieu d’une partie de Magic et un effet vous permet de chercher une certaine carte dans votre bibliothèque. Nous prenons l’exemple d’une bibliothèque contenant alors environ 50 cartes. Le joueur se saisit alors de son deck à l’envers et le parcours jusqu’à trouver la carte recherchée. Lors de cette opération, il doit compter 8 cartes puis retenir les 5 suivantes. Quand il a trouvé la carte recherchée, il effectue un seul mélange américain et pose le deck devant votre adversaire pour qu’il le coupe. Si l’adversaire effectue une simple coupe machinalement, il l’effectuera approximativement au milieu. Les cinq cartes que vous avez alors retenu devraient vous parvenir assez tôt par la suite dans l’ordre inverse duquel vous les avez mémorisées et chacune séparée approximativement par une carte. Cela n’a l’air de rien, mais cela fournit assez facilement beaucoup d’informations au joueur.


Le mélange Français

Le mélange français (Overhand Shuffle) ainsi que le mélange indien (Indian Shuffle) consistent à séparer le paquet de cartes en un nombre aléatoire de paquets puis à inverser leur ordre. La seule chose qui différencie le mélange français et le mélange indien est la manière d'exécuter ce mélange mais le résultat est essentiellement le même.


En utilisant l’indicateur donné plus haut, on estime que le nombre de mélanges français nécessaires pour générer un mélange aléatoire est de l’ordre de 10 000. Il s’agit donc clairement d’un mélange à éviter si l’on souhaite bien mélanger son deck et il faut de même se méfier grandement des adversaires qui utilisent ce mélange pour mélanger les decks lors des tournois important. En effet, ce type de mélange peut être détourné assez facilement pour effectuer un stackage de votre deck. Le stackage est une technique assez répandue hélas qui consiste durant le mélange du deck adverse à observer la carte du dessous du paquet et choisir de la mettre au dessus du paquet ou non. Le but étant de donner ainsi à son adversaire une main de 7 terrains ou une main sans terrain. Bien évidemment une simple coupe suffit à contrecarrer cette méthode, mais le fait d’avoir dans son jeu 7 terrains consécutifs peut évidemment fortement influencer le reste de la partie.

Le mélange par tas

Il existe un type de mélange qui a un certain succès auprès des joueurs de magic et dont nous n’avons pas encore parlé ici. Ce mélange consiste à faire un certain nombre de tas de cartes (entre 3 et 7 généralement), à les remplir alternativement en suivant un ordre cyclique, puis à les rassembler dans l'ordre inverse où ils ont été créé (premier tas en dernière position, second tas en avant dernière position etc...).


La première chose qu’il faut savoir c’est que ce type de mélange doit toujours être combiné à une série de mélanges américains vu précédemment. Un mélange par tas quel qu’il soit, même répété plusieurs fois, n’est absolument pas un mélange fiable c’est même une horreur pure et simple. Je ne détaillerai pas la multitude de méthodes permettant de tricher avec ce type de mélange qui apporte des distributions très particulières à l’ensemble du deck, mais sachez par exemple qu’une des faiblesses les plus évidentes de ce mélange est que quelque soit le nombre de paquet que l'on fait et le nombre de cartes au total, il échangera toujours la première et la dernière carte. Faîtes donc deux mélanges de ce type, et ainsi la carte du dessus restera la même.

En résumé, un mélange par tas doit toujours être accompagné d’une série classique de mélanges américains. Mais même dans ce cas de figure, et j’insiste sur ce point, il n’apporte rien d’un point de vu strictement mathématique. C’est d’ailleurs assez compréhensible étant donné que ce mélange suit clairement un schéma prédéfini qui n’a absolument rien d’aléatoire.

Malgré cela, ce mélange est très répandu parmi les joueurs de Magic et on est donc en droit de se demander pourquoi... Pour répondre à cette question, il faut prendre un peu de recul sur le sujet et s’apercevoir qu’en effet ce type de mélange est certes très répandu à Magic ainsi que dans tous les jeux de cartes à collectionner, mais on ne retrouve pas cette pratique au Poker ou au Bridge par exemple. C’est quand même malheureux mais les cartes à collectionner ne sont pas faites pour être mélangées un grand nombre de fois. Les cartes sont chères et s'abîment très vite et en conséquence les joueurs utilisent des protections pour leurs cartes. Cependant ces dernières ont tendances à coller les unes aux autres ce qui crée un biais qui n'est absolument pas négligeable lorsqu'on effectue un mélange américain. Et là est la clé, le seul but d’un mélange part tas est de séparer toutes les cartes une à une pour s’assurer que deux cartes précédemment voisines ne le reste pas après mélange.


Le mélange Faro

Le Faro est un mélange qui est souvent confondu avec le mélange américain vu précédemment, mais son intérêt est toutefois très différent. Le Faro est un mélange américain parfait. C’est à dire que l’on coupe exactement le paquet de cartes en deux paquets égaux et qu’on les rassemble en alternant exactement les cartes de chaque paquet une par une. Ce mélange parfait est appelé le Faro et il en existe deux : In Faro (IF) pour lequel la première carte du paquet reste à la même position et Out Faro (OF) pour lequel la première carte arrive en seconde position.

Pour l'anecdote le nom Faro est en réalité le nom d'un jeu de cartes aussi appelé Pharaon. C'était un jeu d'argent populaire au XVIIIème siècle et c'est justement pour ce jeu qu'à été décrit pour la première fois dans un écrit anonyme de 1726, cette méthode comme moyen de tricher. Car vous l’avez compris, le principal but de cette opération n’est absolument pas de mélanger son jeu, mais bel est bien de tricher, de faire croire aux personnes qui nous entoure que le deck est mélangé alors qu’il ne l’est absolument pas. Il existe de nombreux tours de prestidigitation avec des jeux de 32 cartes qui reposent sur ce type de manipulation.

En pratique un Faro n’est pas réalisable en quelques seconde sur des cartes Magic avec des protèges cartes. Toutefois il n’est pas exclu que cela soit faisable par un prestidigitateur aguerri avec un paquet de 40 cartes neuves sans protection si vous voyez où je veux en venir… A partir de là, un joueur qui maîtriserait cette manipulation pourrait effectuer les manipulations décrites ci-dessous :

• Dix Out Faro successifs permettent de classer le deck en sens inverse.
• Trois In Faro successifs suivi d’un mélange en 8 tas permet de classer le deck en sens inverse.
• Un mélange en 4 tas suivi de deux In Faro permet de classer le deck en sens inverse.
• Deux In Faro suivi d’un mélange en 4 tas permet de classer le deck en sens inverse.

Et bien entendu, vous l’aurez compris, si on effectue deux manipulations successives qui classe le deck en sens inverse, cela revient à ne pas mélanger son jeu.


Ce qu'il faut retenir :

• Le mélangeur parfait n'existe pas.
• Les mélangeurs informatiques sont suffisamment performants pour qu'on puisse se fier à eux. Tout sentiment d'injustice de la part des joueurs sur les mains de départ qu'ils pourraient obtenir n'est qu'un biais cognitif.
• Pour bien mélanger un deck de 40, 60 ou 99 cartes il faut effectuer 6, 7 ou 8 mélanges américains ou par écrasements consécutifs. Toutefois dans le cas de mélange par écrasements, cela doit s'accompagner de plusieurs mélanges par tas afin de décoller chacune des cartes.
• Le mélange français n'est absolument pas fiable et permet à certains joueurs d'effectuer des techniques de stackage de votre deck.
• Un deck mal ou insuffisamment mélangé peut permettre à un adversaire mal intentionné de tricher facilement. Ne sous-estimez jamais l'importance de bien mélanger son deck ou celui de l'adversaire même pour des faits de jeux aussi anodins que l'activation d'un fetchland.