Het omkeren van de RNG in Factorio

Introductie

Met de release van de Space-Age DLC in Factorio zijn verschillende nieuwe mechanieken geïntroduceerd. Een belangrijk onderdeel hiervan is het concept van verschillende kwaliteiten voor items en gebouwen. Standaard worden items gemaakt met een 'gewone' (common) kwaliteit. Door kwaliteitsmodules te gebruiken in de productiemachines, is er een kleine kans om items van een hogere kwaliteit te verkrijgen.

Wat houdt dit in? Kort gezegd: items en gebouwen krijgen verbeterde statistieken, zoals snellere productiesnelheden, modules die sterkere buffs geven, stroommasten met een groter bereik en sneller bewegende inserters. Omdat dit zeer waardevol is, zijn we geïnteresseerd in het verkrijgen van de hoogst mogelijke kwaliteit voor onze items en gebouwen.

Om een groot aantal van dit soort items te verkrijgen, gaven de ontwikkelaars aan dat deze willekeur in feite neerkomt op "basisstatistiek" [1]; dat wil zeggen: als het volume aan kwaliteitsitems dat men verkrijgt groot genoeg is, zal de geobserveerde distributie van kwaliteiten dicht bij de verwachte distributie liggen.

Maar is dit de enige manier om op te schalen? Men zou zich kunnen afvragen: hoe is het mogelijk voor een deterministisch spel als Factorio om een willekeurige mechaniek te hebben?

Het korte antwoord is: het is niet willekeurig. In plaats daarvan maakt de simulatie gebruik van een pseudo-random number generator (PRNG), wat gebruikelijk is in de informatica. Een PRNG is een deterministisch algoritme dat een reeks getallen produceert die voor alle praktische doeleinden willekeurig lijken. Dit betekent dat de output een goed gedefinieerde distributie volgt zonder herkenbare patronen.

Normaal gesproken kan men in de informatica een PRNG behandelen als een 'black box'-functie die willekeurige getallen oplevert, zonder zich bezig te houden met de exacte werking. Maar door onder de motorkap te kijken, kunnen we iets interessants doen. Wat gebeurt er als we het exacte algoritme en de interne status kennen? Dan kunnen we hetzelfde algoritme uitvoeren op die status en exact dezelfde output verkrijgen als het spel intern doet.

Omdat het algoritme deterministisch is, zijn de outputs altijd hetzelfde. Hierdoor kunnen we gelijktijdig met het spel dezelfde berekeningen uitvoeren en toekomstige outputs van de PRNG voorspellen. Dit stelt ons in staat om toekomstige "willekeurige" gebeurtenissen in het spel te voorspellen, zoals welke productieprocessen een kwaliteitsverbetering zullen ondergaan.

In de volgende secties bouw ik dit uit: beginnend bij welke RNG het spel gebruikt, hoe deze te kraken is en hoe dit in het spel kan worden misbruikt. De achtergrond is begrijpelijk voor iedereen met een basiskennis van lineaire algebra.

Starten vanuit het niets

Hoe ontdek je welk PRNG-algoritme Factorio gebruikt? Er zijn immers verschillende implementaties waaruit gekozen kan worden. Mijn eerste stap was rudimentair internetonderzoek. Aangezien de Factorio-community groot is en vol zit met technisch onderlegde mensen, had iemand deze vraag waarschijnlijk al gesteld.

Na wat zoeken vond ik een post op de Factorio-forums van 11 jaar geleden. In die thread gaf Cube, een voormalig ontwikkelaar bij Wube, het volgende antwoord:

"We hebben gekozen voor taus88, voornamelijk omdat dit de snelste generator uit de Boost-bibliotheek is. Ik overwoog om een van de drie LFSR's te verwijderen (wat het ongeveer 40% sneller zou maken), maar dat heeft geen zin, aangezien de willekeurige getallen voor ons geen bottleneck vormen."

Dit gaf een concrete aanwijzing: de Boost.Random-bibliotheek. Daar vinden we de volgende (ingekorte) implementatie voor de taus88-generator:

typedef xor_combine_engine<
    xor_combine_engine<
        linear_feedback_shift_engine<uint32_t, 32, 31, 13, 12>, 0,
        linear_feedback_shift_engine<uint32_t, 32, 29, 2, 4>, 0>, 0,
        linear_feedback_shift_engine<uint32_t, 32, 28, 3, 17>, 0> taus88;

