Un jeu physique est mélangé de façon imparfaite, et s'en tire presque toujours. Un jeu numérique n'a pas cette marge. Il est mélangé par quelques lignes de code qui produisent soit chaque ordre avec la même probabilité, soit non, et la différence n'apparaît jamais à l'écran : elle se voit dans un tableau de fréquences après quelques millions de mains. Il existe une façon standard de le faire correctement, une façon bien connue de le faire mal qui paraît plus rigoureuse, et une limite réelle qui n'a rien à voir avec l'une ou l'autre.
L'ampleur du problème
Un jeu de 52 cartes peut être ordonné de 52 factorielle façons : 52 × 51 × 50 et ainsi de suite jusqu'à 1, ce qui fait environ 8.07 × 1067. Calling a deck shuffled is a claim about that number: that each of those orderings is exactly as likely as every other. It is a stronger claim than it sounds, and it is what the code must deliver.
Fisher–Yates, en 51 échanges
L'algorithme correct est Fisher–Yates, et il tient en une phrase. Parcourez un compteur i depuis la dernière carte jusqu'à la deuxième. À chaque étape, choisissez une position j uniformément au hasard de 0 jusqu'à inclus i, échangez les cartes aux positions i et j, puis passez à l'étape suivante. Pour 52 cartes, cela fait 51 échanges et 51 nombres aléatoires, et le jeu est mélangé en une seule passe.
La raison pour laquelle cela fonctionne tient à un argument de dénombrement. La première étape offre 52 choix pour j, la deuxième 51, la troisième 50, et ainsi de suite jusqu'à 2 à la dernière étape : 52! exécutions distinctes de l'algorithme, chacune équiprobable car chaque choix était uniforme. Il existe aussi exactement 52! ordres, et aucune de ces exécutions ne produit le même. Une correspondance biunivoque entre exécutions équiprobables et ordres possibles est précisément ce que signifie un mélange uniforme : le mélange est donc uniforme, non pas approximativement, mais exactement.
L'erreur d'indice qui le casse
La variante tentante choisit j à chaque fois dans tout le jeu — de 0 à 51 — plutôt que de 0 à i. It looks like it should be better, because every card can move anywhere at every step. It is not uniform, and the counting argument shows why immediately: there are now 5252 exécutions également probables plutôt que 52!, et 5252 n'est pas un multiple de 52!, si bien que les ordres ne peuvent pas être équiprobables.
Trois cartes suffisent à le rendre concret et vérifiable à la main. La version fautive a 33 = 27 exécutions également probables réparties sur 6 ordres, ce qui en exigerait 4.5 chacun. En réalité, trois ordres en obtiennent 5 et trois en obtiennent 4, si bien qu'un groupe est 25% plus probable que l'autre. À quatre cartes, c'est pire : 44 = 256 exécutions réparties sur 24 ordres, et les effectifs vont de 8 à 15 : l'ordre le plus probable arrive presque deux fois plus souvent que le moins probable. Le biais ne s'atténue pas à mesure que le jeu grandit. Il cesse simplement d'être perceptible.
Où se trouve la vraie limite
Un mélange correct ne vaut que par les nombres aléatoires qui l'alimentent, et c'est là qu'un jeu sur navigateur ou téléphone a une limite réelle. Math.random dans le moteur Chromium dans lequel tournent ces jeux est un générateur appelé xorshift128+, qui porte 128 bits d'état. Il limite à 2128, soit environ 3.4 × 1038. Set that against 8.07 × 1067 ordres, et la fraction accessible est d'environ 4 × 10-30. Almost every ordering of the deck cannot be produced at all.
Cela paraît fatal et ne l'est pas, et cette distinction est la partie utile de cet article. Une main de poker vidéo n'expose jamais un ordre de 52 cartes. Elle montre cinq cartes, puis jusqu'à cinq autres. Il existe 52 × 51 × 50 × 49 × 48 = 311,875,200 donnes ordonnées de cinq cartes, et 2,598,960 mains distinctes de cinq cartes. Répartissez 3.4 × 1038 états de départ possibles répartis sur 311 millions de donnes, et chaque donne a encore de l'ordre de 1030 états derrière elle — uniforme à bien plus de décimales que ce que n'importe quelle partie pourrait mesurer. La faiblesse de Math.random est que sa sortie future est prévisible pour quiconque connaît son état interne, ce qui explique précisément pourquoi il est le mauvais outil dès qu'il y a de l'argent en jeu, et un outil parfaitement adéquat pour distribuer cinq cartes dans un jeu d'entraînement.
Ce que le mélange ne transporte pas
Deux détails découlent de l'uniformité, et ce sont les deux endroits où l'on cherche une donne truquée.
Le premier est que rien ne survit à une main. Un jeu neuf est constitué et mélangé depuis zéro avant chaque donne, si bien que la main précédente n'apporte rien — ce qui explique pourquoi compter les cartes ne peut pas fonctionner sur une machine, et pourquoi une longue série sans gain ne rend pas la main suivante plus susceptible de payer.
Le second est qu'il importe peu d'où viennent les cartes dans le jeu. Une implémentation pourrait distribuer les cinq cartes depuis le dessus et prendre les cartes de tirage depuis le dessous, ce qui semble devoir signifier quelque chose. Après un mélange uniforme, chaque position du jeu a la même distribution ; le dessus, le dessous et le milieu sont donc indiscernables, et ce choix relève de la commodité de celui qui a écrit le code plutôt que d'un fait sur le jeu. Il en va de même pour un double mélange : un mélange uniforme appliqué à un jeu déjà uniforme reste uniforme, donc la seconde passe n'apporte rien.
La qualité du mélange et l'équité de la donne sont deux questions distinctes, et les confondre est l'erreur facile. Un jeu peut appliquer un Fisher–Yates de manuel sur un jeu de 52 cartes, puis modifier l'une des cinq cartes avant de la montrer à l'écran, sans que rien dans le mélange ne le révèle. Savoir si le mélange est uniforme se vérifie en quelques lignes de code. Savoir si la main que vous regardez est la sortie non modifiée du mélange est une autre question, et dans un jeu à jetons gratuits sans régulateur, la réponse honnête est souvent non — y compris pour celui ci-dessous.
En résumé, c'est court. Fisher–Yates de 0 à i, 51 échanges, chaque ordre étant équiprobable ; la variante appliquée à tout le jeu est biaisée, de façon invisible au-delà d'environ cinq cartes. Le générateur ne peut pas atteindre la plupart des ordres d'un jeu complet, et pour un jeu à cinq cartes cela n'a aucune importance. Rien de tout cela ne répond à ce qui se passe entre le mélange et l'écran, qui est la seule partie d'une donne numérique qui mérite d'être suspectée.
Video Poker: Jacks or Better mélange exactement comme décrit ci-dessus — un jeu neuf de 52 cartes avant chaque main, Fisher–Yates de 0 à i, 51 échanges, piloté par Math.random. It is also a free-chip practice game rather than a model of a regulated machine, so the paragraph above applies to it: the five dealt cards are not always the shuffle's untouched output. A dead deal is sometimes nudged towards a pair or a four-card flush, more often after a run of losses or when your balance is nearly gone, and a deal that already contains a pair or better is left alone. The draw is untouched — replacement cards come straight off the remaining shuffled deck — so the hold decisions you practise are the real ones even though hands arrive more kindly than the maths would send them. Use it to drill les priorités de garde plutôt que d'estimer la fréquence d'apparition des mains. Il propose quatre machines, chacune affichant sa propre table figée : Jacks or Better dès le départ, Deuces Wild au niveau 3, Bonus Poker au niveau 8 et Double Bonus au niveau 15, avec Triple and Five Play au niveau 10. Vous commencez avec 1,000 jetons, vous misez 5, 10, 20 ou 50 par main, et vous recevez 200 de plus une fois par jour ; les conseils de stratégie font briller les cartes conseillées à garder. Il fonctionne hors ligne, et les jetons n'ont aucune valeur monétaire.