一種利用資訊熵獎勵智能體構建方塊世界(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. 完整系統
- 在一劃定的範圍內，所包含的方塊、收納方塊內容物、掉落物與玩家物品欄（裝備欄）內容物。
3. 方塊系統
- 在一劃定的範圍內，所包含的方塊與收納方塊內容物。
5. 玩家系統
- 玩家物品欄（裝備欄）內容物。

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

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

### 天然資源 (Natual Resource)
使用 Cuberite 1.7.X-linux64[^Cuberite-release] 生成地圖並搭配插件[^statistics-plugin]統計方塊數量。總共抽樣 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)所說的[^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}
$$

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

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

[^statistics-plugin]: FlySkyPie/cuberite-block-counter: To make statistics of blocks. Retrieved 2020-05-31, from https://github.com/FlySkyPie/cuberite-block-counter

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

###### tags: `The Key Of Huanche`