Ein Zufallsgenerator im Web ... eine einfache Sache ? - Bastbox

Hier mal ein kleines Beispiel, was im Grunde genommen hinter meinen beiden phpBB Fan-Foren steckt.

Auf den ersten Blick mag man ja denken, ich baue mir hier rein zum Zeitvertreib und meiner allgemeinen Belustigung zwei tolle Hörspielforen. Dieser Grund lässt sich auch nicht leugnen. Ich musste einen Inhalt wählen und habe natürlich etwas gewählt, auf das ich Lust habe. So weit: Ok …

Hier aber mal ein augenscheinlich kleines Ding, das eigentlich auf den ersten Blick zu 100% der Bespaßung dient, jedoch letztlich eine Menge Dinge der Informatik beinhaltet. Das Ziel war eigentlich einfach und auch schön zugleich: Ein Zufallsgenerator der jeden Tag einen Hörspieltitel anzeigt (je Board) sollte her.

Es soll in jedem meiner beiden Fanforen jeden Tag zufällig ein Hörspiel der jeweiligen Serie ausgewählt und als Hörtipp angezeigt werden.
Dazu gibt es 2 Textdateien mit jeweils +- 200 Hörspieltiteln. Immer ein Titel pro Zeile.
In den beiden Listen stehen alle Hörspiele der Serie TKKG und der Serie Die drei Fragezeichen.
Jede Nacht um null Uhr wird eine neue Folge aus diesen beiden Listen ausgewählt und für 24 Stunden angezeigt.

Dann wird das nächste Hörspiel zufällig ausgewählt und so weiter…

Natürlich mit dem Punkt, dass die Listen jeweils einmal völlig abgearbeitet werden sollen und erst dann wieder von vorne beginnen (um zu vermeiden, dass “zufällig” ein Hörspiel mehrfach angezeigt wird, bevor nicht alle einmal an der Reihe gewesen sind).

Eigentlich klingt das einfach, plausibel und nach einer Menge Spielspaß.,

Im Einzelnen ist das alles auch kein Problem:

Einen zufälligen Titel (also eine Zeile aus der Textdatei) zu einer festen Uhrzeit anzuzeigen und auszugeben, ist einfach.
– Der Haken dabei: Es kann vorkommen, dass manche Titel mehrfach angezeigt werden, obwohl noch nicht alle an der Reihe waren.

Ebenso ist es kein Problem, Wiederholungen zu vermeiden. Man beginnt oben in der Liste und rutscht Zeile für Zeile nach unten bis zum Schluss. Dann beginnt man wieder von vorne.
– Der Haken: Die Titel werden in der Reihenfolge angezeigt werden, in der sie in der Liste stehen (Zeile 1, Zeile 2 usw.).

Beides gleichzeitig umzusetzen, ist hingegen etwas schwieriger: Es muss zufällig ein Titel ausgewählt und angezeigt werden, und das Skript muss sich merken, welche Titel bereits angezeigt wurden und welche nicht. Erst wenn alle Titel genau einmal zufällig ausgewählt wurden, beginnt der Vorgang von vorne. Dies zu programmieren ist für einen Anfänger, der genau verstehen möchte, was er tut, etwas herausfordernd.

Hier einmal die theoretischen Hintergründe, die jedoch notwendig sind, um dies zu realisieren:

Zufall in Computern: Eine einfache Erklärung
Wenn wir von “Zufall” in Computerprogrammen sprechen, meinen wir eigentlich etwas anderes als den echten Zufall, den wir aus dem Alltag kennen, wie zum Beispiel beim Würfeln oder Münzwerfen.

Was ist Computerzufall?
Computerzufall ist in Wirklichkeit “Pseudozufall”. Das bedeutet, die Zahlen scheinen zufällig zu sein, werden aber tatsächlich durch komplizierte mathematische Formeln berechnet. Man stelle sich vor, man hätte eine sehr lange Liste von Zahlen, die zufällig aussehen. Der Computer wählt also eigentlich “zufällig” eine Zahl aus dieser Liste aus. Aber “zufällig”? Ein Computer? Wie geht das !?

Wie funktioniert das?

