源文檔：https://docs.google.com/document/d/1stTJAjLmCXtqctdFOpuv4lylegcmfO8mFrptFtwqb78/edit

本機(jī)翻pdf版百度云鏈接: https://pan.baidu.com/s/1tqPu5A0oFCjNEB-4b3P2uA?pwd=1234

提取碼: 1234

這個(gè)項(xiàng)目的目標(biāo)是在Minecraft游戲中用紅石完全逆轉(zhuǎn)并模擬一個(gè)特定的隨機(jī)器，即Math.random。

以下是使用Math.random的所有事物的完整列表，突出顯示的部分是我們正在使用的重要部分：

以任何方式創(chuàng)建任何類型的生物實(shí)體，包括通過正常生成、加載或維度更改產(chǎn)生的玩家、怪物和盔甲架。（3次調(diào)用）

當(dāng)實(shí)體受到攻擊時(shí)，計(jì)算擊退力。（可變次數(shù)的調(diào)用）

實(shí)體破壞物品時(shí)產(chǎn)生的粒子。（5次調(diào)用，每個(gè)粒子一次）

實(shí)體進(jìn)食時(shí)產(chǎn)生的粒子。（可變次數(shù)的調(diào)用，每個(gè)粒子一次。如果完全吃掉一個(gè)普通食物物品，46次調(diào)用）

以任何方式創(chuàng)建物品實(shí)體。（4次調(diào)用）

以任何方式創(chuàng)建經(jīng)驗(yàn)球?qū)嶓w。（4次調(diào)用）

TNT隨機(jī)角度。（1次調(diào)用）

液體混合以生成石頭、圓石或黑曜石。（16次調(diào)用，每個(gè)粒子兩次）

用桶在下界嘗試放置水。（24次調(diào)用，每個(gè)粒子三次）

當(dāng)平均獲得的經(jīng)驗(yàn)值嚴(yán)格在0和1之間時(shí)，從熔爐輸出槽中拿取物品。（1次調(diào)用）

在怪物生成算法中，生成怪物群的大小。（每個(gè)群1次調(diào)用）

逆轉(zhuǎn)

這個(gè)過程的這一部分逆轉(zhuǎn)了Math.random的當(dāng)前種子，這樣我們就可以預(yù)測所有未來（和過去，但誰在乎）的Math.random值。可以使用7個(gè)TNT實(shí)體的隨機(jī)角度，這些實(shí)體已經(jīng)從中心爆炸到半徑為120個(gè)方塊的圓上（以夸大角度），在那里角度可以被檢測到大約1個(gè)方塊的分辨率。

線性同余生成器（LCGs）背景知識

一般的LCG是一種隨機(jī)數(shù)生成器（RNG），它具有與生成器當(dāng)前輸出相同的內(nèi)部狀態(tài)（“種子”），并在每次調(diào)用后按以下公式更新其種子：

其中a、b和m是精心選擇的常數(shù)，用于產(chǎn)生類似隨機(jī)的序列。在Java中，這些常數(shù)的值為a=25214903917,b = 11,m = 2^48，盡管輸出被截?cái)酁樽疃嘀皇褂庙敳?2位。這使得Java LCG的內(nèi)部狀態(tài)長度為48位。

盡管Java選擇了好的參數(shù)，但所有的LCG都不可避免地存在一些共同的弱點(diǎn)：

低位具有高周期性（即它們的序列傾向于更頻繁地重復(fù)自身）；這就是為什么Java只返回高32位，但在某些情況下仍然可以利用（盡管我們不打算使用這個(gè)）。

如果你取一個(gè)n×n的矩陣，其行是模數(shù)為m的LCG的連續(xù)調(diào)用，并取其行列式，那么這個(gè)行列式總是具有k×m^(n-1)的形式，k屬于整數(shù)集Z。如果k等于1，這些向量就生成了LCG可以生成的所有點(diǎn)（參見第3點(diǎn)）。

如果你用LCG在二維空間或更高維空間中繪制點(diǎn)，它會形成一個(gè)點(diǎn)的格子（像一個(gè)傾斜的網(wǎng)格），這看起來一點(diǎn)也不隨機(jī)。正是這個(gè)格子，我們將在這次逆轉(zhuǎn)中利用。

像我是本科生一樣解釋非正式的格子LCG逆轉(zhuǎn)數(shù)學(xué)描述

（如果你不喜歡數(shù)學(xué)，可以跳過這部分，但如果你想了解Matthew說的任何事情，請閱讀）。

