一種利用資訊熵獎勵智能體構建方塊世界(Minecraft)的方法

評價資源

我們能夠直觀的以資源的稀有程度去抽象的衡量資源的價值；越稀有的資源越有價值，反之亦然。但是經濟學上的價值是透過供需市場產生的，並不能作為有明確定義的綱量。我們能獲得的是資源生成在地圖上的機率，但是僅有資源機率並不能夠適當直接作為 agent 的評價手段，需要一些額外的處理。

夏農熵與夏農資訊 (Shannon Entropy and Information)

夏農熵本質上是對我們司空見慣的「不確定現象」的數學化度量。¹

$$\mathrm H (X) = \mathrm{E}[\mathrm{I}(X)] = \mathrm{E}[-\ln(\mathrm{P}(X))]$$

其中 $I$ 為夏農資訊，被定義為：

$$I(X) = - \log_2 \mathrm{P}(X)$$

我們可以注意到當中的 $-\log_2 p_i$ 所描述的意義為：「事件發生的機率越低，則當該事件發生時所夾帶的資訊越大」，因此夏農熵也是對不確定的夏農資訊的期望值，亦可寫作：

$$\mathrm H (X) = - \sum_i p_i \log_2 p_i$$

合成式 (Formular of Crafting)

為了方便描述合成或其他遊戲機制使資源 (items) 發生變化的過程，我借用了化學反應式的形式來表達：

$$aX + bY \xrightarrow[P]{} cZ$$

$a,b,c$：原料或產物的數量 $X,Y$：原料，合成過程會被消耗的物品 $Z$：產物 $P$：合成途徑，參與合成但是不會被消耗的物品。

資源的資訊量 (Information of Items)

Minecraft 世界在本質上就是一團數位資料，因此將其視作一串由方塊構成的資訊，並用夏農熵或夏農資訊去衡量其資訊量是十分合理的作法。對於一個不確定狀態的方塊來說，其值為：

$$\mathrm H (X) = \mathrm{E} ( \mathrm{I}) = - \sum_i p_i \log_2 p_i$$

其 中$p_i$ 為某種類型的方塊出現在地圖中的機率，換句話說我們可以得知特定種類方塊其資訊量為：

$$I_x = -\log_2 p_x$$

合成的資訊量 (Information of Crafting)

天然資源能夠以其在地圖生成的機率來計算熵，但是 Minecraft 中的大部分物品需透過合成途徑獲得，當我提到合成是指：「能夠被合成式所表示的所有遊戲機制」，這些非天然物品的熵需透過計算取得。

以一個合成為例：

$$X + Y \xrightarrow[W]{} Z$$

$X,Y,W$ 分別代表三種不同類型的方塊，我們可以視作三個隨機事件，而這三者出現在地圖的機率分別為 $p_X, p_Y, p_W$ 並且互為獨立事件，因此我們可以得知事件 $Z$ 發生的機率為三者的機率相乘，也就是三者資訊量的加總：

$$\begin{align} I_Z &= -\log_2(p_X p_Y p_W) \\ &= -\log_2 p_X -\log_2 p_Y -\log_2 p_W \\ &= I_X + I_Y + I_W \end{align}$$

數量的變化 (The ratio between resource and product)

當原料與產物的比值不為 1 時，物品的總數量發生了變化。

$$mX \xrightarrow[P]{} nY$$

則：

$$H_Y = \frac{m}{n}H_X$$

合成途徑 (Crafting Path)

作為合成途徑的物品不會被消耗，因此：

$$\begin{array}{l} X \xrightarrow[W]{} Y & \Delta I = I_W \end{array}$$

多重途徑 (Multiple Crafting Path)

當一個物品有多種取得途徑時可以視作一個並聯系統 (parallel systems)，因此該物品的資訊量可以寫作：

$$I = -\log_2 [1 - \prod_i(1-p_i)]$$

零資訊的資源 (The Items with Zero Entropy)

怪物掉落物仰賴怪物的生成，但是怪物生成的機率並不是與空間關聯，而是與時間關聯的，以空間機率考慮：

$$H |_{\Delta t = 0}= -\lim_{p \rightarrow0^+} p\log p = 0$$

若或是考慮其在無窮的時間中能夠被無限生成，事件發生的機率為 1，因此：

$$H |_{t \rightarrow \infty} = -\log(1) = 0$$

環境的資訊量 (Information of Environment)

當我們要量化系統的資訊量時，必須先界定所謂的「系統」。要定義一個系統，我們要給定一個範圍（空間大小）以及具體包含了多少方塊或物品。以下有三種定義應該是我們比較常用的系統類型：

1. 完整系統
   • 在一劃定的範圍內，所包含的方塊、收納方塊內容物、掉落物與玩家物品欄（裝備欄）內容物。
2. 方塊系統
   • 在一劃定的範圍內，所包含的方塊與收納方塊內容物。
3. 玩家系統
   • 玩家物品欄（裝備欄）內容物。

