Wenn Sie schon einmal einen Stapel Spielkarten gemischt haben, dann haben Sie dabei höchstwahrscheinlich eine einmalige Mischung erzeugt. Das heißt, Sie sind vermutlich der einzige Mensch, der die Karten jemals in dieser Reihenfolge angeordnet hat. Das mag unglaublich klingen, doch dieses Beispiel verdeutlicht, wie schnell unfassbar große Zahlen in ganz alltäglichen Situationen auftauchen können. Und das kann fatale Auswirkungen haben, wie die Entwickler eines Online-Pokerspiels Ende der 1990er Jahre schmerzlich herausfanden (Dank an den »Nerds at work«-Podcast für diese Geschichte).

Die Mathematik des Kartenmischens ist im Grunde recht schnell erklärt: Möchte man ausrechnen, wie viele Anordnungen 52 Spielkarten haben können, muss man dafür alle Möglichkeiten des Mischens durchgehen. Zuoberst liegt eine von 52 Karten. Wenn diese festgelegt ist, gibt es nur noch 51 Möglichkeiten, die darunter befindliche Karte zu wählen. Die nächste Karte hat dann nur noch 50 mögliche Werte und so weiter. Deshalb lässt sich ein Stapel mit 52 Karten auf $52\cdot 51\cdot 50\cdot \dots \cdot 2\cdot 1=52!$ verschiedene Weisen anordnen. Um zu veranschaulichen, wie groß diese Zahl ist, zitiere ich die deutschen Podcaster Rezo und Julien Bam, die sich in einer Folge des Podcasts »Hobbylos« darüber unterhalten:

Rezo: »Was da rauskommt, ist eine Zahl, die 67 Nullen hat. Das ist mehr, als es Atome gibt auf der Erde.«

Julien: »Alter.«

Rezo: »Es ist nicht nur mehr, als es Atome gibt auf der Erde. Es ist mehr als eine Billiarde-oft die Atome auf der Erde.«

Julien: »What the fuck?«

Rezo: »Eine Billiarde-oft die Erde sozusagen in Atomen: So viele Möglichkeiten gibt es, ein Kartendeck zu mischen.«

Julien: »Krass. Wie machen das dann Magier?«

Damit wird klar: Es gibt wirklich sehr, sehr viele verschiedene Möglichkeiten, 52 Spielkarten anzuordnen. Und trotzdem muss man mit seinen Aussagen vorsichtig sein. Denn wenn man jetzt herausfinden möchte, wie wahrscheinlich es ist, dass eine andere Person auf der Welt zufällig dieselbe Reihenfolge an Karten durch Mischen erzeugt, genügt es nicht, einfach nur $\frac{1}{52!}$ zu rechnen. Denn diese – unfassbar winzige – Zahl gibt an, wie wahrscheinlich es ist, eine ganz bestimmte Kartenmischung zu erhalten. Die eigentliche Fragestellung ist aber etwas subtiler: Wie wahrscheinlich ist es, dass zwei oder mehr beliebige Personen auf der Welt zufällig einen Kartenstapel gleich mischen?

Hat schon einmal jemand die Karten gleich gemischt?

Diese Frage erinnert an das Geburtstagsparadoxon. Dieses funktioniert nach demselben Prinzip: Es ist eher unwahrscheinlich, dass ein Schüler oder eine Schülerin einer Klasse an einem festgelegten Datum Geburtstag hat (bei 30 Personen beträgt die Wahrscheinlichkeit dafür $1-{\left(\frac{364}{365}\right)}^{30}\approx 7,9$ Prozent). Die Wahrscheinlichkeit hingegen, dass zwei am selben Tag geboren sind, beträgt mehr als 70 Prozent. Grund für diese scheinbare Unstimmigkeit ist, dass man in der Regel unterschätzt, wie viele mögliche Schülerpaare es gibt. Aus 30 Schülerinnen und Schülern lassen sich 435 Paare bilden. Die Wahrscheinlichkeit, dass jedes Schülerpaar an einem anderen Tag geboren ist, erscheint dann gar nicht mehr so groß.