template<class UIntType, int w, int k, int q, int s>
class linear_feedback_shift_engine {
    // w = word size (bijv. 32 voor 32 bit uint)
    // k = aantal bits in de LFSR
    // q = feedback tap positie
    // s = aantal stappen per keer
    // wordmask() = 0b11...111; masker van w lage bits
    result_type operator()() {
        const UIntType b = (((value << q) ^ value) & wordmask()) >> (k-s);
        const UIntType mask = (wordmask() << (w-k)) & wordmask();
        value = ((value & mask) << s) ^ b;
        return value;
    }
}

Dit betekent dat taus88 bestaat uit drie linearfeedbackshift_engine waarvan de resultaten via XOR met elkaar worden gecombineerd. Deze engine staat meer algemeen bekend als een Linear Feedback Shift Register (LFSR).

Omdat het forumbericht al oud was, wilde ik de informatie controleren aan de hand van de meest accurate bron: het game-binary. Hoewel het spel closed source is, leveren de ontwikkelaars een .pdb-bestand met debug-symbolen mee. Hiermee kunnen we een geannoteerde decompilatie van het binary genereren. Ik gebruikte hiervoor Ghidra en later Binary Ninja.

In de code van het spel is de RandomGenerator klasse te vinden, waar getInt() als volgt is geïmplementeerd:

uint RandomGenerator::getInt(RandomGenerator *this) {
    uint a = this->seed1;
    uint b = this->seed2;
    uint c = this->seed3;
    a = (a << 12 ^ a >> 6) & 0x1fff ^ a >> 19 ^ a << 12;
    b = (b << 4 ^ b >> 23) & 0x7f ^ b >> 25 ^ b << 4;
    c = (c << 17 ^ c >> 8) & 0x1fffff ^ c >> 11 ^ c << 17;
    this->seed1 = a;
    this->seed2 = b;
    this->seed3 = c;
    return a ^ b ^ c;
}

Het valt op dat veel constanten uit de originele taus88-definitie zijn verdwenen; dit komt door compiler-optimalisaties (zoals constant folding). Echter, het feit dat er drie seeds worden opgeslagen en dat de uiteindelijke resultaat de XOR is van deze drie onafhankelijk bijgewerkte statussen, is een sterke aanwijzing dat dit inderdaad dezelfde generator is.

Om alle twijfel weg te nemen, heb ik beide varianten in Python herschreven en met sympy (een bibliotheek voor symbolische manipulatie) vergeleken. Een stap vooruit in beide varianten bevestigde dat alle bits van de registers op exact dezelfde manier worden bijgewerkt.

Conclusie: de RNG in Factorio is de taus88-generator, bestaande uit drie LFSR's. LFSR's staan erom bekend zwakke PRNG's te zijn; in de literatuur wordt zelfs gesteld dat ze "triviaal te breken" zijn [2]. Om te begrijpen waarom, moeten we kijken naar de onderliggende wiskunde.

Review van LFSR-wiskunde

Een Linear Feedback Shift Register (LFSR) modelleert een verzameling bits, samengevoegd in één waarde $x$: $x = x{n-1} \dots x2 x1 x0$

Elke individuele bit $xi$ is een binaire variabele waarbij $xi \in \{0, 1\} = \mathbb{F}2$. In plaats van $x$ te zien als een getal in het bereik $[0, 2^n - 1]$, is het nuttiger om het te beschouwen als een vector van individuele bits: $x \in \mathbb{F}2^n$.

We gebruiken twee operaties:

• $xi \oplus yi$: De XOR-operatie (addition modulo 2).
• $xi \cdot yi$: De AND-operatie (multiplicatie modulo 2).

In een shift register worden alle bits één positie naar beneden verschoven, waarbij de laagste bit als output wordt weggegooid. Om te voorkomen dat het register simpelweg leegloopt naar nul, voegen we feedback toe. Door de weggegooide bit terug te voeren naar de hoogste bit, creëren we een loop. Echter, dit is nog steeds zeer voorspelbaar omdat de sequentie zich elke $n$ stappen herhaalt.