這一部分需要一些線性代數(shù)的背景知識。如果你的線性代數(shù)基礎(chǔ)不穩(wěn)，我建議觀看3blue1brown線性代數(shù)系列（譯注：b站鏈接）的前幾個(gè)視頻。

以一個(gè)簡單的LCG為例，我們將使用連續(xù)的兩個(gè)偽隨機(jī)數(shù)來逆轉(zhuǎn)LCG的種子。實(shí)際上，我們使用的是一個(gè)更大的LCG的7個(gè)連續(xù)輸出，但這很難可視化，所以我們將堅(jiān)持這個(gè)簡單的例子——它的工作原理是相同的。

我們的迷你LCG將具有參數(shù)a = 5,b = 3,m = 8。從種子0開始，我們的隨機(jī)數(shù)序列是（如果你愿意，你可以自己驗(yàn)證這一點(diǎn)）：0,3,2,5,4,7,6,1,0,? 因此，連續(xù)調(diào)用的對是：(0,3),(3,2),(2,5),(5,4),(4,7),(7,6),(6,1),(1,0)。我們將這些點(diǎn)繪制在一張圖上：

這是一個(gè)格子，正如你所看到的，它一點(diǎn)也不隨機(jī)。那么，假設(shè)我們想要找到一個(gè)種子，它可以產(chǎn)生兩個(gè)連續(xù)的隨機(jī)數(shù)大于或等于5。在圖上，每個(gè)點(diǎn)的x坐標(biāo)是第一個(gè)隨機(jī)數(shù)，y坐標(biāo)是第二個(gè)隨機(jī)數(shù)。所以我們可以繪制一個(gè)框，表示我們想要在其中搜索的不等式：

從圖中可以很明顯地看出解決方案會是什么，但請記住，這只是一個(gè)在二維空間中過于簡化的LCG。

在平面平移之后，使得這個(gè)格子上的一個(gè)點(diǎn)位于原點(diǎn)，這樣一個(gè)格子可以由兩個(gè)基向量來描述，這樣任何在格子上的點(diǎn)都可以通過添加這兩個(gè)向量的整數(shù)倍來到達(dá)。在這個(gè)例子中，我將把H點(diǎn)平移到原點(diǎn)，然后選擇基向量(1,5)和(0,8)。見下圖。

現(xiàn)在，你應(yīng)該能很容易地看到，可以應(yīng)用一個(gè)逆線性變換，將這些基向量變成兩個(gè)單位向量?和?；我們將平面上的每個(gè)點(diǎn)向量v乘以行向量：

經(jīng)過逆變換后，我們的格子變成了這個(gè)樣子：

你可能會想，進(jìn)行這個(gè)變換的意義是什么，問題看起來和以前一樣困難。你是對的；這是因?yàn)槲覀円婚_始選擇了較差的基向量。不過，你應(yīng)該注意到，現(xiàn)在與之前不同的是，我們的不等式平行四邊形內(nèi)唯一的整數(shù)坐標(biāo)是點(diǎn)F，這正是我們要尋找的點(diǎn)。這是因?yàn)槲覀円呀?jīng)將格子轉(zhuǎn)換為整數(shù)坐標(biāo)（兩個(gè)新基向量的整數(shù)倍將我們帶到整數(shù)坐標(biāo)的任何地方）。

那么我們?nèi)绾芜x擇更好的基向量呢？讓我們明確一下我們想要的。我們希望盡可能少地搜索整數(shù)坐標(biāo)，所以我們希望我們的基向量在大小上大致相等，這樣一切都會更加均勻地收縮。這對應(yīng)于大致正交的基。有一個(gè)算法，LLL縮減，它接受我們的兩個(gè)原始基向量，并對它們進(jìn)行這樣的處理。我不會在這里詳細(xì)介紹，但維基百科有一篇很好的文章。經(jīng)過LLL縮減后，我們的基向量變成了這樣：

在應(yīng)用逆變換后，它看起來是這樣的：

你可以看到這使得問題變得容易得多，尤其是在更高的維度（更多的連續(xù)調(diào)用）和更復(fù)雜的LCG中。有足夠好的基向量，在平行四邊形上找到整數(shù)點(diǎn)可以簡單到取點(diǎn)的地板值。

在找到這個(gè)平行四邊形內(nèi)的點(diǎn)F后，你只需重新應(yīng)用基向量的變換，并平移回去，使H回到(1,0)而不是原點(diǎn)，然后，因?yàn)閷τ贚CG，種子和輸出是相同的，選擇結(jié)果向量中的第一個(gè)數(shù)字，你就得到了你的種子。

