在波函數塌縮演算中,我們可以選擇最小夏農熵(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)這條公式的過程中,我們真正學到的是思考「狀態是由哪些元素組成」這件事。

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

作者簡介


報名台灣唯一超規格資安盛會


熱門新聞

Advertisement