Startwert (Seed): Der Computer braucht einen Ausgangspunkt, um seine Berechnungen zu beginnen. Dieser wird oft “Seed” genannt. Meist wird dafür die aktuelle Zeit in Millisekunden verwendet, da diese sich ständig ändert. (Damit ist also erst einmal kein Punkt innerhalb der Liste gemeint.)
Berechnung: Mit diesem Startwert und einer mathematischen Formel berechnet der Computer dann die “zufälligen” Zahlen.
Scheinbare Zufälligkeit: Für uns Menschen sehen diese Zahlen völlig zufällig aus, weil die Berechnungen so komplex sind, dass wir kein Muster erkennen können.

Ist das wirklich zufällig?
Streng genommen nein. Wenn man den exakt gleichen Startwert und die gleiche Formel verwendet, würde man immer die gleiche Folge von “Zufallszahlen” erhalten. Das ist der Grund, warum es “Pseudozufall” genannt wird.

Warum ist das trotzdem gut genug?

Praktische Anwendungen: Für die meisten Anwendungen, wie das Auswählen eines Liedes in einer Playlist oder das Mischen von Spielkarten in einem Computerspiel, ist dieser Pseudozufall völlig ausreichend.
Unvorhersehbarkeit: Für den normalen Benutzer ist es praktisch unmöglich vorherzusagen, welche Zahl als nächstes kommt.
Schnelligkeit: Diese Methode ist sehr schnell und effizient für Computer.

Gibt es auch “echten” Computer Zufall?
Für bestimmte Anwendungen, besonders in der Sicherheit und Verschlüsselung, ist echter Zufall wichtig. Hier verwenden Experten spezielle Methoden, die auf physikalischen Prozessen basieren, wie zum Beispiel das Messen von atmosphärischem Rauschen oder radioaktivem Zerfall.

Fazit
Wenn ein Computerprogramm also sagt, es wähle etwas “zufällig” aus, benutzt es in Wirklichkeit einen sehr komplexen, aber berechenbaren Prozess. Für die meisten Zwecke, wie das Auswählen eines täglichen Hörspieltitels, ist dieser Pseudozufall aber mehr als ausreichend. Er sorgt dafür, dass die Auswahl fair und für den Benutzer unvorhersehbar ist, auch wenn sie technisch gesehen auf Berechnungen basiert. Diese Art von “Zufall” ist zwar nicht perfekt, aber sie erfüllt ihren Zweck in den meisten alltäglichen Anwendungen hervorragend und ist ein faszinierendes Beispiel dafür, wie Computer komplexe Probleme auf kreative Weise lösen.

Eine einfache Berechnung für einen Pseudozufallszahlengenerator könnte wie folgt aussehen:

Man wählt einen Startwert (Seed) x0. Dies könnte zum Beispiel die aktuelle Zeit in Millisekunden sein.
Man wählt Konstanten a, c und m. Diese bestimmen die Eigenschaften des Generators.
Man berechnet die nächste Zahl in der Sequenz mit der Formel: x(n+1) = (a * x(n) + c) mod m
Die erzeugte Pseudozufallszahl ist dann x(n+1) / m, um einen Wert zwischen 0 und 1 zu erhalten.

Beispiel:

Parameter

Startwert (Seed): x0=12345×0=12345
Konstanten:
a=1664525a=1664525
c=1013904223c=1013904223
m=232=4294967296m=232=4294967296

Berechnungen

Erste Iteration:
x1=(a×x0+c)mod m=(1664525×12345+1013904223)mod 4294967296=3935559000
x1=(a×x0+c)modm=(1664525×12345+1013904223)mod4294967296=3935559000

Zweite Iteration:
x2=(a×x1+c)mod m=(1664525×3935559000+1013904223)mod 4294967296=797355205
x2=(a×x1+c)modm=(1664525×3935559000+1013904223)mod4294967296=797355205

Dritte Iteration:
x3=(a×x2+c)mod m=(1664525×797355205+1013904223)mod 4294967296=3957529789
x3=(a×x2+c)modm=(1664525×797355205+1013904223)mod4294967296=3957529789

Pseudozufallszahlen
Um die Pseudozufallszahlen zwischen 0 und 1 zu erhalten, teilt man die Ergebnisse durch mm: $m$ :