Om dit tegen te gaan, voegen we lineaire feedback toe door de feedback-bit niet alleen aan de eerste bit, maar ook aan bepaalde tussenliggende bits (de taps) toe te voegen via XOR. De term "lineair" komt voort uit het feit dat de nieuwe bit-staten een lineaire combinatie zijn van de vorige staten. Deze lineariteit is precies de reden waarom we de interne RNG-status kunnen reconstrueren op basis van observaties alleen.

In de praktijk is de output van een RNG-aanroep vaak de volledige status van het register, die vervolgens als een integer in het bereik $[0, 2^n - 1]$ wordt geïnterpreteerd.

De cycluslengte van LFSR's

De cycluslengte is het aantal stappen voordat de status zich herhaalt. Voor een LFSR met $n$ bits is de maximale cycluslengte $2^n - 1$ (alle staten behalve de all-zero status). Dit wordt bereikt wanneer het feedback-polynoom $P(X)$ van graad $n$ primitief (en dus irreducibel) is.

LFSR's zijn lineair

Als we een symbolische representatie van de LFSR nemen, zien we dat elke bit op tijdstip $t+1$ altijd een combinatie is van de beginbits op tijdstip $t$.

De set bits $\mathbb{F}_2 = \{0, 1\}$ samen met de operaties $\oplus$ en $\cdot$ vormt een structuur die in de wiskunde een lichaam (field) wordt genoemd, specifiek het Galois-lichaam $\text{GF}(2)$. Een lichaam is een verzameling waarden met operaties die voldoen aan eigenschappen zoals associativiteit, commutativiteit, identiteit, inverse elementen en distributiviteit.

Waarom is dit belangrijk? Omdat een lichaam een voorwaarde is voor het bestaan van vectorruimtes. We kunnen de status van de LFSR beschouwen als een vector in de vectorruimte $\text{GF}(2)^n$. De overgang van de huidige status $s(t)$ naar de volgende status $s(t+1)$ kan dan worden geschreven als een matrixproduct: $s(t+1) = T s(t)$ waarbij $T \in \text{GF}(2)^{n \times n}$ de transitiematrix is.

Dit stelt ons in staat om de LFSR met meerdere stappen tegelijk vooruit te spoelen: $s(t+k) = T^k s(t)$

Voor de taus88-implementatie in Factorio resulteert dit in drie transitiematrices $T1, T2$ en $T_3$. Omdat de LFSR-grootte ($k$) kleiner is dan de word-size ($w=32$), zijn sommige kolommen in de matrix leeg (lineair afhankelijk), wat betekent dat de matrix in zijn 32x32 vorm strikt genomen niet inverterbaar is. Echter, door de matrix te reduceren tot de werkelijke LFSR-grootte (bijv. 31x31), herstellen we de volledige rang en wordt de matrix inverterbaar.

Een LFSR inverteren

Als we een LFSR kunnen inverteren, kunnen we vanuit de output de interne status afleiden. Als er een matrix $T$ bestaat voor een stap vooruit, kunnen we een matrix $T^{-1}$ construeren die de stap perfect terugdraait: $T^{-1} T = I$ (waarbij $I$ de identiteitsmatrix is).

Dit kan via constructie (door de datastromen in het diagram om te keren) of via Gauss-eliminatie. In $\text{GF}(2)$ is Gauss-eliminatie eenvoudig omdat er geen numerieke precisieproblemen zijn.

Inverteerbaarheid in taus88

Zoals eerder vermeld, zijn de matrices $T_i$ in taus88 niet direct inverterbaar in 32-bit formaat omdat de laagste bits lineair afhankelijk zijn van de hogere bits. Door de matrices te reduceren tot hun effectieve grootte (31, 29 en 28 bits), kunnen we de status herstellen. Zodra we de gereduceerde status hebben, wordt de volledige 32-bit status na één stap vooruit automatisch weer correct gevuld.

Meerdere LFSR's combineren

De uiteindelijke RNG-output is de XOR van drie onafhankelijke LFSR's. We kunnen dit modelleren door de drie statusvectoren $s1, s2, s3$ te stapelen in één grote vector $s$: $s(t+1) = \begin{bmatrix} T1 & 0 & 0 \\ 0 & T2 & 0 \\ 0 & 0 & T3 \end{bmatrix} s(t) = T s(t)$