我想提到的最后一件事是，調(diào)用不必是連續(xù)的，只要在你的兩個(gè)值之間有一個(gè)已知的常數(shù)調(diào)用次數(shù)。這是因?yàn)?，如果你取LCG的每一個(gè)其他調(diào)用，那相當(dāng)于使用一個(gè)新的LCG：

因此，新的LCG具有參數(shù)(a^2 ?mod m,ab+b mod m,m)。對于任意數(shù)量n的連續(xù)調(diào)用，你可以繼續(xù)形成一個(gè)LCG (a^n ?mod m ,b×(a^n-1)/(a-1) mod m ,m)。

實(shí)踐中的逆轉(zhuǎn)

我們使用7個(gè)TNT的隨機(jī)角度，通過半徑為120的圓中的692個(gè)探測器進(jìn)行檢測。

一個(gè)探測器僅在TNT爆炸的tick被觸發(fā)。探測器是一個(gè)觸發(fā)器，TNT實(shí)體在爆炸前的磚塊tick階段與其相交。在此之前，圍繞圓周的觸發(fā)器將被物品實(shí)體觸發(fā)，計(jì)時(shí)使得觸發(fā)器在此磚塊tick階段檢查相交實(shí)體，導(dǎo)致正確的觸發(fā)器額外激活10個(gè)tick。在多個(gè)觸發(fā)器仍然被激活的可能情況下（即TNT在兩個(gè)探測器之間爆炸），我們?nèi)∧鏁r(shí)針方向上的探測器，并說它被激活。

探測器對應(yīng)于TNT可能被發(fā)射的角度范圍。角度由Math.random() ×2π計(jì)算，Math.random的實(shí)現(xiàn)就像：

其中next(x)表示使LCG前進(jìn)一位并取最高的x位。

因此，種子的最高26位與TNT發(fā)射的角度成離散比例，允許我們將探測器與種子范圍對應(yīng)起來。此外，探測器n的上限角度是探測器n+1的下限角度；如果給定的角度給出了next(26)的上限，那么上限種子值必須是具有那26位的最高種子值，即剩余的22位都是1。下一個(gè)探測器的下限具有相同的26個(gè)上限位，但是下限的22位都是0。

使用這些種子范圍，我們可以形成一個(gè)表示這些范圍的7維超立方體，并按照上述方法逆轉(zhuǎn)種子。

Matthew在這里寫了所有的東西

將LCG的n個(gè)連續(xù)種子作為n維空間中的點(diǎn)的坐標(biāo)，揭示出一個(gè)晶格狀結(jié)構(gòu)，經(jīng)過原點(diǎn)平移后，該結(jié)構(gòu)在加法下與Z^n同構(gòu)。通過用LLL-約化基向量表示這種同構(gòu)關(guān)系的線性變換，我們可以有效地利用變換的逆矩陣將我們晶格的任何不等式系統(tǒng)表示為Z^n上的不等式系統(tǒng)。我們的機(jī)器產(chǎn)生7個(gè)值，它們的上限和下限是可能使TNT落在觸發(fā)探測器上的種子，這些值可以轉(zhuǎn)換為Z^n上的不等式系統(tǒng)。通過使用足夠大的探測器并在射擊之間有意調(diào)用LCG，我們可以在數(shù)學(xué)上保證只有一個(gè)Z^n元素能滿足新轉(zhuǎn)換的不等式系統(tǒng)（通過尋找正交程度足夠的晶格，使與我們的不等式相對應(yīng)的區(qū)域收縮到適合一個(gè)單位立方體內(nèi)）。對Z^n這一點(diǎn)的變換進(jìn)行反轉(zhuǎn)并平移空間，再次與原始晶格對齊，揭示出每次射擊時(shí)的7個(gè)種子。

具體而言，正在進(jìn)行的計(jì)算如下所示：

請注意，通過櫻桃挑選每個(gè)乘法的上限或下限，(v-b) M^(-1)可以得到一個(gè)點(diǎn)，其每個(gè)分量必然大于真實(shí)值。因?yàn)槲覀冞x擇的晶格總是在每個(gè)維度上距離真實(shí)值小于1，所以只需對每個(gè)分量取地板值就可以得到所需的Z^n點(diǎn)。在實(shí)踐中，所有可以預(yù)先計(jì)算的計(jì)算都已經(jīng)完成，因此這個(gè)描述并不準(zhǔn)確地表示機(jī)器實(shí)際上所做的計(jì)算。

校對：小灰灰

遵循知識共享協(xié)議CC-BY-NC-SA