Wie funktionieren Zufall auf einem Computer, was sind gute Zufallszahlen, wie erzeugt man diese und was ist ein RNG? In diesem Artikel wollen wir erklären, wie man Zufall, oder zumindest Pseudo-Zufall, auf einem Rechner erzeugt.
Wenn ein Computer Karten für das Pokerspiel mischt, ist es äußerst wichtig, dass er auch gut mischt. Sprich: Man sollte nicht vorhersagen können, welche Karten wo im Deck sind und jeder Spieler sollte auf lange Sicht alle Karten mit der selben Frequenz erhalten. Wie man es nicht machen sollte, demonstrierte Planet Poker Ende der Neunziger.
Ohne einen echten physikalischen Zufallszahlengenerator ist es unmöglich, auf einem Computer echte Zufallszahlen zu erzeugen. Aber glücklicherweise reicht es schon aus, wenn man Zahlen erzeugen kann, die zufällig aussehen und nicht vorherbestimmt werden können. Mit Hilfe solcher Zahlen kann man Decks beim Poker mischen und einen für alle Spieler fairen Deal sicherstellen.
Methoden, die auf einem Computer solche zufällig aussehenden Zahlen erzeugen, werden Pseudozufallszahlen-Generatoren genannt und wie diese funktionieren, soll hier erläutert werden.
Wie funktioniert ein Zufallszahlengenerator?
Um zu verstehen, wie ein Zufallszahlengenerator (kurz RNG) auf einem Computer funktioniert, schauen wir uns ein ganz einfaches Beispiel an.
Der hier vorgestellte Algorithmus (die Mittelquadratmethode ) stammt von John von Neumann und auch wenn dieser ziemlich viele Makel hat, ist er dennoch sehr instruktiv.
Der Algorithmus stammt aus den vierziger Jahren und diente vor allem dazu, möglichst schnell halbwegs zufällig aussehende Zahlen für Tests auf dem ENIAC zu erzeugen.
So funktioniert der Algorithmus:
1. Man nehme eine beliebige vierstellige Zahl (etwa 4567).
2. Man quadriere diese Zahl (heraus kommt 20857489).
3. Man streiche die beiden vorderen und hinteren Ziffern weg (8574).
4. Man hat eine neue vierstellige Zahl und wiederholt damit den Algorithmus um neue Zahlen zu erzeugen.
Lässt man den Algorithmus ein wenig laufen, produziert er (ausgehend von 4567) folgende Zahlen: 8574, 5134, 3579, 8092, 4804, 0784, 6146, 7733, 7992, 8720, 0384, 1474 – das sieht auf den ersten Blick schon ziemlich zufällig aus und für ein paar Tests, bei denen man zufällige vierstellige Zahlen braucht, reicht das auch.
Seed und Periode
Die erste Zahl, die man in so einen Algorithmus reinsteckt, nennt man Seed. Füttert man einen RNG mit dem selben Seed, produziert er wieder die selben Zahlen. Deswegen versucht man, diesen Seed möglichst immer neu zu wählen, wenn man den RNG ein weiteres Mal laufen lässt.
Viele RNGs wählen als Seed die Systemzeit in Millisekunden, denn diese ändert sich hinreichend oft.
Nimmt man den obigen Algorithmus und lässt ihn etwas länger laufen, werden sich die ausgespuckten Zahlen irgendwann wiederholen. Fängt man etwa mit der 4567 an, kommt im 18. Schritt 4100 raus. Nach 4 weiteren Schritten (im 22.) kommt wieder 4100 raus und im Anschluss spuckt der RNG nur noch Zahlen aus, die er schon vorher einmal ausgespuckt hatte.
Wie viele Schritte es dauert, bis sich ein RNG wiederholt, nennt man die Periode des RNG. Je größer die Periode eines RNG ist, desto besser ist er in der Regel.
Der obige Mittelquadrat-Algorithmus hat bei fast allen Seeds eine sehr kurze Periode. Bei fast jeder initial gewählten vierstelligen Zahl wiederholt sich der Algorithmus nach spätestens 100 Schritten und bei einigen Seeds sofort (startet man etwa mit 1000, kommen den nächsten Schritten nur noch Nullen).
Güte eines Zufallszahlengenerators
Die Algorithmen von Zufallszahlengenratoren können von sehr unterschiedlicher Qualität sein. Die Länge der Periode ist ein Merkmal für die Güte von RNGs. Hier gilt ziemlich profan: Je länger, desto bester.
Moderne Algorithmen weisen Periodenlängen jenseits von 1030 Schritten auf. Sprich, diese können eine unglaubliche Anzahl von Zahlen erzeugen, ohne sich selbst in Schleifen zu wiederholen.
Ferner gibt es weitreichende Tests, die prüfen, ob die ausgespuckten Zahlen statistisch tatsächlich zufällig sind. Ein RNG, der Zahlen zwischen 0 und 100 produziert, sollte auf lange Sicht jede Zahl mit der gleichen Häufigkeit ausspucken, auch sollten alle Frequenzen (etwa 4, 6, 8 oder 97, 17, 60 in Folge) mit der gleichen Häufigkeit vorkommen.
Insgesamt gibt es über 100 statistische Tests, denen sich ein RNG unterziehen kann. Diese werden Big Crush Tests genannt und bei Zufallszahlengeneratoren, die alle diese Tests bestehen, sind die produzierten Zahlen statistisch nicht mehr von echten Zufallszahlen (etwa über einen physikalischen RNG erzeugt) nicht mehr zu unterscheiden.
Elementar ist aber auch die Wahl eines geeigneten Seeds für den Generator. Selbst der fortgeschrittenste RNG produziert immer wieder die selben Zahlen, wenn man den selben Seed wählt.
Wie man am Beispiel Planet Poker gesehen hat, kann ein zu kleiner Wertebereich für den Seed dazu führen, dass man die gemischten Decks korrekt vorhersagen kann.
Twister, Shifts und Whirlpools
Ein sehr geläufiger RNG Algorithmus ist der Mersenne Twister. Dieser extrem schnelle Algorithmus erzeugt stets 64 Zufallszahlen zwischen 0 und 4,3 Milliarden gleichzeitig und hat eine Periodenlänge von über 106000.
Initialisiert wird der Mersenne Twister über 64 auf andere Art und Weise gefundene Zufallszahlen. Entsprechend hat der Twister einen extrem hohen Wertebereich für den Seed und eine für praktische Zwecke de facto unendlich Periode. Einmal gestartet kann ein Mersenne Twister genügend Zufallszahlen erzeugen, um alle Pokerkarten dieser Welt für immer zu mischen, ohne dass er neu gestartet werden müsste.
Andere Algorithmen sind XOR-Shifts oder der Whirlpool, welcher zum Hashen verwendet wird.
Statistisch am sichersten sind jedoch physikalische Zufallsgeneratoren, da diese ohne weitere Eingaben zufällige Zahlen erzeugen. Dort, wo Zufallszahlen und RNG eine bedeutende Rolle spielen (etwa bei allen modernen Online-Kasinos und Pokerseiten) werden immer physikalische Zufallszahlengeneratoren verwendet. Im Mindesten ist ihr Anwendungsbereich das Bereitstellen von Seeds für andere Algorithmen, so dass diese über algorithmische RNGs die Karten mischen können.
PokerStars benutzt nicht nur einen physikalischen RNG, sondern greift auch User-Eingaben ab, um auf einem gesonderten Server die Decks zum Spielen zu mischen. Wie genau das Mischen der Karten bei PokerStars funktioniert, erklären wir im nächsten Artikel dieser Serie.
Dieser Artikel erschien auf PokerOlymp am 11.04.2016.