Diese Methode erzeugt eine Sequenz von Pseudozufallszahlen, die durch die Wahl der Konstanten und des Startwerts bestimmt wird. Sie wird häufig in Anwendungen verwendet, bei denen eine schnelle und einfache Generierung von Zufallszahlen benötigt wird.

Diese Methode wird als “Linearer Kongruenzgenerator” bezeichnet. Sie ist einfach zu implementieren, aber hat einige bekannte Schwächen und sollte nicht für kryptographische Zwecke verwendet werden. Für anspruchsvollere Anwendungen werden komplexere Algorithmen wie der Mersenne Twister verwendet, die auf ähnlichen Prinzipien beruhen, aber bessere statistische Eigenschaften aufweisen. Es ist wichtig zu verstehen, dass diese Berechnungen deterministisch sind – bei gleichem Startwert erhalten Sie immer die gleiche Sequenz von “Zufallszahlen”. Die Kunst besteht darin, die Parameter so zu wählen, dass die Sequenz möglichst lange und “zufällig” erscheint, bevor sie sich wiederholt.

Für Pseudozufallszahlengeneratoren werden häufig folgende Algorithmen verwendet:

Lineare Kongruenzgeneratoren (LCG):
Dies ist einer der einfachsten und am häufigsten verwendeten Algorithmen. Er basiert auf der rekursiven Formel:
x(n+1) = (a * x(n) + c) mod m
Dabei sind a, c und m Konstanten und x(0) der Startwert (Seed).
Mersenne Twister:
Ein sehr beliebter und weit verbreiteter Algorithmus, der eine sehr lange Periode (2^19937-1) und gute statistische Eigenschaften aufweist. Er wird in vielen Programmiersprachen als Standard-Zufallsgenerator verwendet.
Xorshift:
Eine Familie von Algorithmen, die auf XOR-Operationen und Bit-Verschiebungen basieren. Sie sind schnell und haben gute statistische Eigenschaften.
Blum Blum Shub:
Ein kryptographisch sicherer Pseudozufallszahlengenerator, der auf der Schwierigkeit der Faktorisierung großer Zahlen basiert.
Lagged Fibonacci Generator:
Basiert auf der Fibonacci-Folge, verwendet aber weiter zurückliegende Werte in der Sequenz.
Multiple-with-carry (MWC):
Eine Variante des Lagged Fibonacci Generators, die zusätzlich einen “Übertrag” verwendet.
WELL (Well Equidistributed Long-period Linear):
Ein verbesserter Algorithmus, der auf ähnlichen Prinzipien wie der Mersenne Twister basiert, aber einige seiner Schwächen behebt.
PCG (Permuted Congruential Generator):
Ein relativ neuer Algorithmus, der gute statistische Eigenschaften mit hoher Geschwindigkeit und kleinem Speicherbedarf kombiniert.

Diese Algorithmen unterscheiden sich in Bezug auf ihre Periodenlänge, statistische Qualität der erzeugten Zahlen, Geschwindigkeit und Speicherbedarf. Die Wahl des Algorithmus hängt von den spezifischen Anforderungen der Anwendung ab. Für die meisten alltäglichen Anwendungen sind einfachere Algorithmen wie LCG oder Mersenne Twister ausreichend, während für kryptographische Zwecke spezialisierte, sicherere Algorithmen bevorzugt werden.

Es gibt bei verschiedenen Pseudozufallszahlengeneratoren (PRNGs) bekannte Schwachstellen. Hier einige Beispiele:

Lineare Kongruenzgeneratoren (LCG):
Haben eine relativ kurze Periode
Weisen erkennbare Muster auf, besonders in niedrigeren Bits
Aufeinanderfolgende Zahlen können leicht vorhergesagt werden, wenn die Parameter bekannt sind
Mersenne Twister:
Ist nicht kryptographisch sicher
Der interne Zustand kann rekonstruiert werden, wenn genügend Ausgaben bekannt sind
Bei schlechter Initialisierung kann die Qualität der Zufallszahlen leiden, besonders wenn der Startwert zu viele Nullen enthält
Ältere Versionen des RAND()-Generators in verschiedenen Programmiersprachen:
Oft basierend auf einfachen LCGs mit bekannten Schwächen
Kurze Perioden und vorhersagbare Muster
Xorshift:
Einfache Varianten können in bestimmten statistischen Tests durchfallen
Nicht kryptographisch sicher
Blum Blum Shub:
Sehr langsam im Vergleich zu anderen PRNGs
Sicherheit hängt von der Schwierigkeit der Faktorisierung großer Zahlen ab.
Wenn die Systemzeit als einziger Seed verwendet wird, kann dies zu vorhersagbaren Ergebnissen führen, besonders wenn mehrere Instanzen kurz hintereinander gestartet werden.

