Ein physisches Deck wird unvollkommen gemischt und kommt meist ungeschoren davon. Ein digitales Deck hat keinen solchen Spielraum. Es wird von ein paar Zeilen Code gemischt, die entweder jede Anordnung mit gleicher Wahrscheinlichkeit erzeugen oder nicht, und der Unterschied zeigt sich nie auf dem Bildschirm, sondern erst in einer Häufigkeitstabelle nach einigen Millionen Händen. Es gibt eine Standardmethode, es richtig zu machen, eine bekannte Methode, es falsch zu machen, die gründlicher aussieht, und eine echte Grenze, die mit keiner von beiden zu tun hat.
Die Größe des Problems
Ein Deck mit 52 Karten lässt sich auf 52 Fakultät Arten anordnen: 52 × 51 × 50 und so weiter bis 1, was ungefähr 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, in 51 Tauschvorgängen
Der korrekte Algorithmus ist Fisher–Yates, und er ist kurz genug, um ihn in einem Satz zu beschreiben. Laufen Sie einen Zähler i von der letzten Karte bis zur zweiten herunter. Wählen Sie bei jedem Schritt eine Position j gleichverteilt zufällig von 0 bis einschließlich i, tauschen Sie die Karten an i und j, und fahren Sie fort. Bei 52 Karten sind das 51 Tauschvorgänge und 51 Zufallszahlen, und das Deck ist in einem Durchgang gemischt.
Der Grund, warum es funktioniert, ist ein Zählargument. Der erste Schritt hat 52 Wahlmöglichkeiten für j, die zweite mit 51, die dritte mit 50, bis hinunter zu 2 im letzten Schritt: 52! verschiedene Durchläufe des Algorithmus, jeweils gleich wahrscheinlich, weil jede Wahl gleichverteilt war. Es gibt außerdem genau 52! Anordnungen, und keine zwei Durchläufe ergeben dieselbe. Eine eindeutige Zuordnung zwischen gleich wahrscheinlichen Durchläufen und möglichen Anordnungen ist genau das, was ein gleichverteiltes Mischen bedeutet; also ist das Mischen gleichverteilt – nicht ungefähr, sondern exakt.
Der Off-by-one-Fehler, der es kaputt macht
Die verlockende Variante wählt j jedes Mal aus dem ganzen Deck – 0 bis 51 – statt von 0 bis 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 gleich wahrscheinliche Durchläufe statt 52!, und 5252 ist kein Vielfaches von 52!, daher können die Anordnungen unmöglich gleichmäßig herauskommen.
Drei Karten machen es greifbar genug, um es von Hand zu prüfen. Die fehlerhafte Version hat 33 = 27 gleich wahrscheinliche Durchläufe, verteilt auf 6 Anordnungen, was 4.5 Durchläufe pro Anordnung bräuchte. Stattdessen bekommen drei Anordnungen 5 Durchläufe und drei bekommen 4, sodass eine Gruppe 25% wahrscheinlicher ist als die andere. Bei vier Karten ist es schlimmer: 44 = 256 Durchläufe auf 24 Anordnungen, und die Zählungen reichen von 8 bis 15, was bedeutet, dass die wahrscheinlichste Anordnung fast doppelt so oft auftritt wie die unwahrscheinlichste. Die Verzerrung verblasst nicht, wenn das Deck wächst. Sie hört nur auf, etwas zu sein, das man bemerken könnte.
Wo die eigentliche Grenze liegt
Ein korrektes Mischen ist nur so gut wie die Zufallszahlen, die es speisen, und hier hat ein Browser- oder Handyspiel eine echte Einschränkung. Math.random in der Chromium-Engine, in der diese Spiele laufen, ist ein Generator namens xorshift128+ im Einsatz, der 128 Bit Zustand trägt. Das begrenzt die Zahl der verschiedenen Folgen, die er je erzeugen kann, auf 2128, also etwa 3.4 × 1038. Set that against 8.07 × 1067 Anordnungen, und der erreichbare Anteil liegt bei etwa 4 × 10-30. Almost every ordering of the deck cannot be produced at all.
Das klingt verheerend und ist es nicht, und genau diese Unterscheidung ist der nützliche Teil dieses Beitrags. Eine Video-Poker-Hand legt nie eine 52-Karten-Anordnung offen. Sie zeigt fünf Karten und dann bis zu fünf weitere. Es gibt 52 × 51 × 50 × 49 × 48 = 311,875,200 geordnete Fünf-Karten-Austeilungen und 2,598,960 verschiedene Fünf-Karten-Hände. Verteilt man 3.4 × 1038 mögliche Startzustände auf über 311 Millionen Austeilungen, und jede Austeilung hat immer noch in der Größenordnung von 1030 Zustände dahinter – gleichverteilt auf weit mehr Nachkommastellen, als irgendeine Spielmenge messen könnte. Die Schwäche von Math.random liegt darin, dass seine künftige Ausgabe für jeden vorhersagbar ist, der seinen inneren Zustand kennt. Genau deshalb ist er das falsche Werkzeug, wenn Geld im Spiel ist, und ein völlig ausreichendes für das Austeilen von fünf Karten in einem Übungsspiel.
Was das Mischen nicht überträgt
Zwei Details folgen aus der Gleichverteilung, und beide sind die Stellen, an denen Leute nach einer manipulierten Austeilung suchen.
Das erste ist, dass nichts eine Hand überdauert. Vor jeder Austeilung wird ein neues Deck von Grund auf aufgebaut und gemischt, sodass die vorherige Hand nichts beiträgt – deshalb Kartenzählen kann nicht funktionieren an einem Automaten, und warum eine lange Trockenphase die nächste Hand nicht wahrscheinlicher zur Auszahlung macht.
Das zweite ist, dass es keine Rolle spielt, von welchem Ende des Decks die Karten kommen. Eine Implementierung könnte die fünf Karten von oben austeilen und Ersatzkarten von unten nehmen, was danach klingt, als müsste es etwas bedeuten. Nach einem gleichverteilten Mischen hat jede Position im Deck dieselbe Verteilung, daher sind oben, unten und Mitte nicht zu unterscheiden, und die Wahl ist eine Bequemlichkeit für denjenigen, der den Code geschrieben hat, keine Tatsache über das Spiel. Dasselbe gilt für zweimaliges Mischen: Ein gleichverteiltes Mischen auf einem bereits gleichverteilten Deck bleibt gleichverteilt, der zweite Durchgang bringt also nichts.
Mischqualität und Fairness der Austeilung sind getrennte Fragen, und sie zu verwechseln ist der naheliegende Fehler. Ein Spiel kann ein Lehrbuch-Fisher–Yates über ein 52-Karten-Deck laufen lassen und dann eine der fünf Karten verändern, bevor sie auf dem Bildschirm gezogen wird, und am Mischen wäre davon nichts zu erkennen. Ob das Mischen gleichverteilt ist, lässt sich mit ein paar Zeilen Code beantworten. Ob die Hand, die Sie ansehen, die unveränderte Ausgabe des Mischens ist, ist eine andere Frage, und bei einem Spiel mit Gratis-Chips ohne Aufsicht lautet die ehrliche Antwort oft nein – auch bei dem unten.
Die Zusammenfassung ist kurz. Fisher–Yates über 0 bis i, 51 Tauschvorgänge, jede Anordnung gleich wahrscheinlich; die Variante über das ganze Deck ist verzerrt, und zwar unsichtbar ab etwa fünf Karten. Der Generator kann nicht die meisten Anordnungen eines vollen Decks erreichen, und für ein Fünf-Karten-Spiel ist das irrelevant. Nichts davon beantwortet, was zwischen dem Mischen und dem Bildschirm passiert, und das ist der einzige Teil einer digitalen Austeilung, bei dem Misstrauen angebracht ist.
Video Poker: Jacks or Better mischt genau wie oben beschrieben – ein frisches 52-Karten-Deck vor jeder Hand, Fisher–Yates über 0 bis i, 51 Tauschvorgänge, angetrieben von 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 Halte-Prioritäten statt zu beurteilen, wie oft Hände auftauchen. Es hat vier Automaten, jeder zeigt seine eigene, unveränderliche Tabelle: Jacks or Better von Anfang an, Deuces Wild auf Stufe 3, Bonus Poker auf Stufe 8 und Double Bonus auf Stufe 15, dazu Triple und Five Play auf Stufe 10. Sie beginnen mit 1,000 Chips, setzen 5, 10, 20 oder 50 pro Hand und sammeln täglich 200 weitere; Strategiehinweise lassen das empfohlene Halten aufleuchten. Es läuft offline, und die Chips haben keinen Geldwert.