透過到目前為止建立的規則，我們可以量化一個系統的熵，而該值能透過統計地圖中的方塊與實體取得。隨著 agent 在環境中活動，我們可以預期環境的熵會因此發生改變，這個變化量便可做為評量 agent 的指標之一。

資訊量表 (Table of Items Information)

以下的資訊量評估值僅供參考，過程並不嚴謹並且沒有對所有的物品進行計算。目的只是透過實做示範如何實踐本文建構的理論，有興趣的人可以自行用更嚴謹的方式建構完整的遊戲物件資訊量表。

天然資源 (Natual Resource)

使用 Cuberite 1.7.X-linux64² 生成地圖並搭配插件³統計方塊數量。總共抽樣 10 次，每次都會將地圖檔案刪除以生成新的種子。為了簡化數據，將紅花與黃花視為同樣的東西，並將流動水、流動岩漿、鵝卵石、火把、火焰、生怪磚、箱子與枯萎灌木移除並用空氣取代。統計資料如下表：

方塊	數量	生成機率	資訊量	熵
Air	151464079	0.7506049	0.4138744	0.3106562
Bedrock	788224	0.0039062	8.0000287	0.0312495
Brown Mushroom	648	0.0000032	18.2484248	0.0000586
Cactus	11	0.0000001	24.1288432	0.0000013
Clay	8790	0.0000436	14.4866274	0.0006310
Coal Ore	345962	0.0017145	9.1880208	0.0157526
Cobweb	1998	0.0000099	16.6239340	0.0001646
Diamond Ore	19629	0.0000973	13.3275758	0.0012964
Dirt	2347857	0.0116352	6.4253617	0.0747603
Double Plant	14242	0.0000706	13.7904107	0.0009733
Fence	8543	0.0000423	14.5277478	0.0006151
Flower	4014	0.0000199	15.6174499	0.0003107
Gold Ore	43697	0.0002165	12.1730282	0.0026360
Grass	471646	0.0023373	8.7409299	0.0204303
Gravel	534501	0.0026488	8.5604417	0.0226750
Iron Ore	395336	0.0019592	8.9955550	0.0176237
Lapis Lazuli Ore	17690	0.0000877	13.4776284	0.0011815
Leaves	382779	0.0018969	9.0421227	0.0171522
Lily Pad	122	0.0000006	20.6575375	0.0000125
Obsidian	2390	0.0000118	16.3654799	0.0001938
Rail	2528	0.0000125	16.2844941	0.0002040
Red Mushroom	974	0.0000048	17.6604969	0.0000852
Redstone Ore	160117	0.0007935	10.2995079	0.0081725
Sand	272220	0.0013490	9.5338613	0.0128615
Sandstone	109888	0.0005446	10.8426005	0.0059045
Snow	3033	0.0000150	16.0217451	0.0002408
Still Lava	158088	0.0007834	10.3179065	0.0080834
Still Water	3281908	0.0162640	5.9421715	0.0966437
Stone	40812030	0.2022507	2.3057837	0.4663463
Sugar Canes	41	0.0000002	22.2307228	0.0000045
Tallgrass	66818	0.0003311	11.5603257	0.0038279
Vines	1179	0.0000058	17.3849268	0.0001016
Wood Plank	12762	0.0000632	13.9487080	0.0008822
Wood	55614	0.0002756	11.8251144	0.0032591

加工品 (Products)

木板

$$\text{Wood} \xrightarrow[]{} 4 \text{ Wood Plank}$$ $$\begin{align} I_{WP} &= \frac1{4} I_{W} = 0.25 \cdot 11.8\\ &= 2.95 \end{align}$$

工作台

$$4 \text{ Wood Plank} \xrightarrow[]{} \text{Crafting Table}$$ $$\begin{align} I_{CT} &= 4 I_{WP} = 4 \cdot 2.95 \\ &= 11.8 \end{align}$$

木棒

$$2 \text{ Wood Plank} \xrightarrow[]{} 4 \text{ Stick}$$ $$\begin{align} I_{S} &= \frac{2}{4} I_{WP} = 0.5 \cdot 2.95 \\ &= 1.475 \end{align}$$

木鎬

$$3 \text{ Wood Plank} + 2 \text{ Stick} \xrightarrow[\text{Crafting Table}]{} \text{ Wooden Pickaxe}$$ $$\begin{align} I_{\text{WPickaxe}} &= 3 I_{\text{WPlank}} + 2 I_{S} + I_{CT}\\ &= 3 \cdot 2.95 + 2 \cdot 1.475 + 11.8\\ &= 23.6 \end{align}$$

鵝卵石

為了簡化計算，下列過程不考慮其他材質的鎬挖掘的情況。

$$\text{ Stone } \xrightarrow[\text{Wooden Pickaxe}]{} \text{ Cobblestone}$$ $$\begin{align} I_{C} &= I_{S} + I_{WP} \\ &= 2.31 + 23.6 \\ &= 25.91 \end{align}$$

熔爐