Um diese Schwachstellen zu adressieren, werden oft folgende Ansätze verfolgt:

Kombination mehrerer Generatoren (hybride Generatoren)
Verwendung kryptographisch sicherer PRNGs für sicherheitskritische Anwendungen
Sorgfältige Auswahl und regelmäßige Aktualisierung des Seeds
Regelmäßige statistische Tests der generierten Zahlenfolgen

Für die meisten Anwendungen, die keine hohen Sicherheitsanforderungen haben, sind moderne PRNGs wie der Mersenne Twister trotz ihrer theoretischen Schwächen in der Praxis ausreichend. Für kryptographische Zwecke sollten jedoch speziell dafür entwickelte, sicherere Algorithmen verwendet werden.

Grundlegend – die Null-basierte Indizierung:

In der Informatik und Programmierung wird häufig mit der Null-basierten Indizierung gearbeitet, was bedeutet, dass die Zählung von Elementen in einer Liste oder einem Array bei Null beginnt. Diese Konvention hat sich aus mehreren Gründen etabliert:

In vielen Programmiersprachen, insbesondere solchen, die auf niedriger Ebene arbeiten wie C, entspricht der Index eines Arrays direkt einem Offset in einem Speicherblock. Der erste Index (0) zeigt auf den Anfang des Speicherblocks. Dies vereinfacht die Berechnung der Speicheradresse eines Elements, da keine zusätzliche Subtraktion erforderlich ist.
Die Null-basierte Indizierung stammt aus frühen Programmiersprachen wie C und hat sich in vielen modernen Sprachen fortgesetzt. Diese Tradition wurde beibehalten, um Konsistenz und Kompatibilität zu gewährleisten.
In der Mathematik und Informatik wird oft mit Mengen gearbeitet, bei denen die Null-basierte Indizierung natürlicher erscheint. Sie erleichtert auch die Implementierung von Algorithmen, die mit Intervallen oder Schleifen arbeiten.
Bei der Implementierung von Schleifen kann die Null-basierte Indizierung effizienter sein, da sie oft zu weniger Berechnungen führt und somit die Performance verbessern kann.

Diese Konvention ist also weit verbreitet und wird von vielen Entwicklern als Standard betrachtet, obwohl es auch Programmiersprachen gibt, die mit Eins-basierten Indizes arbeiten. (z.B.: Lua, MATLAB, Fortran)

So viel zu der eigentlichen Theorie. In meinem Falle habe ich es aber etwas anders gemacht (wobei die Basis eben beschrieben wurde):

Mein Script verwendet die PHP-Funktion array_rand() zur Zufallszahlengenerierung.

Hier eine genauere Erklärung, wie es funktioniert:

1. Auswahl eines zufälligen Titels:

Im Script passiert die zufällige Auswahl eines Titels durch den folgenden Code:

php

$randomIndex = array_rand($availableTitles);
$selectedTitle = $availableTitles[$randomIndex];

array_rand($availableTitles): Diese Funktion nimmt das Array $availableTitles, das alle verfügbaren Titel enthält, und wählt zufällig einen Schlüssel (Index) daraus.
$selectedTitle = $availableTitles[$randomIndex]: Hier wird der ausgewählte zufällige Schlüssel benutzt, um den dazugehörigen Titel aus dem Array auszulesen.

2. Wie generiert PHP diese Zufallszahl?

PHP verwendet zur Generierung von Zufallszahlen standardmäßig seinen internen Pseudo-Zufallszahlengenerator.

array_rand(): Diese Funktion nutzt intern die PHP-Zufallszahlengenerierung, die je nach PHP-Version unterschiedlich implementiert ist. Ab PHP 7 wurde array_rand() durch den CSPRNG (Cryptographically Secure Pseudo Random Number Generator) verbessert.

Alternative: mt_rand(): Wenn man explizit den Mersenne Twister Zufallsgenerator verwenden möchte, könnte man hier mt_rand() anstelle von array_rand() nutzen.

