Zufall? Ich glaube nicht

petomka

Senior
21 Feb 2018
785
Hinweis: Dieser Beitrag geht tiefer in die Materie als üblich.

Zufall und Zufallsgeneratoren
Was ist Zufall? Sucht man im Internet nach der Definition, gibt der Duden einem folgende Definition:
etwas, was man nicht vorausgesehen hat, was nicht beabsichtigt war, was unerwartet geschah
Ich denke, die meisten würden dieser Aussage zustimmen. Es kann Zufall sein, dass jemand von euch morgen im Lotto gewinnt, genauso ist es Zufall, dass von euch morgen wahrscheinlich keiner im Lotto gewinnt. Da ist auch schon das nächste Schlagwort: Wahrscheinlichkeit. Auch hier gibt es im Duden eine Definition, allerdings nicht ganz so befriedigend wie die von Zufall:
Grad der Möglichkeit des Eintretens bzw. der Voraussagbarkeit eines Ereignisses
Auch dieser Aussage kann man - auch ohne große mathematische Kenntnisse - zustimmen.
Ein Computer kennt aber keinen Zufall, ein Computer berechnet exakte Ergebnisse (alles andere wäre auch fatal). Wenn ein Programmierer zufällige Werte haben möchte, muss er meistens auf Algorithmen zurückgreifen, die Pseudo-Zufallszahlen generieren. Pseudo (= möchtegern) deshalb, weil diese Algorithmen berechenbar sind.

Natürlich gibt es aber wie immer viele Wege zum Ziel. Es gibt verschiedene Umsetzungen von Zufallsalgorithmen. In diesem Artikel gehe ich aber nur auf die relevantesten Zufallsgeneratoren ein. Diese umfassen java.util.Random, java.security.SecureRandom und einen XOR-Shift-Generator. Am Ende gibt es noch einen Downloadlink zu einem kleinen Demo-Programm.

Bei Zufallsgeneratoren sind diese Eigenschaften besonders wünschenswert:
  • jede Zahl von 0 bis m-1 inklusive kommt mindestens einmal vor, bevor sich das Muster wiederholt
  • möglichst "statistisch zufällig"

java.util.Random
Wenn man selbst schon Erfahrungen mit Java gemacht hat, ist es - wahrscheinlich -, dass man schon mit java.util.Random in Kontakt gekommen ist. Dieser Generator verwendet eine relativ simple mathematische Formel:
next_random = (a * previous_random + c) mod m

a, c und m sind konstante Werte. Die Qualität der generierten Zufallszahlen hängt dabei von a, c und m ab. Man wählt entweder a als eine Potenz von zwei (leistungssparend, da nur Bitshiftoperation notwendig) oder m als Potenz von zwei (meistens die Registerbreite der Maschine, spart beim Modulorechnen). Der erste Wert für next_random, wenn noch keine Werte generiert wurden, ist der Seed. So einen Generator nennt man Linear Congruential Generator (LCG).

Aus der obigen Formel wird außerdem deutlich, dass wenn man eine Zufallszahl aus dem Generator hat, man direkt alle weiteren Zufallszahlen vorhersehen kann. Außerdem wiederholt sich das Muster der erzeugten Zufallszahlen nach maximal m Generationen (genannt Periode eines Generators).

Die Periode des java.util.Random Generators ist 2^48 (= 281.474.976.710.656). Das mag vielleicht für unsere Schatztruhen reichen, bei anderen Anwendungen könnte es aber zu Problemen führen. Wenn man z.B. zwei 32-Bit Zahlen generieren möchte, wären das 2^32 * 2^32 = 2^64 Möglichkeiten, was bedeutet, dass der Generator nicht alle Möglichkeiten produzieren kann (auch ein perfekter Zufallsgenerator mit Periode 2^48 könnte das nicht).

Außerdem stehen Kombination aus Werten (z.B. aus Koordinaten) immer in einem mathematischen Zusammenhang (wer sich genauer dafür Interessiert, kann in der Quelle nachlesen). Außerdem sind niederwertigere Bits "weniger zufällig" als höherwertige Bits.

qPbelZW.png

Bitmuster des niederwertigsten Bits mit Seed "Unl1m1t3dW0rld" aus dem Demo-Programm

Hier lassen sich einige Muster erkennen, das ist für einen Zufallsgenerator natürlich nicht gerade toll. Mit höherwertigeren Bits wird es dann schon besser. Das java.util.Random verwendet für die Generation von bool'schen Werten das 32. Bit.
Damit man noch einen Unterschied sieht, hier nochmal das gleiche Random, aber dieses Mal schauen wir uns das vierte Bit an:

HqdKH51.png

Bitmuster des viertniederwertigesten Bits mit Seed "Unl1m1t3dW0rld" aus dem Demo-Programm

Sieht, wie versprochen, schon deutlich besser aus, aber es lassen sich immer noch eindeutig Muster erkennen. Mit dem 32. Bit erkennt man dann zwar keine Muster mehr, der Zufall ist aber trotzdem - aus bereits genannten Gründen - nicht so toll.

java.security.SecureRandom
So einen Zufallsgenerator kann man also nicht verwenden, wenn man qualitativ hochwertige Zufallszahlen braucht, zum Beispiel beim Erstellen einer Verschlüsselung, oder bei einer Glücksspielanwendung. Eine Verbesserung stellt java.security.SecureRandom dar, welches kryptografisch sicher ist. Das bedeutet:
  • Wenn eine generierte Zahl des Generators bekannt ist, lässt sich nicht sagen, welche Zahlen bereits generiert wurden und welche Zahlen als nächstes generiert werden
  • Generierte Zahlen besitzen keine bekannte Tendenz
  • Der Generator besitzt eine sehr große Periode (die Standardimplementierung hat eine Periode von 2^160)
  • Der Generator kann an einer beliebigen Stelle innerhalb seiner Periode einen neuen Seed wählen
Um einen möglichst zufälligen Seed auszuwählen, stehen meistens mehrere Entropiequellen zur Verfügung. Diese könnten zum Beispiel sein:
  • Zeit zwischen Tastaturanschlägen
  • Zeit zwischen Mausbewegungen und deren Position
  • CPU-Auslastung/-Temperatur
  • Umgebungsgeräusche
Dabei kommt es natürlich darauf an, ob diese Quellen verfügbar sind (ist an der Maschine ein Mikrofon angeschlossen?), wie erreichbar diese Quellen innerhalb der Software sind und wie ergiebig bzw. zufällig diese Quellen sind.

Der Nachteil dieser hochwertigen Zufallszahlen ist, dass sie 20 bis 30 mal langsamer sind als z.B. ein LCG.

XOR-Shift-Generator
Im Demoprogramm ist noch ein dritter Algorithmus enthalten ("XOR-Generator"), welcher einen XOR-Shift-Generator implementiert. Dieser produziert trotz geringer Kosten mittelwertige Zufahlszahlen. Verschlüsselungs- und Hashalgorithmen verwenden ebenfalls solche simplen Bitoperationen, nur eben sehr viele davon. Auf dieser Technik setzt übrigens auch Java's SecureRandom auf. Die Periode dieses XOR-Generators ist 2^64 - 1.

Zufall bei Unlimitedworld
Nun, was hat das mit Unlimitedworld zu tun? Auch hier hängt einiges vom Zufall ab, zum Beispiel das Dialotto oder die Schatztruhen. Auch das ist natürlich nur Pseudozufall. Um den Zufall aber etwas zufälliger zu machen, habt ihr bei den Schatztruhen tatsächlich eine Wahl! In jeder Truhe befindet sich, bevor ihr sie öffnet, ein zuvor "zufällig" ausgewähltes Item. Dass ihr bald die Möglichkeit habt, zu sehen, was ihr verpasst habt, wurde bereits im Devblog zu den neuen Achievements angeteasert. Übrigens haben wir auch die Möglichkeit, die Items in euren Truhen zu sichten, während ihr euch entscheidet:

0kQXFzh.png

Da hatte jemand wohl eher weniger Glück.

Zufall bei Minecraft
Dass Zufallswerte nicht ganz zufällig sind, nutzt Minecraft aus, um aus einem Startwert eine Welt immer gleich zu berechnen. Zwei Welten mit demselben Startwert und derselben Minecraft-Version sind also immer nahezu identisch. Es gibt kleine Unterschiede bedingt dadurch, in welcher Richtung neue Bereiche erzeugt werden. Ein Baum kann z.B. aus einem Chunk herausragen und damit verhindern, dass dort ein anderer Baum erstellt wird. In der anderen Richtung wäre es vielleicht anders herum.