Wenn man herausfinden will, wie wahrscheinlich es ist, ein Kartendeck zufällig so zu mischen wie irgendeine andere Person auf der Welt, gibt es dafür mehrere Möglichkeiten. Eine besteht darin, zunächst die Wahrscheinlichkeit für das gegenteilige Ereignis zu berechnen und dieses Ergebnis dann von eins abzuziehen. Das heißt, man untersucht zunächst, wie wahrscheinlich es ist, dass alle Menschen auf der Welt beim Mischen jeweils eine völlig neue Anordnung erzeugen (die erste Person hat dafür eine Wahrscheinlichkeit von 1, die zweite eine Wahrscheinlichkeit von $\frac{52!-1}{52!}$, die dritte von $\frac{52!-2}{52!}$ und so weiter). Und dieses Ergebnis zieht man dann von eins ab. Falls es acht Milliarden Menschen auf der Welt gibt, lässt sich die Wahrscheinlichkeit dafür, dass mehrere Personen dieselbe Kartenmischung erzeugen, folgendermaßen berechnen:

Das Problem ist: Mein Rechner (oder eher: das Online-Programm Wolfram Alpha) versagt mir den Dienst, wenn ich diese Formel auswerten möchte. Deshalb bin ich auf eine sehr grobe Abschätzung dieser Wahrscheinlichkeit angewiesen:

Das heißt, die Wahrscheinlichkeit, dass zwei oder mehr Menschen auf der Welt dieselbe Kartenanordnung erzeugen, entspricht weniger als 0,0000…08 Prozent – eine Zahl, die erst in der 47. Dezimalstelle von 0 abweicht.

Mit dieser beispielhaften Berechnung konnte ich hoffentlich jede und jeden davon überzeugen, dass es enorm unwahrscheinlich ist, dass mehrere Menschen auf der Welt zufällig die gleiche Kartenanordnung durch Mischen erzeugen. Aber jetzt haben Sie in Ihrem Leben wahrscheinlich nicht nur einmal Karten gemischt, sondern eher viele Male. Damit stellt sich die Frage: Wie verändert sich das Ergebnis, wenn man annimmt, dass jeder Mensch in seinem Leben etwa 100 Kartendecks mischt? Indem man die acht Milliarden in der vorigen Abschätzung durch 800 Milliarden ersetzt, erhält man folgendes Ergebnis: Die Wahrscheinlichkeit beträgt in dem Fall weniger als $8\cdot {10}^{-43}$ Prozent.

Das ändert nicht viel am Ergebnis: Auch wenn jeder Mensch auf der Welt 100-mal ein Kartendeck mischt, ist es sehr unwahrscheinlich, dass zweimal dieselbe Anordnung vorkommt.

Es ist wirklich extrem unwahrscheinlich, dass zwei Personen in der gesamten Geschichte der Menschheit jemals ein Kartenspiel gleich gemischt haben

Und deshalb möchte ich in einem letzten Schritt noch ein bisschen weitergehen und untersuchen, wie sich das Ergebnis verändert, wenn man nicht nur alle aktuell lebenden Menschen berücksichtigt, sondern alle Menschen, die jemals auf der Welt waren. Deren Anzahl wird mit 117 Milliarden abgeschätzt. Wenn man nun davon ausgeht, dass jede Person etwa 100-mal ein Kartendeck gemischt hat (was vermutlich eine maßlose Übertreibung ist, da es Spielkarten in dieser Form noch gar nicht so lange gibt), dann beträgt die Wahrscheinlichkeit, dass mehrmals die gleiche Anordnung entstand, weniger als $1,7\cdot {10}^{-40}$ Prozent.