De output $o(t)$ is de XOR van de drie statussen: $o(t) = \begin{bmatrix} I & I & I \end{bmatrix} s(t)$

Als we drie opeenvolgende outputs observeren, krijgen we het volgende stelsel vergelijkingen: $\begin{bmatrix} o(t) \\ o(t+1) \\ o(t+2) \end{bmatrix} = \begin{bmatrix} I & I & I \\ T1 & T2 & T3 \\ T1^2 & T2^2 & T3^2 \end{bmatrix} s(t) = A s(t)$

Om de status $s(t)$ te bepalen, hoeven we alleen de inverse van matrix $A$ te berekenen: $s(t) = A^{-1} \begin{bmatrix} o(t) \\ o(t+1) \\ o(t+2) \end{bmatrix}$

Implementatie-uitdagingen

Hoewel de theorie klopt, zijn er in-game uitdagingen:

1. Opeenvolgende aanroepen: We hebben consecutive outputs nodig, maar andere systemen in het spel kunnen ook RNG-aanroepen doen, waardoor onze observaties worden onderbroken.
2. Resultaatbreedte: We kunnen niet direct de volledige 32-bit output van een RNG-aanroep lezen. We kunnen alleen indirecte informatie verkrijgen (bijv. "is dit item geproduceerd?").

Opeenvolgende aanroepen

Dit kan worden opgelost door:

• Alle andere RNG-bronnen in het spel uit te schakelen.
• Gebruik te maken van sub-tick mechanics. In Factorio gebeuren gebeurtenissen binnen één tick in een vaste volgorde. Door onze "entropie-generatoren" in een blok te plaatsen in de wachtrij van de simulatie, dwingen we de RNG-aanroepen om gatloos te zijn.

Volledige resultaatbreedte (Entropie)

We gebruiken productierecepten met willekeurige outputs. De hoeveelheid informatie die we per aanroep verkrijgen, hangt af van de kans $p$ van de gebeurtenis. De verwachte hoeveelheid informatie (in bits) kan worden berekend als: $\mathbb{E}[\text{bits}] = p \lfloor -\log2(p) \rfloor + (1-p) \lfloor -\log2(1-p) \rfloor$

Dit is een gediscretiseerde versie van de Shannon-entropie. Analyse van de game-data laat zien dat recepten met een 50/50 kans de meeste informatie per aanroep opleveren. Recycling van repair packs is hiervoor ideaal: het is goedkoop, snel en geeft precies 1 bit informatie per resultaat.

De feitelijke implementatie

De implementatie is opgedeeld in vijf stappen:

1. Bemonstering van de huidige RNG via observaties.
2. Berekenen van de huidige interne RNG-status.
3. Voorspellen van toekomstige statussen.
4. Berekenen van de bijbehorende kwaliteitsniveaus.
5. Gebruikmaken van deze voorspellingen via "adapters".

Bemonstering van de RNG

Door repair packs te recyclen, verkrijgen we per operatie 2 bits informatie. We hebben in totaal 88 bits nodig om de status volledig te reconstrueren, wat neerkomt op 44 recycling-operaties.

Dit wordt uitgevoerd met een reeks van 44 eenheden. Om te garanderen dat de aanroepen in de juiste volgorde gebeuren, wordt gebruikgemaakt van same-tick shenanigans via een netwerk van combinators en vertragingen.

Bepalen van de huidige status

Omdat we slechts 1 bit per aanroep observeren (de meest significante bit), gebruiken we een aangepaste matrix-vector vermenigvuldiging in $\text{GF}(2)$. De matrix $\tilde{A}^{-1}$ kan vooraf in Python worden berekend en in Factorio worden geïmplementeerd met decider- en arithmetic combinators.

De berekening ziet er als volgt uit: $s(t+88) = \bigoplus{k=0}^{87} o(t+k) \cdot [\tilde{A}^{-1}]k$

In-game wordt dit gerealiseerd door de resultaten van de recycling-eenheden te XOR-en via "impliciete optelling" (het optellen van signalen en alleen de laatste bit behouden).

Vooruitkijken