Minecraft speichert auch für jeden Spieler eine Zufallszahl, die für Verzauberungen benutzt wird. Sobald man eine Verzauberung durchführt, wird eine neue Zufallszahl aus dieser berechnet. Somit sieht man bis eine Verzauberung durchgeführt wird, immer dieselben Angebote für denselben Gegenstandstyp.
Beim Verzauberungstisch gibt es bei den Verzauberungen eine Anzeige mit Runen. Damit diese auch nach einem erneuten Einloggen dieselben Zeichen anzeigen, macht es sich Minecraft leider sehr einfach und benutzt dort zur Anzeige diese Zufallszahl. Damit das auch bei Servern funktioniert, sendet der Server dem Client die auf 32 bit gekürzte Zufallszahl zusammen mit den Verzauberungsangeboten.
Und weil Zufallszahlen wie oben beschrieben nicht wirklich zufällig sind, gibt es Crack-Programme, die daraus nach ein paar Versuchen den nächsten (und alle folgenden) Verzauberungsstartwerte berechnen können. Damit weiß man dann, in welcher Reihenfolge man vorgehen muss, um seine Wunschverzauberungen zu bekommen.
Auf Unlimitedworld haben wir das geändert, so dass beide Zufallszahlen unterschiedlich sind und etwas zufälliger erzeugt werden. Man kann hier also nicht ableiten, welche Verzauberungen man bekommt.

Das Demo-Programm
Für das normale Random und das XOR-Random wird der Hashcode des Seeds verwendet. Nur für SecureRandom wird der Seed in ein Byte-Array umgewandelt.

Das Demo-Programm auf GitLab: https://gitlab.com/petomka/randomvisualizer
Das Demo-Programm vorkompiliert: https://drive.google.com/open?id=1jwHfYz4JxYHHSKObfc86engLu_y5Qfbb

Quellen:
https://www.javamex.com/tutorials/random_numbers/java_util_random_algorithm.shtml
https://www.javamex.com/tutorials/random_numbers/lcg_bit_positions.shtml
https://www.javamex.com/tutorials/random_numbers/securerandom.shtml
https://www.javamex.com/tutorials/random_numbers/xorshift.shtml
 
Es gibt auch noch die Möglichkeit echte Zufallszahlen mithilfe bestimmter physikalischer Prozesse zu erzeugen.
Hierfür eignen sich besonders Ereignisse auf atomarer oder subatomarer Ebene , denn in der Quantenphysik gibt es zufällige Ereignisse, die prinzipiell unvorhersagbar sind.
Zum Beispiel:
Natürlich gibt es hierfür PC Komponenten, die sind meist aber sehr teuer und komplizierter zu verwenden als PRNGs.
Quantis-RNG-Products-500-x-400.png

Quelle
 
Ein sehr lesenswerter Beitrag!

Viele Systeme hängen vom "Zufall" ab (insbesondere die Kryptografie), deswegen ist dort eine verlässliche Quelle sehr wichtig.

Das TPM stellt unter anderem einen zuverlässigen RNG (Random Number Generator) für das System bereit.
 
  • Gefällt mir
Wertungen: petomka
Dass Zufallswerte nicht ganz zufällig sind, nutzt Minecraft aus, um aus einem Startwert eine Welt immer gleich zu berechnen. Zwei Welten mit demselben Startwert und derselben Minecraft-Version sind also immer nahezu identisch. Es gibt kleine Unterschiede bedingt dadurch, in welcher Richtung neue Bereiche erzeugt werden. Ein Baum kann z.B. aus einem Chunk herausragen und damit verhindern, dass dort ein anderer Baum erstellt wird. In der anderen Richtung wäre es vielleicht anders herum.

Minecraft speichert auch für jeden Spieler eine Zufallszahl, die für Verzauberungen benutzt wird. Sobald man eine Verzauberung durchführt, wird eine neue Zufallszahl aus dieser berechnet. Somit sieht man bis eine Verzauberung durchgeführt wird, immer dieselben Angebote für denselben Gegenstandstyp.
Beim Verzauberungstisch gibt es bei den Verzauberungen eine Anzeige mit Runen. Damit diese auch nach einem erneuten Einloggen dieselben Zeichen anzeigen, macht es sich Minecraft leider sehr einfach und benutzt dort zur Anzeige diese Zufallszahl. Damit das auch bei Servern funktioniert, sendet der Server dem Client die auf 32 bit gekürzte Zufallszahl zusammen mit den Verzauberungsangeboten.
Und weil Zufallszahlen wie oben beschrieben nicht wirklich zufällig sind, gibt es Crack-Programme, die daraus nach ein paar Versuchen den nächsten (und alle folgenden) Verzauberungsstartwerte berechnen können. Damit weiß man dann, in welcher Reihenfolge man vorgehen muss, um seine Wunschverzauberungen zu bekommen.
Auf Unlimitedworld haben wir das geändert, so dass beide Zufallszahlen unterschiedlich sind und etwas zufälliger erzeugt werden. Man kann hier also nicht ableiten, welche Verzauberungen man bekommt.
 