Damit ist klar: Es ist wirklich extrem unwahrscheinlich, dass zwei Personen in der gesamten Geschichte der Menschheit jemals ein Kartenspiel gleich gemischt haben – zumindest, wenn man davon ausgeht, dass sie die Karten wirklich sorgfältig vermengt haben. Das verdeutlicht, wie groß 52! ist und wie enorm viele Möglichkeiten es gibt, 52 Karten anzuordnen. Das kann nicht nur die Fantasie beflügeln. Es hat in der Vergangenheit Online-Spiele-Entwickler vor ein handfestes Problem gestellt.

Karten mischen für den Computer

Beim Online-Poker kann es schnell um hohe Geldsummen gehen. Umso wichtiger ist es daher, dass die Karten in einem wirklich zufälligen Muster an die Spielerinnen und Spieler verteilt werden. Hierbei kommt es natürlich auf die Mischung an. In einer idealen Welt würde ein Algorithmus zufällig eine Anordnung aus den 52! möglichen Kartenstapeln auswählen. Allerdings hat kein Rechner genug Speicherplatz, um all diese Möglichkeiten zu auszuwerten – und einen perfekten Zufallsgenerator gibt es bislang auch nicht. Deshalb greifen Entwickler in der Regel auf Algorithmen zurück, die das Kartenmischen simulieren.

Die ehemalige Entwicklerplattform ASF Software hatte Ende der 1990er Jahre mehrere Online-Poker-Anbieter wie PlanetPoker mit Algorithmen zum Kartenmischen versorgt. Eine dieser Websites hatte den Algorithmus sogar veröffentlicht – als Beweis dafür, dass das Spiel wirklich verlässlich programmiert sei. Darüber stolperten einige Mitarbeiter von Reliable Software Technologies, einer IT-Firma. »Als wir den Mischer-Algorithmus sahen, ahnten wir sofort, dass es ein Problem geben könnte«, schrieben die Mitarbeiter in einem Beitrag. »Eine kleine Untersuchung bewies, dass unsere Intuition richtig war.«

Der Algorithmus startete jedes Mal mit einem geordneten Kartendeck und tauschte dann in mehreren Schritten je zwei Karten untereinander aus. Dafür nutzte das Programm einen Zufallsgenerator, der an die Systemzeit des Computers gekoppelt war, um eine zufällige Eingabe zu erzeugen. Dabei gab es allerdings einige Probleme: Der Austausch-Mechanismus war so implementiert, dass gewisse Kartenanordnungen bevorzugt wurden und mit höherer Wahrscheinlichkeit auftauchten. Und da die Systemzeit täglich um Mitternacht zurückgesetzt wird, schränkte das die möglichen Zufallswerte ein. Wie die Mitarbeiter von Reliable Software Technologies herausfanden, konnten auf diese Weise nur etwas mehr als 86 Millionen Anordnungen entstehen.

Tatsächlich konnten die Programmierer die mögliche Anzahl an Kartenanordnungen noch weiter einschränken, indem sie die Systemzeit der Poker-Server auslasen. Auf diese Weise blieben nur noch 200 000 Kartendecks übrig, die der Algorithmus erzeugen konnte. »Nach diesem Schritt gehört das System uns, da die Suche in dieser winzigen Menge von Mischungen trivial ist und auf einem PC in Echtzeit durchgeführt werden kann«, schreiben sie – und das schon in den 1990er Jahren, als die Leistung von Computern deutlich geringer ausfiel als heute.

Die Mitarbeiter von Reliable Software Technologies teilten dem Entwickler des betreffenden Algorithmus die Schwachstellen mit, der die Programme sogleich überarbeitete. Heute greifen viele Online-Poker-Webseiten auf den »Fischer-Yates-Algorithmus« zurück, auch Knuth-Shuffle genannt (klingt wie ein Tanz). Das ist leicht umzusetzen und liefert zufriedenstellende Ergebnisse. Eine perfekte Mischung erzeugen auch diese Algorithmen nicht – dafür sind die Zufallsgeneratoren nicht gut genug. Doch auch ein Mensch wird niemals ein ideales Ergebnis liefern, vermutlich nicht einmal die geübtesten Dealer.