Zodra de status bekend is, kunnen we toekomstige staten berekenen via $s(t+k) = T^k s(t)$. Ik heb gekozen om 1000 stappen vooruit te voorspellen in parallel. Dit wordt gedaan met een binaire boom van arithmetic combinators om de XOR-reducties snel uit te voeren.

Kwaliteitvoorspelling

De functie rollQuality in Factorio vergelijkt de RNG-rol met bepaalde drempelwaarden (thresholds). Omdat deze drempels constant zijn, kunnen we in-game berekenen welk kwaliteitsniveau een specifieke RNG-rol zal opleveren.

Adapters

Met deze voorspellingen kunnen we verschillende "adapters" bouwen:

• Quality Queue: Een display dat, net als in Tetris, de volgende kwaliteiten laat zien voordat het item klaar is.
• Sorted Quality: Een systeem dat items verdeelt over verschillende banden op basis van hun voorspelde kwaliteit.
• Legendarische Automatisering: Dit is het uiteindelijke doel. Omdat de RNG-sequentie deterministisch is, kunnen we "slechte" RNG-aanroepen verspillen (consumeren) totdat de volgende aanroep precies de waarde heeft die nodig is voor een legendarisch item.

Voor het verspillen van aanroepen wordt scrap recycling gebruikt, omdat dit zeer snel gaat en veel aanroepen (12 per craft) verbruikt. De exacte hoeveelheid scrap en gears die nodig is om een specifiek aantal aanroepen te 'skippen', wordt berekend met een specifieke formule die rekening houdt met productiviteitsbonussen.

Beperkingen

Kan dit in een normale save-game worden gebruikt? Waarschijnlijk niet.

De reden is dat de RNG-statussen globaal voor de gehele map zijn opgeslagen, maar er zijn meerdere RNG's. De generalRandomGenerator is verantwoordelijk voor item-creatie, maar wordt ook gebruikt door:

• Het willekeurig kiezen van vloertegels.
• Naamgevingsrandomisatie van labs en treinstops.
• Het spawnen van stofdeeltjes wanneer een speler loopt.
• Blikseminslagen op Fulgora.
• De plaatsing van poten van de Spidertron.

Elke keer als een van deze systemen de RNG aanroept, verandert de status en lopen de voorspellingen uit synchronisatie. Bovendien kunnen grote productielijnen duizenden aanroepen per seconde genereren, wat de rekenkracht van de in-game combinators overstijgt.

Factorio 2.1

In de nieuwste updates is de manier waarop RNG wordt gebruikt fundamenteel veranderd. Hoewel taus88 nog steeds wordt gebruikt, wordt één aanroep nu gedeeld over meerdere item-outputs. Bovendien gebruikt nu elke crafting-operatie de RNG, zelfs als deze deterministisch is.

Dit betekent dat geen enkele andere machine parallel kan draaien zonder de RNG-status te beïnvloeden. Een interessant detail: op een gegeven moment werd de generalRandomGenerator gebruikt voor de beweging van vissen. Dit zou een ramp zijn voor voorspellingen, omdat elke vis op de map een onbekend aantal aanroepen zou genereren. Gelukkig is dit in versie 2.1.13 opgelost door een aparte fishRandomGenerator te introduceren.

Conclusie

Dit project heeft meer dan twee jaar in beslag genomen en heeft geleid tot een volledig autonome "gamblen't"-machine. Het bewijst dat zelfs complexe systemen in Factorio, mits men de wiskunde en de binary begrijpt, volledig voorspelbaar en manipuleerbaar zijn.

***

Voetnoten: [1] Zie Factorio Friday Facts #375. [2] Voor beveiligingsonderzoekers betekent "triviaal breekbaar" dat ze weten hoe het moet, ook al vereist het enige voorbereiding. [3] Hier realiseerde ik me dat structuren als Lichaam, Ring en Monoïde eigenlijk de wiskundige variant zijn van programmeren met generics. [4] Factorio biedt de --dump-data command line argument om prototypes in JSON-formaat te exporteren. [5] In Factorio is de som van signalen op een draad equivalent aan een XOR-operatie als men alleen naar de laatste bit kijkt. [6] De in-game implementatie van Gauss-eliminatie is inbegrepen in de world download. [7] In tegenstelling tot Ghidra, waarbij zelfs 64 GB RAM niet genoeg waren om het game-exe succesvol te decompileren.