Echten Zufall könnte man auch über 1 Lichtquantum erzeugen, das durch einen halbdurchlässigen Spiegel gelenkt wird und jenachdem wo es ankommt, wird dann eine 1 oder 0 ausgespuckt. Ich glaube es gibt dafür auch schon entsprechende Hardware. Die Webseite random.org (die zum ermitteln der Vote Lotto Gewinner verwendet wird) verwendet wenn ich das richtig weiß Radiorauschen als Input.
 
Wieso kann man Schatztruhen stapeln, wenn jede etwas unterschiedliches enthält?
Technisch gesehen enthalten Schatztruhen gar nichts, sondern sind Spielerköpfe. Weil sie identische NBT-Daten haben, kann man sie stapeln. Diese NBT-Daten geben ihnen unter anderem die Truhentextur, aber das ist nur wie Farbe auf einem angemalten Klotz.
Der Schatztruhenkopf oder -klotz wirkt als Schlüssel, d.h. wenn er am einzig möglichen Ort platziert wird, löst er eine Funktion aus, die vier Inhalte generiert, von denen du dir einen aussuchen kannst.
 
Ich denke, die Truhe berechnet gar nichts. Mit ihr startest du nur den Vorgang, bei dem alles berechnet wird, die Gewinne sind nicht an ein spezielles Truhen-Item gebunden.
 
  • Gefällt mir
Wertungen: Sumpfhytte
Aber wenn man dann 4 Schatztruhen auf 1mal aufmacht, hat man ja keine Wahl mehr.
Werden dann einfach die Gewinne von einer truhe berechnet nur man bekommt sie alle?
Ja und Nein.
Wenn du 4 Truhen gleichzeitig öffnest, werden vom Server alle 4 Gewinne zufällig ausgewählt und du hast praktisch "keine Wahl mehr".
Öffnest du eine Truhe, werden vom Server vor der Öffnung 4 zufällige Gewinne gewählt und du kannst dich für eine entscheiden. Die anderen drei Gewinne werden verworfen.
Der Unterschied ist, dass bei der zweiten Variante der Zufallsfaktor Mensch hinzukommt.
 
Ja und Nein.
Wenn du 4 Truhen gleichzeitig öffnest, werden vom Server alle 4 Gewinne zufällig ausgewählt und du hast praktisch "keine Wahl mehr".
Öffnest du eine Truhe, werden vom Server vor der Öffnung 4 zufällige Gewinne gewählt und du kannst dich für eine entscheiden. Die anderen drei Gewinne werden verworfen.
Der Unterschied ist, dass bei der zweiten Variante der Zufallsfaktor Mensch hinzukommt.
Also gibt es keinen Unterschied in den Chancen auf wertvolle items zwischen den beiden Methoden
 
  • Gefällt mir
Wertungen: tth2507
Also gibt es keinen Unterschied in den Chancen auf wertvolle items zwischen den beiden Methoden

Für die einzelne Kiste betrachtet nicht, es werden ja mit dem selben Algorithmus die Inhalte der 4 Truhen bestimmt, ob du nun eine öffnest oder alle... Aber wenn du nur eine öffnest und „jedes Mal die falsche“ hast du schlechtere Chancen, als wenn du immer 4 Kisten auf einmal öffnest und damit jedes Mal alles nimmst, was der Algorithmus Dir zugedacht hat...
 
Aber wenn du nur eine öffnest und „jedes Mal die falsche“ hast du schlechtere Chancen, als wenn du immer 4 Kisten auf einmal öffnest
Hallo,
bei mir waren nach dem Öffnen einer Kiste auch schon nur 4 "schlechte" Gewinne zur Option (Gebratenes Huhn, Birkenholz, 5x Gebratenes Huhn, Fichtenstamm). Beim Öffnen von 4 Kisten gleichzeitig hätte ich dann die 4 "schlechten" Gewinne alle bekommen?

LG X38L.
 
  • Gefällt mir
Wertungen: tth2507

Benutzer, die dieses Thema gerade lesen

ONLINE 40 Spieler