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:
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:
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:
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.
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:
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:
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:
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
Zufall und Zufallsgeneratoren
Was ist Zufall? Sucht man im Internet nach der Definition, gibt der Duden einem folgende Definition:
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:
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.
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:
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
- Zeit zwischen Tastaturanschlägen
- Zeit zwischen Mausbewegungen und deren Position
- CPU-Auslastung/-Temperatur
- Umgebungsgeräusche
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:
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
