Random Number Generator

Aus PokéWiki
(Weitergeleitet von RNG)
Navigation Suche
Lückenhaft.png   In diesem Artikel fehlen wichtige Informationen hinsichtlich Spielen. Du kannst ihn verbessern, indem du sie recherchierst und einfügst und anschließend diese Markierung entfernst. Nähere Angaben: Diese Spielmechanik muss ggf. an die Musterstruktur angepasst und aktualisiert werden.
Random Number Generator
ja 乱数ポケモン
en Pseudorandom number generation in Pokémon
Auftritte
Spiele RBG GSK RUSAFRBGSM DPPTHGSS SWS2W2 XYΩRαS
Erstmals in Erste Spielgeneration
Diese Spielmechanik kommt nur in den Spielen der Hauptreihe vor.

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 IS-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 IS-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

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 DezimalsystemsWikipedia-Icon werden Berechnungen in 32- bzw. 64-Bit-Systemen, wie es die meisten Pokémon-Spiele sind, in der Regel im HexadezimalsystemWikipedia-Icon ausgeführt. Statt nur die Ziffern 0-9 zu benutzen, werden dabei noch die Buchstaben A-F als zusätzliche Ziffern verwendet. So entsprechen beispielsweise die Zahlen B und 1E im Hexadezimalsystem den Zahlen 11 und 30 im klassischen Dezimalsystem.

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ärsystemWikipedia-Icon wesentlich einfacher als für das Dezimalsystem. Für bitweise Operationen wie die xorWikipedia-Icon-Funktion, die das Binärsystem benutzen, ist das Hexadezimalsystem also die maßgeblich bessere Wahl.

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 KongruenzgeneratorWikipedia-Icon da, oft abgekürzt mit LCRNG (vom engl. linear congruential random number generator). Ein LCRNG benötigt einen Startwert als Eingabe und wird beschrieben durch drei Zahlen m, a und b, wobei m nicht 0 und kein Teiler von a sein darf. Bei der Eingabe des Startwertes verwendet man den bereits zuvor ermittelten Seed. Der Algorithmus wird dann rekursiv wie folgt beschrieben:

[math]\displaystyle{ \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]\displaystyle{ \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]\displaystyle{ \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 IS-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]\displaystyle{ \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 IS 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]\displaystyle{ \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]\displaystyle{ \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]\displaystyle{ \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 IS-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 IS 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]\displaystyle{ \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 IS 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 IS, 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 IS 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.

Quellen

[1] [2] [3] [4]

Gen. I
Gen. II
Gen. III
Gen. IV
Gen. V
Gen. VI
Gen. VII
Gen. VIII