數學大神攻克猜字遊戲Wordle：連資訊理論都用上了
免費猜字小遊戲Wordle正在席捲全球，火到以數百萬美元的價格被收購，全球玩家數量也突破了200萬。
如果你在微博、微信等地方看到這些神神秘秘的方塊，那就是Wordle玩家在分享自己當日的戰績了。
根據統計，大多數人類玩家需要猜測4次或以上才能取得勝利。
比如，2月5日的題目在當天30多萬份曬出戰績的玩家中，只有27%能在三次以內猜中。
這個遊戲自然也成了程式設計師們的新競技場，他們寫出各種演算法來比拼誰用的步數最少。
這其中，百萬粉數學科普大神3Blue1Brown的玩法更為硬核——
他不光寫出了求解演算法，還用數學知識一步步優化至逼近理論極限，最終成績平均3.138次猜測就能獲勝。
並且他用統計辦法找出了與人類常見策略不同的最佳開局單詞crane。
他像往常一樣把這個過程整理成影片分享出來，不僅展示了演算法，還把其中涉及的資訊理論、統計學知識講得明明白白。
影片發布一天之內就有上百萬播放，圍觀的網友也紛紛在評論區表達了讚歎。
為了遊戲點進來，為了精彩的資訊理論知識留下，太酷了！
他用了什麼樣的演算法，理論極限又是怎麼算出來的？下面一起來看看。
從每一次猜測中獲得最多資訊
Wordle的遊戲規則很簡單，玩家需要猜出程式每天指定的一個5位英語單詞謎底。
玩家可以隨意提交一個英語單詞，但必須是字典里有的，不能胡亂拼寫。
如果字母在謎底中出現且位置對了就顯示綠色，字母出現了但位置不對就顯示黃色，字母在答案的單詞中沒出現就顯示灰色。
根據回饋資訊再進行下一輪猜測，在6次嘗試之內猜出就算贏。
如何讓步數盡量少？
3Blue1Brown的總體思路是盡量從每一次猜測中獲得最多的資訊。
他先是找來了26個字母在英語文本中出現頻率的統計數據，嘗試在前兩次嘗試中覆蓋最多高頻字母。
比如other+nails的組合，就可以覆蓋出現頻率最高的11個字母中的10個，如果運氣好就能確定下來一些字母。
即使這些字母都沒出現依然是一種資訊量很大的回饋，10個常用字母都沒出現的單詞數量就大大減少了，讓下一步猜測更簡單。
不過在嘗試過程中，又出現了新的問題。
同樣用nails這幾個字母，也可以拼成snail ，這兩種拼寫順序之間的差異，僅依據字母頻率數據是無法衡量的。
下面需要一種新的計算方法。
如何計算資訊量？
原版Wordle遊戲里有一個數量12972的總單詞列表，都能作為猜測詞使用。
另外有一個2315個單詞的列表，只有這些單詞會出現在答案里(據說是遊戲作者的女朋友挑選的)。
因為遊戲是用Javascript寫的，數據都在客戶端，這些數據直接可以從源碼里找到。
不過3Blue1Brown覺得讓程式利用答案列表的話有點像作弊了，他果斷給自己加大難度，只考慮總單詞列表。
遊戲中，每一次猜測都能從12972個單詞中排除一些結果。
比如猜測weary，如果W位置正確同時A出現了，那麼剩下的可選單詞只剩58個。
這樣對同一個猜測，從5個字母全沒出現到5個字母全對的各種回饋的概率都可以計算出來。
這樣，問題就變成了如何評估各種回饋情況包含的資訊量。
3Blue1Brown選擇的辦法，就是利用資訊理論祖師爺香農提出的資訊熵概念。
資訊熵描述的是事件的不確定性，單位就是大家知道的比特。
理解起來也不難，可以用扔硬幣來解釋。
扔1枚硬幣只會出現正、反兩種結果，而且概率相等。
扔2枚硬幣就有正正、正反、反正、反反這4種結果，扔3枚有8種情況等等，也就是扔n次有2的n次方種結果。
當一個事件有兩種結果且概率都是1/2，其不確定性相當於扔1枚硬幣，此時資訊熵定義為1比特。
如果一個事件有8種結果且概率都是1/8，就相當於扔3枚硬幣，此時資訊熵就是3比特。
資訊量和資訊熵的數量相等、意義相反，相當于衡量一則資訊能消除多少不確定性。
設每種結果的概率為p，資訊量為I，有如下等式。
稍作變換，可以得到資訊量的計算公式。
回到Wordle遊戲上，一次猜測獲得的資訊量可以用每種可能情況的概率與對應資訊量相乘、再把結果相加來計算，也就是求數學期望。
以猜測weary為例，計算出獲得的資訊量為4.9比特。
代表這則資訊消除的不確定性比扔5個硬幣的不確定性少一點。
演算法思路有了，接下來就可以交給程式，計算出所有12972個單詞的能消除的資訊熵。
用同樣的方法，可以再計算第二步、第三步猜測能消除的資訊熵。
根據這些計算結果，程式就可以在每一次猜測時，選擇所有可能單詞里能消除資訊熵最多的那個。
比如第一次猜slate獲得一次回饋，此時還剩下578個單詞可選，其中選ramin能消除最多的資訊熵，這樣一步一步猜直到猜出正確答案。
接下來，拿這個程式在所有2135種可能的答案上跑一遍，平均用了4.124步猜出正確答案。
3Blue1Brown覺得這個成績還不夠好，至少沒有超過普通人類玩家水平，還需要繼續優化。
最終成績逼近理論極限
成績不夠好的一個問題出在每個單詞作為答案的可能性其實並不相同。
像aahed aalii aargh這種偏門單詞雖然在允許猜測的總單詞列表裡，但並不在答案列表的2315個單詞里。
找一個典型的例子，當遇到abbas（人名，阿巴斯）和abyss（深淵）二選一時，如果程式能知道abyss是常用詞，就可以省下一步。
下一步改進方向就是引入詞頻統計數據，這樣的數據集可以從Wolfram上找到。
這裡還遇到一個問題，比如which和braid的出現頻率相差1000倍，但都可以算是常見單詞，出現在答案列表裡的可能性相差不大。
解決辦法就是用Sigmoid函數做處理，讓更多數據靠近0或1。
將處理後的詞頻數據與前面的資訊量計算結果相結合，得到優化後的資訊量計算方法。
在實際遊戲中，也把資訊量與詞頻結合考慮，就能讓程式更傾向於選擇常見單詞。
比如在下面的情況中，words和dorms的資訊量並不是最高的，但因為詞頻較高所以優先考慮。
優化後的成績到了3.601，平均節省了半步。
如果加大計算量，每次根據兩步搜索的結果選擇單詞可以進一步提高成績。
而且根據兩步搜索的計算結果，3Blue1Brown認為能獲得最大資訊量的開局單詞是crane。
此外還可以讓程式知道具體哪2315個單詞真的是在答案列表裡的，用上所有這些技巧後，成績再次提升到3.438。
實際上這個成績的理論極限就不可能低於3。
2315種答案意味著有11.17比特的不確定性，而暴力搜索後，前兩步能獲得的最大資訊量在10.01比特，還剩下1.16。
也就是說第三步的難度比二選一還要難一點，沒有演算法能保證每次都正確。
不過3Blue1Brown還是找到了新辦法進一步提升成績。
讓程式記住每個正確答案，並在下一局中把猜過的單詞排除出去，最終成績到達3.138，逼近了理論極限。
看完整個影片後，有網友表示學到的資訊理論知識比上課學到的還多。
也有很多人對到底哪個單詞才是最佳開局展開了討論。
雖然兩步搜索的結果是crane，不過3Blue1Brown也不確定對於人類玩家來說是不是最佳開局單詞。
畢竟實際遊戲中人類很難像程式一樣算出第二步的情況。
對於人類來說，soare和tares都是很好的開局。
還能挑戰變態模式
程式寫好後，3Blue1Brown還做了更多嘗試，比如原版Wordle的困難難度，成績是3.562，
還有一個Wordle變態版Absurdle，這個版本不再限制嘗試次數，但變態之處在於遊戲AI會與玩家對抗。
玩家猜測一次後正確答案就會變化，在所有回饋可能性中挑選資訊熵最大的那個，就像是在躲避玩家的猜測。
Absurdle的作者之前還開發過一個變態版俄羅斯方塊，每次都給你最不需要的方塊。
對於這個變態版Wordle，結果3Blue1Brown的程式也挑戰成功。
如果你看到這裡也想挑戰這個變態版試試，可以點下方鏈接。
原版遊戲地址：點此跳轉
變態版遊戲地址：點此跳轉