$$8\text{ Cobblestone } \xrightarrow[\text{Crafting Table}]{} \text{ Furnace}$$ $$\begin{align} I_{F} &= 8I_{C} + I_{CT} \\ &= 8 \cdot 25.91 + 11.8 \\ &= 219.08 \end{align}$$

石鎬

$$3 \text{ Cobblestone} + 2 \text{ Stick} \xrightarrow[\text{Crafting Table}]{} \text{ Stone Pickaxe}$$ $$\begin{align} I_{\text{SP}} &= 3 I_{\text{C}} + 2 I_{S} + I_{CT}\\ &= 3 \cdot 25.91 + 2 \cdot 1.475 + 11.8\\ &= 92.48 \end{align}$$

鐵礦

為了簡化計算，下列過程不考慮其他材質的鎬挖掘的情況。

$$\text{ Iron Ore } \xrightarrow[\text{Stone Pickaxe}]{} \text{ Iron Ore Item}$$ $$\begin{align} I_{IOI} &= I_{IO} + I_{SP} \\ &= 9.00 + 92.48 \\ &= 101.48 \end{align}$$

煤

為了示範並聯系統的計算，以下僅考慮木鎬與石鎬的挖掘途徑。

$$\text{ Coal Ore } \xrightarrow[\text{Wooden(Stone) Pickaxe}]{} \text{ Coal}$$ $$\begin{align} I_{C1} &= I_{CO} + I_{WP} \\ &= 9.18 + 23.6 \\ &= 32.78 \end{align}$$ $$\begin{align} I_{C2} &= I_{CO} + I_{SP} \\ &= 9.18 + 92.48 \\ &= 101.66 \end{align}$$ $$\begin{align} p_1 = 2^{-I_1} = 2^{-32.78} = 1.35592835311 \cdot 10^{-10} \\ p_2 = 2^{-I_2} = 2^{-101.66} = 2.49626473127 \cdot 10^{-31} \\ p = 1 - (1-p_1)(1-p_2) = 1.355928702651 \cdot 10^{-10} \end{align}$$ $$I_C = -\log_2 p = 32.78$$

鐵錠

$$\text{ Iron Ore Item} + \frac1{8} \text{ Coal} \xrightarrow[\text{Furnace}]{} \text{ Iron Ingot}$$ $$\begin{align} I_{II} &= I_{IOI} + \frac1{8} I_{C} + I_{F} \\ &= 101.48 + 0.125 \cdot 32.78 + 219.08\\ &= 324.6575 \end{align}$$

資訊量總表 (The Table)

正如我提過得，本文並沒有計算所有物品的資訊量，僅是將先前統計或計算得到的數值做個整理，因此這個表並不完整。

方塊/物品	資訊量	方塊/物品	資訊量
Iron Ingot	324.66	Lapis Lazuli Ore	13.48
Furnace	219.08	Diamond Ore	13.33
Iron Ore Item	101.48	Gold Ore	12.17
Stone Pickaxe	92.48	Wood	11.83
Coal	32.78	Crafting Table	11.80
Cobblestone	25.91	Tallgrass	11.56
Cactus	24.13	Sandstone	10.84
Wooden Pickaxe	23.60	Still Lava	10.32
Sugar Canes	22.23	Redstone Ore	10.30
Lily Pad	20.66	Sand	9.53
Brown Mushroom	18.25	Coal Ore	9.19
Red Mushroom	17.66	Leaves	9.04
Vines	17.38	Iron Ore	9.00
Cobweb	16.62	Grass	8.74
Obsidian	16.37	Gravel	8.56
Rail	16.28	Bedrock	8.00
Snow	16.02	Dirt	6.43
Flower	15.62	Still Water	5.94
Fence	14.53	Wood Plank	2.95
Clay	14.49	Stone	2.31
Wood Plank	13.95	Stick	1.48
Double Plant	13.79	Air	0.41

結語

就如像詹姆斯·拉夫洛克(James Lovelock)所說的⁴：

I’d look for an entropy reduction, since this must be a general characteristic of life.

我們可以透過 agent 對環境進行改造從而造成的熵減量，作為衡量策略的方法：

$$\Delta S_{\pi,t} = S_o - S_{\pi,t} \\ \pi^* = \arg \min_{\pi} \Delta S_{\pi,t}$$

Footnotes

1. 信息熵是什么？ - 知乎. (返朴). Retrieved 2020-05-31, from https://www.zhihu.com/question/22178202/answer/667876061 ↩

2. Releases · cuberite/cuberite. (cuberite). Retrieved 2020-05-31, from https://github.com/cuberite/cuberite/releases/download/1.7EOL/Cuberite-linux64.tar.gz ↩

3. FlySkyPie/cuberite-block-counter: To make statistics of blocks. Retrieved 2020-05-31, from https://github.com/FlySkyPie/cuberite-block-counter ↩

4. Lovelock, James (1979). GAIA – A New Look at Life on Earth. Oxford University Press. ISBN 978-0-19-286218-1. ↩