(mt_rand() verwendet den Mersenne Twister Algorithmus, der schneller und eine bessere Zufallsverteilung bietet. Ein Beispiel:

php

$randomIndex = mt_rand(0, count($availableTitles) – 1);
$selectedTitle = array_values($availableTitles)[$randomIndex];

Zusammenfassung:

In meinem Script wird also per array_rand() eine zufällige Auswahl eines Titels aus dem Array getroffen. Die Funktion verwendet den PHP-eigenen Zufallszahlengenerator, der keine direkte Implementierung des (Beispielsweise) Mersenne Twisters ist. Man könnte natürlicht auf mt_rand() umsteigen, um explizit den Mersenne Twister zu verwenden. (Das wäre aber für eine einfach Auswahl welches Hörspiel “heute” gehört werden könnte … “etwas übertrieben?!)

Das Skript im Hintergrund sieht dann so aus (ein Auszug):

Hinzu 3 Textdateien (pro Board):

Die Liste mit den Titeln (derzeit: 233 x TKKG, 229 x Drei ???)
Das Datum von immer “heute”.
Die Titel die schon gewesen sind (hier kommt also jede Nacht um 0 Uhr ein aus “1.” gewählter Titel hinzu)

Ist der 3. identisch mit dem 1., wird der 3. gelöscht und der Durchlauf beginnt erneut.
Da aber nur alle 24 Stunden gewechselt wird, würde das nach heutigem Stand bei TKKG nach 233 Tagen und bei den drei ??? nach 229 Tagen passieren.

Erklärung der PHP Funktion array_rand()

Die PHP-Funktion array_rand() ist ein nützliches Werkzeug zur Auswahl zufälliger Elemente aus einem Array. Hier sind die wichtigsten Aspekte dieser Funktion:
Funktionsweise.

array_rand() wählt einen oder mehrere zufällige Schlüssel aus einem übergebenen Array aus. Die Funktion gibt standardmäßig einen einzelnen zufälligen Schlüssel zurück, kann aber auch mehrere Schlüssel zurückgeben, wenn dies spezifiziert wird.

Die grundlegende Syntax lautet:

php
array_rand(array $array, int $num = 1)

$array: Das Eingabe-Array, aus dem zufällige Schlüssel ausgewählt werden sollen (erforderlich).
$num: Die Anzahl der zurückzugebenden Schlüssel (optional, Standard ist 1).

Rückgabewerte:

Bei Anforderung eines einzelnen Schlüssels wird ein einzelner Schlüssel zurückgegeben.
Bei Anforderung mehrerer Schlüssel wird ein Array von Schlüsseln zurückgegeben.

Besonderheiten und Einschränkungen:

array_rand() arbeitet nur mit eindimensionalen Arrays. Für mehrdimensionale Arrays müsste man also andere Lösungen implementieren.
Die Funktion gibt nur die Schlüssel zurück, nicht die Werte selbst. Um die Werte zu erhalten, muss man auf das ursprüngliche Array mit den zurückgegebenen Schlüsseln zugreifen.

Beispiel:

php
$fruits = array(“Apple”, “Banana”, “Cherry”, “Date”, “Elderberry”);
$random_keys = array_rand($fruits, 2);

echo $fruits[$random_keys[0]] . “\n”;
echo $fruits[$random_keys[1]];

Dieses Beispiel wählt zwei zufällige Früchte aus dem Array aus und gibt sie aus.

Alternativen:

Für bestimmte Anwendungsfälle, insbesondere wenn eine höhere Zufälligkeit erforderlich ist, können Alternativen wie mt_rand() in Betracht gezogen werden. Diese Funktion generiert Zufallszahlen etwa viermal schneller als die Standard-Zufallszahlengeneratoren. array_rand() ist eine einfache und effektive Methode zur Auswahl zufälliger Elemente aus Arrays, sollte aber mit Bedacht eingesetzt werden, insbesondere bei Anwendungen, die eine hohe Zufälligkeit erfordern.

Das Ergebnis in beiden Boards:

Fazit: Fertig! Wollen wir nur hoffen, dass morgen bessere Titel gewählt werden als die, die auf den beiden Bildern zu sehen sind. Die sind beide eher mittelmäßig.