Random Number Generator
Ein Random Number Generator (abgekürzt "RNG") bezeichnet im Allgemeinen einen bestimmten Typ an mathematischen Algorithmen oder Programmen, die dafür zuständig sind, zufällige Zahlen mit einer gewissen Wahrscheinlichkeitsverteilung zu generieren. Übersetzt bedeutet dieser Begriff etwa „Zufallszahlengenerator“. Es ist ein ungelöstes Problem der theoretischen Informatik und der Mathematik, ob ein RNG realisierbar ist, der ohne Anfangseingabe auskommt. In der Praxis wird bei einem solchen Verfahren immer auf einen festgelegten, allerdings variablen Startwert (auch Seed genannt) zurückgegriffen, der dann das Generieren weiterer Zahlen ermöglicht. Aufgrund dieser Einschränkung ist ein RNG allerdings stets berechenbar und liefert nur scheinbar zufällige Werte, weswegen man oft auch von Pseudo-Zufall spricht.
Wie in vielen anderen Videospielen kommen auch in den meisten Pokémon-Spielen RNGs zum Einsatz. In den Spielen der Hauptreihe werden sie zum Beispiel verwendet, um bei Kämpfen gegen wilde Pokémon deren DV-Verteilung und deren Personality Value zu generieren. Letzterer bestimmt unter anderem, welches Wesen das Pokémon besitzt und ob es sich um eine schillernde Variante handelt. Die (oftmals sogar relativ leicht) berechenbare Natur von RNGs führt dazu, dass mit einem gewissen technischen Aufwand teils sehr präzise Vorhersagen über das Spielgeschehen getroffen werden können. Der Missbrauch dieser Spielmechanik macht es so in einigen Spielen möglich, die Spieldaten so zu manipulieren, dass sich beispielsweise Pokémon mit perfekten DV-Werten fangen lassen. Dieser als "RNG abuse" bekannte Exploit wird weiter unten diskutiert.
Einsatzgebiete
RNGs bestimmen in den Pokémon-Spielen der Hauptserie das Auftreten zufälliger Ereignisse. Dies ist immer dann der Fall, wenn etwas nicht sicher, sondern nur mit einer bestimmten Wahrscheinlichkeit ausgelöst wird. Sie sind somit verantwortlich für einen großen Teil des gesamten Spielgeschehens. Einige der wichtigsten Einsatzgebiete aus verschiedenen Spielen, wenn auch bei weitem nicht alle, sind zum Beispiel
- Die Generierung aller Daten über ein wildes Pokémon zu Kampfbeginn, also
- seine Spezies
- sein Level
- seine DV-Verteilung,
- seinen Personality Value, welcher je nach Generation unter anderem das Wesen, das Geschlecht und die Fähigkeit bestimmt und ob es sich bei ihm um eine schillernde Variante handelt
- die Generierung zufälliger Faktoren im Pokémon-Kampf, also zum Beispiel
- den zufälligen Schadensmultiplikator (mehr dazu siehe im Artikel Schaden)
- das Landen von Volltreffern
- das Fehlschlagen von Attacken (mehr dazu siehe im Artikel Genauigkeit)
- das Auftreten von Statusveränderungen, wie beispielsweise Schlaf, Verwirrung oder Paralyse
- die Bestimmung zufälliger Werte beim Fangen eines Pokémon (mehr dazu siehe im Artikel Fangchance)
- Der Zufall in verschiedenen Minispielen, wie beispielsweise bei der Lotterie
- das ungewöhnliche Auftreten einer bestimmten Spezies zum Beispiel bei Schwärmen, im Großmoor oder im Trophäengarten
Hintergrund
Um die in Pokémon-Spielen eingesetzten RNGs genauer beschreiben zu können, müssen zunächst einige Begriffe erklärt werden. Vorab sei aber angemerkt, dass Zufallszahlengeneratoren im Allgemeinen keineswegs einem bestimmten Schema folgen müssen. Jeder Algorithmus, der aus einer vorgegebenen Liste an Zahlen eine Folge von diesen auswählt, sodass alle Zahlen mit gleich großer Wahrscheinlichkeit ausgewählt werden, ist ein Zufallszahlengenerator. Somit sind die im Folgenden aufgeführten Varianten nicht implizit für einen RNG, sondern nur die in Pokémon-Spielen vertretenen.
Der Seed
Wie schon in der Einleitung erwähnt, ist die tatsächliche Erzeugung zufälliger Zahlenfolgen nur durch eine Computer-Simulation nicht möglich. Ein RNG-Algorithmus benötigt vor der Ausführung stets einen Startwert, der vollständig die durch den Algorithmus generierte Zahlenfolgen bestimmt. Dieser Startwert wird in der Informatik auch Seed (engl. für Samenkorn) genannt. Weil der Seed alleine dafür verantwortlich ist, wie die Zahlenfolge generiert wird, und der gleiche Seed immer mit derselben Folge einhergeht, spricht man auch von der Pseudozufallsfolge zum jeweiligen Seed.
Der Seed selbst kann nicht komplett algorithmisch bestimmt werden. Daher wird bei seiner Bestimmung in der Regel auf einen physikalischen Zufallszahlengenerator zurückgegriffen, also auf eine physikalisch bestimmbare Größe; anschaulich gesprochen könnte hier etwa eine Münze oder ein Würfel geworfen werden. In der Praxis wird hier oft auf Spannungsschwankungen oder ähnliche elektrische oder mechanische Phänomene zurückgegriffen. Die einfachste Methode, die auch in den Pokémon-Spielen verwendet wird, ist der Zugriff auf die interne Uhrzeit. Je nach verwendeter Methode und Anwendung werden die physikalisch ermittelten Werte noch mathematisch modifiziert. Am Ende dieses Prozesses steht dann der Seed als Zahl fest und der richtige Algorithmus kann gestartet werden.
Hexadezimalsystem
Anstelle des üblichen Dezimalsystems
Um zwischen der üblichen Schreibweise für Zahlen und ihrer Schreibweise im Hexadezimalsystem zu unterscheiden, benutzen wir das Präfix 0x zur Kennzeichnung des Hexadezimalsystems. Somit entspricht beispielsweise die 9 der 0x9, aber die 10 entspräche nicht der 0x10.
Für arithmetische Operationen wie Addition, Multiplikation und Modulrechnung (siehe weiter unten) ist die Wahl der Basis des Systems im Prinzip irrelevant. Allerdings ist die Umrechnung von Zahlen zwischen Hexadezimalsystem und Binärsystem
Algorithmen
Im Folgenden werden für die Pokémon-Spiele relevante Arten von RNG-Algorithmen aufgeführt. Zum besseren Verständnis empfiehlt es sich, zunächst die arithmetische Modulo-Operation zu erklären: Für zwei Zahlen x und n ist mit x mod n (sprich: x Modulo n) der Rest gemeint, der entsteht, wenn man x durch n teilt. Beispielsweise ist damit 4 = 19 mod 5. Dieses Verfahren funktioniert ebenfalls im Hexadezimalsystem, es lässt sich also auch beispielsweise 0x5 = 0x1B mod 0xB schreiben.
LCRNG
Eines der am häufigsten verwendeten und gleichzeitig am einfachsten zu verstehenden Beispiele für einen Zufallszahlengenerator stellt der Lineare Kongruenzgenerator
[math]\begin{align} r_0 = a \cdot \text{Seed} + b \mod m \\ r_{i+1} = a \cdot r_{i} + b \mod m \end{align}[/math]
In jedem Schritt wird also eine Zahl generiert, die stets durch das gleiche Verfahren aus der vorherigen folgt. Hieran erkennt man auch sehr gut, warum man nur einen Pseudo-Zufall vorliegen hat, denn alle Zahlen der Folge sind bereits eindeutig bei der Eingabe des Seeds bestimmt. Falls klar ist, dass zu Beginn dieses Verfahrens ein Seed verwendet wurde, wird zur Beschreibung des Algorithmus lediglich die zweite Zeile verwendet.
An zwei einfachen Beispielen wird klar, dass allerdings nicht jeder so beschriebene Algorithmus auch sinnvoll implementiert werden kann: Betrachtet man zunächst für einen beliebigen Seed und ein beliebiges m den LCRNG-Algorithmus
[math]\begin{align} r_{i+1} = 1 \cdot r_i + 1 \mod m \end{align}[/math]
ist klar, dass der Algorithmus lediglich in chronologischer Reihenfolge und Endlosschleife die Zahlen von 0 bis m-1 durchläuft, beginnend beim gewählten Seed. In diesem Extremfall ist also augenscheinlich klar, dass die Zahlenfolge nicht wirklich zufällig ist. Ein anderes Problem tritt beispielsweise bei folgendem LCRNG-Algorithmus auf:
[math]\begin{align} r_{i+1} = 2 \cdot r_i + 2 \mod 6 \end{align}[/math]
Bei diesem Algorithmus können, abgesehen vom Seed, lediglich die Zahlen 0, 2 und 4 auftreten, aber nicht die Zahlen 1, 3 und 5. Einen RNG-Algorithmus, bei dem jede mögliche Zahl mindestens einmal auftreten wird, nennt man zyklisch. Die oben beschriebene Vorschrift ist also nicht-zyklisch. Für ein Pokémon-Spiel wäre ein nicht-zyklischer LCRNG-Algorithmus nicht geeignet, da das Nichtauftreten bestimmter Zufallszahlen beispielsweise bestimmte DV-Verteilungen unmöglich machen könnte. Entsprechend wird in den Pokémon-Spielen der Hauptreihe stets ein zyklischer LCRNG benutzt.
Mersenne-Twister
Der Mersenne-Twister ist ein wesentlich komplexerer RNG-Algorithmus, der speziell für 32-Bit-Systeme entwickelt ist. Der Seed muss aus 624 einzelnen 32-Bit integers bestehen, also 624 Hexadezimalzahlen zwischen 0x00000000 und 0xFFFFFFFF. Der Algorithmus erzeugt dann wiederum 624 neue 32-bit integers. So müssen immer erst dann neue Zahlen generiert werden, sobald alle vorherigen Zahlen genutzt worden sind. Im oben beschriebenen Sinne ist der Mersenne-Twister ebenfalls zufällig, also kann unabhängig vom Seed jeder erwartbare Wert irgendwann eintreten.
In den Spielen
1. & 2. Generation
In den Spielen der ersten sowie zweiten Generation gab es noch keinen algorithmischen RNG im oben beschriebenen Sinne. Stattdessen wurde auf einen im Game Boy implementierten mechanischen Zufallsgenerator zurückgegriffen, um zufällige Ereignisse in den Spielen zu bestimmen.
3. Generation
In allen Spielen der dritten Generation , also Rubin, Saphir, Feuerrot, Blattgrün und Smaragd, wurde erstmals ein RNG in Form eines Linearen Kongruenzgenerators eingeführt. Aus unterschiedlichen Gründen, die vor allem mit einer verhältnismäßig einfachen Seedfindung zusammenhängen, ist diese Generation besonders anfällig für RNG abuse.
Da alle Spiele mit 32-bit integers arbeiten, sind die Seeds und Zufallszahlen stets Werte zwischen 0x00000000 und 0xFFFFFFFF.
Der Seed
Die Generierung des Seeds erfolgt über eine Formel, die die genaue Uhrzeit der inneren Systemuhr zum Zeitpunkt des sechsten Frames nach Starten des Spiels verwendet. Eine Ausnahme bildet hierbei Smaragd, bei dem der Seed vollkommen unabhängig von der Systemuhr immer auf 0x00000000 gesetzt wird. Warum diese Änderung bei Smaragd im Gegensatz zu den Vorgängern vorgenommen wurde, ist nicht bekannt.
Stark vereinfacht wird die Bestimmung des Seeds in Rubin und Saphir,, sofern die innere Systemuhr bereits abgelaufen ist. Dieser Fehler wird einem im Spiel angezeigt, da dies auch unter anderem zur Folge hat, dass Beeren in den Spielen nicht mehr wachsen können, siehe dazu auch hier. In diesem Fall nimmt der Seed ähnlich wie in Smaragd stets einen festen Wert an, nämlich 0x000005A0.
Der Algorithmus
Der verwendete Algorithmus ist der folgende LCRNG:
[math]\begin{align} r_{i+1} = 0x41C64E6D \cdot r_i + 0x00006073 \mod 2^{32} \end{align}[/math]
Dieser Algorithmus ist aufgrund mathematischer Eigenschaften zyklisch, somit wird bei beliebig langer Laufzeit unabhängig vom Seed jeder Wert zwischen 0x00000000 und 0xFFFFFFFF angenommen. Befindet sich der Spieler außerhalb eines Kampfes oder im Menü generiert der Algorithmus automatisch einmal pro Frame eine neue Zufallszahl, im Kampf passiert dies zwei Mal pro Frame. Bei Ereignissen, die die Zufallszahlen abrufen, wird zusätzlich dazu immer eine zusätzliche Zahl an Zufallszahlen generiert und dann auf eine oder mehrere dieser generierten Zahlen zurückgegriffen. Hier sorgt die folgende Tabelle für eine Übersicht über manche Abläufe des RNG:
| Ereignis | Zeitpunkt | Anzahl zusätzliche Generierung | Zufallszahlen | Beschreibung |
|---|---|---|---|---|
| Bestimmung der Trainer-ID | Im Blackscreen, kurz bevor der Spieler im LKW steht | 3 | 0x???????? 0xaaaa???? 0xbbbb???? | Die Zahl bbbb ist die im Spiel sichtbare Trainer-ID, die Zahl aaaa ist die unsichtbare Trainer-ID, die sich auch über den Verlauf des Spiels nicht ändert |
| Erscheinen eines wilden Pokémon | Jedes Mal, wenn man ein Feld im hohen Gras betritt | 2 (3, wenn man das Gras betritt) | (0x????????) 0x???????? 0xaaaa???? | Ist die Zahl aaaa mod 2880 < 320 beginnt ein Kampf mit einem wilden Pokémon |
| Bestimmung von Spezies, Wesen und Level des wilden Pokémon | Sofort nachdem der Kampfbeginn festgelegt wurde | 3 | 0xaaaa???? 0x???????? 0xbbbb???? | Die Zahl bbbb mod 100 bestimmt das Level und die Spezies des Pokémon durch im Spiel hinterlegte Ablagen, aaaa mod 25 bestimmt das Wesen des Pokémon |
| Bestimmung des Personality Values | Nach Festlegung des Wesens | 2 (solange, bis die PID zum Wesen passt) | 0xaaaa???? 0xbbbb???? | Wenn die Zahl 0xbbbbaaaa mod 25 dem bereits festgelegten Wesen des Pokémon entspricht, wird diese Zahl zur PID |
| Bestimmung der DVs | Nach Festlegung des PIDs | 2 | 0xaaaa???? 0xbbbb???? | Die Zahl 0xbbbbaaaa wird ins Binärsystem übertragen und anschließend in 5er-Blöcke unterteilt. Der erste Block bestimmt den Initiative-Wert, gefolgt von Spezial-Angriff, Spezial-Verteidigung, KP, Angriff und Verteidigung |
4. Generation
In der vierten Generation wurde weitestgehend das Verfahren aus der vorherigen Generation benutzt. Sogar die genauen Zahlen eines LCRNG wurden übernommen. Da diese Generation allerdings erstmals auf das DS-System zugreifen konnte, konnte die Systemuhr erstmals verstellt werden, was RNG abuse wesentlich vereinfachte.
Der Seed
Wie auch in der Generation zuvor wird die sekundengenaue Uhrzeit des jeweiligen DS-Systems zur Ermittlung des Seeds benötigt. Zusätzlich dazu kam aber ein weiterer physikalischer Faktor, der den Seed beeinflussen konnte: Der sogenannte „Delay“. Unter dem Delay versteht man die Zeit vom Starten des Spiels bis zum tatsächlichen Beginn des Spiels.
Der Algorithmus
Wie auch in der dritten Generation ist in dieses Spiel ein LCRNG integriert, der durch
[math]\begin{align} r_{i+1} = 0x41C64E6D \cdot r_i + 0x00006073 \mod 2^{32} \end{align}[/math]
gegeben ist. Zusätzlich zu diesem alten Bekannten wurde aber noch ein weiterer LCRNG eingefügt, der durch
[math]\begin{align} r_{i+1} = 0x6C078965 \cdot r_i + 0x00000001 \mod 2^{32} \end{align}[/math]
gegeben ist. Dieser neue RNG wird hauptsächlich verwendet, um das unregelmäßige Auftreten bestimmter Pokémon-Spezies zu bestimmen, also unter anderem in Schwärmen, im Trophäengarten und im Großmoor.
Über die bereits bekannten LCRNGs der vorherigen Generation hinaus wird in dieser Generation auch der Mersenne-Twister verwendet. Dieser wird zu Beginn des Spiels eingesetzt, um die (versteckte) Trainer-ID zu generieren. Ebenfalls kommt der Mersenne-Twister bei der Bestimmung des Personality Values von Pokémon zum Einsatz, die aus Eiern geschlüpft sind.
5. Generation
In der fünften Generation kamen mit Schwarz und Weiß die ersten Spiele, bei denen der RNG auf 64-bit integers umgerüstet worden sind. Die Zahlen sind also nicht mehr wie zuvor acht-, sondern sogar sechzehnstellig.
Der Seed
Der Seed wird in den Spielen der 5. Generation prinzipiell wie auch zuvor durch die interne Uhr des DS-Systems bestimmt, allerdings wurde der Delay in Schwarz 2 und Weiß 2 vollständig irrelevant.
Der Algorithmus
Aufgrund des Umrüstung auf ein 64-bit-System wurde der LCRNG-Algorithmus der Vorgänger abgeändert zu
[math]\begin{align} r_{i+1} = 0x5D588B656C078965 \cdot r_i + 0x0000000000269EC3 \mod 2^{64} \end{align}[/math]
Im Vergleich zur dritten Generation findet die Neubestimmung von Zufallszahlen nicht mehr mehrfach in jedem Frame statt, sondern nur noch bei vorgegebenen Aktionen. Dasselbe gilt auch für den integrierten Mersenne-Twister, der in dieser Generation auch zur Bestimmung der DV-Verteilung von wilden Pokémon dient. Außerdem entscheidet der Mersenne-Twister über das zufällige Bewegungsmuster von NPCs, weswegen die Bewegung von NPCs auch umgekehrt eine neue Generierung von Zufallszahlen zur Folge haben kann.
Dass die PIDs und die DVs von wilden Pokémon in dieser Generation unabhängig voneinander durch den Mersenne-Twister und den LCRNG neu generiert werden und die Generierung neuer Zufallszahlen im Vergleich zur dritten Generation kontrollierbar wurde, sorgt für eine Erleichterung des Betreibens von RNG abuse.
6. Generation
In der sechsten Generation erfolgte die Ermittlung des Seeds erstmals über ein internes RNG-Modul des Nintendo 3DS, was zu einer deutlichen Erschwerung des RNG abuse führt.
Der Algorithmus
Auch in der sechsten Generation wurde der bereits in Generation 5 eingesetze LCRNG
[math]\begin{align} r_{i+1} = 0x5D588B656C078965 \cdot r_i + 0x0000000000269EC3 \mod 2^{64} \end{align}[/math]
erneut verwendet.
RNG abuse
Wenngleich sämtliche Variablen eigentlich garantieren, dass immer zufallsbasierte Pokémon erscheinen und es kein für den Spieler erkennbares Muster gibt, so ist es dennoch möglich, durch Berechnungen genau bestimmen zu können, zu welchem Zeitpunkt im Spiel welches Pokémon auftaucht. Dies wird von einigen Spielern (ugs. auch als „RNGer“ bezeichnet) beispielsweise dazu genutzt, um gezielt Pokémon erscheinen zu lassen, die für das „Competitive Play“ geeignete Werte besitzen oder in jeder denkbaren Form andere Besonderheiten aufweisen. Wenn dank Knacken des Algorithmus vorhersehbar ist, bei welchem Seed und welcher Framezahl ein bestimmtes Pokémon erscheint, so ist auch ersichtlich, wann der RNG abuser das Spiel zu betreten hat und welche Aktionen er im Spiel auszuführen hat, um dieses Pokémon erscheinen zu lassen.
Das Ausnutzen dieser Spielmechanik sorgt seit Anbeginn für große Kontroversen in der Pokémon-Community. Während es für die meisten professionellen Spieler normal ist, Turnier-Pokémon über diese Methodik zu erhalten, so gibt es auch eine Gegenseite, die den RNG abuse als drastischen Eingriff in das Spiel definiert, der so nicht legitim sei und den Nutzern einen großen Vorteil gegenüber „ehrlichen“ Spielern verschaffe. Auf diese Diskussion gibt es bis heute keine eindeutige Antwort, da die Manipulation des RNG von Nintendo weder akzeptiert, noch abgelehnt wurde und beide Diskussionsseiten einen nicht von der Hand zu weisenden Standpunkt vertreten. Fakt ist einmal, dass natürlich ein zeitlicher Vorteil für den RNG abuser entsteht. Während ein Spieler ohne RNG-Erfahrungen in der 5. Generation im Schnitt 45 Minuten benötigt, ein für Turniere geeignetes Pokémon zu erhalten, so benötigt der „RNGer“ 15 Minuten. Daraus ist allerdings auch zu folgern, dass RNG abuser auf Turnieren selbst keinen direkten Vorteil besitzen, da ein normal züchtender Spieler auch die in einem Kampf wichtigen Werte wie gute DVs erreichen kann. Auf Turnierebene ist der RNG abuse also letztlich als eine Steigerung der Effizienz gegenüber dem normalen Spieler zu betrachten. Ob dies bedenklich ist, kann niemals eindeutig definiert werden. Weitere Informationen zur RNG-Manipulation in Generation 5 finden sich beispielsweise hier.
Beispiel
Der RNG abuser verwendet für seine Berechnungen meistens ein darauf spezialisiertes Programm, in das er seine Suchkriterien, wie zum Beispiel die Höhe der DVs, einzutragen hat. Daraufhin werden ihm die entsprechenden Werte vorgelegt, die er zu beeinflussen hat, damit das gewünschte Pokémon auftauchen kann. In diesem Beispiel werden die Pokémon-Editionen HGSS genutzt. Gesucht ist ein Larvitar mit dem Wesen „Hart“ Und 31 DVs auf jedem Statuswert. Das Resultat sind folgende Angaben:
| Variable | Wert |
|---|---|
| Zeit | 17:45:49 |
| Datum | 17.10.2015 |
| Delay | 491 |
| PID-Frame | 56 |
Zuvor geht der Spieler meist in das Gebiet, in welchem das Pokémon zu finden ist und speichert dort ab. Anschließend wird versucht, die Delay und die Zeit korrekt zu treffen, daher muss das Spiel zur richtigen Zeit gestartet werden und der Spielstand im richtigen Moment aufgerufen werden. Durch das Verstellen der Uhrzeit und des Datums ist es möglich auch auf unrealistischere Zeiten zu kommen. Ist dies geschafft, werden anschließend die Frames durch verschiedene Aktionen so weit erhöht, dass sie auf dem korrekten Wert liegen. Nun erscheint das Pokémon, indem z.B. Lockduft eingesetzt wird. Bei richtiger Ausführung sollte dieses nun die vom Nutzer gewünschten Werte besitzen. Da es viel Übung erfordert, die korrekte Zeit, Delay und Framezahl zu treffen, ist allerdings auch nicht ausgeschlossen, dass der Versuch des Öfteren neu gestartet werden muss, bis sich ein Erfolg einstellt.