波函數塌縮演算中的熵

在波函數塌縮演算中，我們可以選擇最小夏農熵（Shannon entropy）位置進行塌縮，目的是選擇狀態數量最少，較穩定的位置，避免傳播塌縮時對其他位置衝擊過大，導致後續可選擇的狀態變少。

塌縮位置的選擇？

波函數塌縮演算是2016年遊戲設計師Maxim Gumin提出的演算法，有效率地將有限的拼接塊（tile）做無限的拼接，然而，拼接塊之間又彼此相容。我在先前專欄文章〈理解波函數塌縮演算〉談過基本原理，若需要更多的說明，你可以參考〈Wave Function Collapse（一）〉。

在波函數塌縮演算的每一次迭代中，必須選出一個位置進行塌縮與傳播，首次塌縮可以隨機選擇，然而，在首次傳播之後，我們可以觀察到：每個位置的拼接塊數量各不相同了，有些甚至是塌縮至只剩一個拼接塊了，因此，位置的選取顯然要考量一下這個部份。

拼接塊數量是選擇位置時的一個考量，另外在生成拼接地圖時，通常也會考慮拼接塊的權重，例如，或許會想要陸地廣一些或是海岸線長一些之類的，若是如此，選擇位置的依據或許也可以是某個權重結果。

想依拼接塊數量、某個權重計算結果，或是其他因素，甚至是計算結果再加上些隨機，據以選擇位置，基本上都是看生成的地圖風格，是否能夠符合需求。

就像在Maxim Gumin的WaveFunctionCollapse談到，他採用具有最小夏農熵的位置來塌縮，這是因為他觀察到，人們解決類似問題時，所採取的方式，通常具有最小熵值的概念。

例如〈理解波函數塌縮演算〉中的婚禮賓客範例，就算你不知道波函數塌縮演算，當你要進行下一輪卡片的剔除時，應該會選卡片數量小的位置作為開始，而不是隨機選取，畢竟直覺或經驗上，這麼做比較能趕快確定一些人的位置。

熱力學熵到夏農熵

熵的原文為entropy，源於熱力學，是物理學家Rodolph Clausius於1854年提出，它本為熱量除以溫度的商數，而「熵」本無此字，是物理學家胡剛復陪同Max Planck在中國講學談及entropy，為了譯名上的聯想，而在「商」字旁加上「火」而創造了「熵」字。

即便在熱力學的領域，許多人也覺得熵極為神祕，而難以就日常經驗來解釋。根據物理學家Ludwig Boltzmann的發現，系統的熵，跟構成熱力學性質的微觀狀態數量有關，也就是將物質視為巨大數量的粒子組成，而粒子之間難以分辨，例如，容器中氣體分子的位置、動量等構成之狀態數量，也就是說「熵是個跟狀態有關的函數」。

熵後來被作為系統混亂程度的度量，系統中的狀態數量越多，系統會越混亂。例如，在維基百科〈熵〉條目中，有個丟硬幣的比喻，若有10個硬幣，丟硬幣時得到最有規律的狀態，是10個都為正面或反面，硬幣排列上只會構成兩種狀態；若是最混亂的情況，有5個正面、5個反面，硬幣排列上就會有252種。

Claude Shannon將熵引入了資訊理論（Information theory）的領域，作為不確定性的量度，熵越大，表示不確定性越大。

根據維基百科〈Entropy (information theory)〉條目來看，若X是變數，可能的值為(x1,x2,…,Xn)，P(xi)是xi出現的機率，那麼，夏農熵的計算方式是i從1到n，P(xi)*logb(P(xi))的總和乘上負號，logb代表以b為底的對數，b視使用的夏農熵單位而定，單位為bits時使用2，nats使用e，bans使用10。

例如，夏農熵常用在計算密碼強度，熵值越大，表示密碼組合的混亂程度越大，也就越難以組合出正確的密碼。換言之，若允許使用的字元有N個，密碼長度為L，密碼的可能組合就是 1/(N^L)，而每一種組合是一種狀態時，某組密碼出現的機率會是1/(N^L)。

對應至夏農熵公式，n就是1/(N^L)，P(xi)是1/(N^L)，採用bits為夏農熵單位。讓我們來整理一下公式後，此時，密碼強度的計算公式，就是維基百科Entropy as a measure of password strength列出的L*log(N)/log2，簡單來說，如果使用的字元個數越多，密碼長度會越長，熵值也就越大。

最小熵值作為塌縮位置

在波函數塌縮演算中，若某位置的拼接塊數量少，其周圍的拼接塊數量也不會多，選擇該位置塌縮成一個拼接塊，在傳播時對各位置的拼接塊衝擊較小，也就是傳播過程，各位置的拼接塊可以保有較多的選擇性，後續選擇某個拼接塊，發生死胡同的可能性會比較低。

也就是說，一個方式是選擇剩餘拼接塊數量少的位置，這也可以理解為，拼接塊數量少的位置，代表它受到周圍位置的限制較多，也就是它接收到周圍位置的資訊較多，才會擁有較少的拼接塊。

不過，拼接塊的數量並非狀態，畢竟兩個位置以上數量相同的情況下，有可能擁有不同的權重加總，反之，權重加總也不是狀態的全部，畢竟相同權重加總下，也可能有不同的拼接塊數量，最好的方式是兩者都考慮。

一般而言，夏農熵是個與狀態有關的值，公式在計算過程當中，考量了數量（1到n），若我們將權重設計進去來求得熵值，就可以作為狀態的代表，也就是，我們可以尋找最小熵值的位置來塌縮，WaveFunctionCollapse中的範例，就是採用權重作為夏農熵的計算依據。

若某位置拼接塊總權重是sumOfWeights，某拼接塊的權重為wi，該位置出現該wi權重的類型機率P(wi)是wi/sumOfWeights。套用到夏農熵公式整理一下，如果sumOfWeightLogWeights代表每個wi*log(wi)的加總，那麼，最後的公式將會是log(sumOfWeights)-(sumOfWeightLogWeights/sumOfWeights)。

而在〈The Wavefunction Collapse Algorithm explained very clearly〉中，則從另一角度來解釋為何最小熵值作為塌縮位置，若選擇高熵，代表該位置更難以確定要塌縮為哪一塊，如果選擇低熵，應能減少最後發生拼接塊不相容的可能性。

夏農熵與狀態

在波函數塌縮演算中，不使用熵來作為塌縮位置的依據，單純使用拼接塊的數量或總權重來選擇會怎樣嗎？

就我個人的實驗，在有限拼接塊、有限範圍下，是沒什麼問題，畢竟數量與總權重，都是狀態的組成元素之一，或許要在無限城之類的例子中，才有發生矛盾的可能性。

然而，在理解波函數塌縮演算中，為何要使用log(sumOfWeights)-(sumOfWeightLogWeights/sumOfWeights)這條公式的過程中，我們真正學到的是思考「狀態是由哪些元素組成」這件事。

事實上，夏農熵在資訊理論相關理論應用許多，而這樣的思考，將會有助於我們理解在各應用中，夏農熵為何足以發揮作用吧！